b'@techreport{LermenReinert97,'b'\nTITLE = {The practical use of the A* algorithm for exact multiple sequence alignment},\nAUTHOR = {Lermen, Martin and Reinert, Knut},\nLANGUAGE = {eng},\nNUMBER = {MPI-I-97-1-028},\nYEAR = {1997},\nDATE = {1997},\nABSTRACT = {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.},\nTYPE = {Research Report / Max-Planck-Institut f\xc3\xbcr Informatik},\n}\n'