Ishikawa M, Toya T, Hoshida M, Nitta K, Ogiwara A, Kanehisa M
Institute for New Generation Computer Technology (ICOT), Tokyo, Japan.
Comput Appl Biosci. 1993 Jun;9(3):267-73. doi: 10.1093/bioinformatics/9.3.267.
We have developed simulated annealing algorithms to solve the problem of multiple sequence alignment. The algorithm was 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-way dynamic programming. Every annealing algorithm produced a better energy value than the conventional algorithm. The best energy value, which probably represents the optimal solution, was 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 useful for refining multiple alignments obtained by other heuristic methods.
我们开发了模拟退火算法来解决多序列比对问题。经用于三序列比对的严格动态规划算法证实，该算法能给出最优解。为克服模拟退火执行时间长的问题，我们使用了并行计算机。在一个问题上测试了顺序算法、简单并行算法和温度并行算法。将结果与通过传统基于树的算法获得的结果进行比较，在传统算法中，比对通过双向动态规划合并。每种退火算法产生的能量值都比传统算法更好。两种并行退火算法都在合理时间内达到了可能代表最优解的最佳能量值。我们认为模拟退火的温度并行算法最适合用于找到最优多序列比对，因为该算法不需要任何优化调度。该算法对于优化通过其他启发式方法获得的多序列比对也很有用。
