Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society


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
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.
References to related material:

To download this research report, please select the type of document that fits best your needs.Attachement Size(s):
MPI-I-97-1-028.ps173 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:
Hide details for BibTeXBibTeX
  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},