An Efficient Method for Multiple Sequence Alignment

Multiple sequence alignment has been a use-ful method in the study of molecular evolution and sequence-structure relationships. This pa-per presents a new method for multiple sequence alignment based on simulated annealing tech-nique. Dynamic programming has been widely used to find an optimal alignment. However, dynamic programming has several limitations to obtain optimal alignment. It. requires long com-putation time and cannot apply certain types of cost functions. We describe detail mechanisms of simulated annealing for multiple sequence align-ment. problem. It is shown that simulated anneal-ing can be an effective approach to overcome the limitations of dynamic programming in multiple sequence alignment problem. Key words, computational complexity, dy-namic programming, multiple sequence align-ment, protein sequence analysis, sequence simi-larity