MPI-INF/SWS Research Reports 1991-2021

2. Number - All Departments


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:

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},