MULTIPLE SEQUENCE ALIGNMENT USING SIMULATED ANNEALING

Multiple sequence alignment is a useful technique for studying molecul ar evolution and analyzing structure-sequence relationships. Dynamic p rogramming of multiple sequence alignment has been widely used to find an optimal alignment. However, dynamic programming does not allow for certain types of gap costs, and it limits the number of sequences tha t can be aligned due to its high computational complexity. The focus o f this paper is to use simulated annealing as the basis for developing an efficient multiple sequence alignment algorithm. An algorithm call ed Multiple Sequence Alignment using Simulated Annealing (MSASA) has b een developed. The computational complexity of MSASA is significantly reduced by replacing the high-temperature phase of the annealing proce ss by a fast heuristic algorithm. This heuristic algorithm facilitates in minimizing the solution set of the low-temperature phase of the an nealing process. Compared to the dynamic programming approach, MSASA c an (i) use natural gap costs which can generate better solution, (ii) align more sequences and (iii) take less computation time.