de.mpg.escidoc.pubman.appbase.FacesBean
English
 
Help Guide Disclaimer Contact us Login
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Report

The practical use of the A* algorithm for exact multiple sequence alignment

MPS-Authors
http://pubman.mpdl.mpg.de/cone/persons/resource/persons44914

Lermen,  Martin
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons45277

Reinert,  Knut
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Locator
There are no locators available
Fulltext (public)

1997-1-028
(Any fulltext), 11KB

Supplementary Material (public)
There is no public supplementary material available
Citation

Lermen, M., & Reinert, K.(1997). The practical use of the A* algorithm for exact multiple sequence alignment (MPI-I-97-1-028).


Cite as: http://hdl.handle.net/11858/00-001M-0000-0014-9CD5-4
Abstract
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.