MPI-I-97-1-028
The practical use of the $\calA^*$ algorithm for exact multiple sequence alignment
Lermen, Martin and Reinert, Knut
December 1997, 16 pages.
.
Status: available - back from printing
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.
-
- Attachement: ATTQX6BU (173 KBytes)
URL to this document: https://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/1997-1-028
BibTeX
@TECHREPORT{LermenReinert97,
AUTHOR = {Lermen, Martin and Reinert, Knut},
TITLE = {The practical use of the $\cal{A}^*$ algorithm for exact multiple sequence alignment},
TYPE = {Research Report},
INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
ADDRESS = {Im Stadtwald, D-66123 Saarbr{\"u}cken, Germany},
NUMBER = {MPI-I-97-1-028},
MONTH = {December},
YEAR = {1997},
ISSN = {0946-011X},
}