Improved Hidden Markov Model training for multiple sequence alignment by a particle swarm optimization-evolutionary algorithm hybrid.
Multiple sequence alignment (MSA) is one of the basic problems in computational biology. Realistic problem instances of MSA are computationally intractable for exact algorithms. One way to tackle MSA is to use Hidden Markov Models (HMMs), which are known to be very powerful in the related problem domain of speech recognition. However, the training of HMMs is computationally hard and there is no known exact method that can guarantee optimal training within reasonable computing time. Perhaps the most powerful training method is the Baum-Welch algorithm, which is fast, but bears the problem of stagnation at local optima. In the study reported in this paper, we used a hybrid algorithm combining particle swarm optimization with evolutionary algorithms to train HMMs for the alignment of protein sequences. Our experiments show that our approach yields better alignments for a set of benchmark protein sequences than the most commonly applied HMM training methods, such as Baum-Welch and Simulated Annealing.
Rasmussen
Thomas Kiel
TK
EVALife Group, Department of Computer Science, University of Aarhus, Ny Munkegade B540, DK-8000 C Aarhus, Denmark. kiel@daimi.au.dk
Krink
Thiemo
T
D000465:Algorithms; D001185:Artificial Intelligence; D045304:Cytochromes c / Q000737:chemistry / Q000235:genetics; D020869:Gene Expression Profiling / Q000379:methods*; D005914:Globins / Q000737:chemistry / Q000235:genetics; D007328:Insulin / Q000737:chemistry / Q000235:genetics; D008390:Markov Chains; D011506:Proteins / Q000737:chemistry* / Q000235:genetics*; D015203:Reproducibility of Results; D012680:Sensitivity and Specificity; D016415:Sequence Alignment / Q000379:methods*; D017422:Sequence Analysis, DNA / Q000379:methods*; D020539:Sequence Analysis, Protein / Q000379:methods*; D017386:Sequence Homology, Amino Acid
D007328:Insulin; D011506:Proteins; D005914:Globins; D045304:Cytochromes c