Eddy S R
Dept. of Genetics, Washington University School of Medicine, St. Louis, MO 63110, USA.
Proc Int Conf Intell Syst Mol Biol. 1995;3:114-20.
A simulated annealing method is described for training hidden Markov models and producing multiple sequence alignments from initially unaligned protein or DNA sequences. Simulated annealing in turn uses a dynamic programming algorithm for correctly sampling suboptimal multiple alignments according to their probability and a Boltzmann temperature factor. The quality of simulated annealing alignments is evaluated on structural alignments of ten different protein families, and compared to the performance of other HMM training methods and the ClustalW program. Simulated annealing is better able to find near-global optima in the multiple alignment probability landscape than the other tested HMM training methods. Neither ClustalW nor simulated annealing produce consistently better alignments compared to each other. Examination of the specific cases in which ClustalW outperforms simulated annealing, and vice versa, provides insight into the strengths and weaknesses of current hidden Markov model approaches.
本文描述了一种模拟退火方法，用于训练隐马尔可夫模型，并从最初未对齐的蛋白质或DNA序列生成多序列比对。模拟退火反过来使用动态规划算法，根据次优多序列比对的概率和玻尔兹曼温度因子对其进行正确采样。在十个不同蛋白质家族的结构比对上评估模拟退火比对的质量，并与其他隐马尔可夫模型训练方法和ClustalW程序的性能进行比较。与其他测试的隐马尔可夫模型训练方法相比，模拟退火在多序列比对概率景观中更能找到接近全局最优解。与彼此相比，ClustalW和模拟退火都不能始终产生更好的比对。对ClustalW优于模拟退火以及反之亦然的具体情况进行研究，有助于深入了解当前隐马尔可夫模型方法的优缺点。
