Multiple Sequence Alignment Using Anytime A*

Abstract

Alignment of multiple DNA or protein sequences is a central problem in computational biology. To create an alignment, gaps are inserted into sequences to shift characters to matching positions and a scoring function is used to rank the biological plausibility of alignments. Multiple sequence alignments are used to identify homologies among different species that reveal evolutionary history from a common ancestor. They are also used to discover genetic causes of certain diseases and to predict protein structure, which has significant importance in the design of drugs. The multiple sequence alignment problem can be formalized as a shortest-path problem through a d-dimensional lattice, where d is the number of sequences to be aligned (Gusfield 1997). Dynamic programming is the traditional approach to constructing optimal alignments. Improved performance has recently been achieved using A*. However, the multiple alignment problem presents a difficulty for the classic A* algorithm. Its branching factor of 2 d − 1 is so large that the size of the open list dramatically exceeds the number of nodes A* must expand to find an optimal solution. Two solutions to this problem have been proposed in the literature. Yoshizumi et al. (2000) describe an extension of A*, called A* with Partial Expansion (PEA*). Instead of generating all successors of a node when it is expanded, PEA* inserts only the most promising successors into the open list. The “partially expanded” node is re-inserted into the open list with a revised f-cost equal to the least f-cost