Multiple sequence alignment by parallel simulated annealing

Publisher Website
Google Scholar
Abstract
We have developed simulated annealing algorithms to solve the problem of multiple sequence alignment. The algorithm wns shown to give the optimal solution as confirmed by the rigorous dynamic programming algorithm for three-sequence alignment. To overcome long execution times for simulated annealing, we utilized a parallel computer. A sequential algorithm, a simple parallel algorithm and the temperature parallel algorithm were tested on a problem. The results were compared with the result obtained by a conventional tree-based algorithm where alignments were merged by two-' dynamic programming. Every annealing algorithm produced a better energy value than the conventional algorithm. The best energy value, which probably represents the optimal solution, wns reached within a reasonable time by both of the parallel annealing algorithms. We consider the temperature parallel algorithm of simulated annealing to be the most suitable for finding the optimal multiple sequence alignment because the algorithm does not require any scheduling for optimization. The algorithm is also usefiui for refining multiple alignments obtained by other hewistic methods.

This publication has 0 references indexed in Scilit: