max planck institut
informatik
informatik
MPI-I-97-1-028. December 1997, 16 pages. | Status: available - back from printing | Next --> Entry | Previous <-- Entry
Abstract in LaTeX format:
Multiple alignment is an important problem in computational biology.
It is well known that it can be solved exactly by a dynamic programming
algorithm which in turn can be interpreted as a shortest path computation
in a directed acyclic graph. The $\cal{A}^*$ algorithm (or goal directed
unidirectional search) is a technique that speeds up the computation of
a shortest path by transforming the edge lengths without losing
the optimality of the shortest path.
We implemented the $\cal{A}^*$ algorithm in a computer program similar to
MSA~\cite{GupKecSch95} and FMA~\cite{ShiIma97}. We incorporated in this program
new bounding strategies for both, lower and upper bounds and show
that the $\cal{A}^*$ algorithm, together with our improvements, can speed up comput
ations
considerably. Additionally we show that the
$\cal{A}^*$ algorithm together with a standard bounding technique
is superior to the well known Carillo-Lipman bounding since it excludes
more nodes from consideration.
Acknowledgement:
References to related material:
| To download this research report, please select the type of document that fits best your needs. | Attachement Size(s): |
|---|---|
| 173 KBytes | |
| Please note: If you don't have a viewer for PostScript on your platform, try to install GhostScript and GhostView | |
BibTeX