max planck institut
informatik

# MPI-I-97-1-028

## The practical use of the $\calA^*$ algorithm for exact multiple sequence alignment

### Lermen, Martin and Reinert, Knut

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:

173 KBytes
Please note: If you don't have a viewer for PostScript on your platform, try to install GhostScript and GhostView
URL to this document: http://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},