@techreport{LermenReinert97,
TITLE = {The practical use of the A* algorithm for exact multiple sequence alignment},
AUTHOR = {Lermen, Martin and Reinert, Knut},
LANGUAGE = {eng},
NUMBER = {MPI-I-97-1-028},
YEAR = {1997},
DATE = {1997},
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.},
TYPE = {Research Report / Max-Planck-Institut für Informatik},
}