Multiple Sequence Alignment Using Anytime A

Alignment of multiple DNA or protein sequences is a cen-tral problem in computational biology. To create an align-ment, 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 differ-ent 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 formal-ized as a shortest-path problem through a d-dimensional lat-tice, where d is the number of sequences to be aligned (Gus-field 1997). Dynamic programming is the traditional ap-proach to constructing optimal alignments. Improved per