Toward efficient multiple molecular sequence alignment: a system of genetic algorithm and dynamic programming
- 1 December 1997
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics)
- Vol. 27 (6) , 918-932
- https://doi.org/10.1109/3477.650054
Abstract
Multiple biomolecular sequence alignment is among the most important and challenging tasks in computational biology. It is characterized by great complexity in processing time. In this paper, a multiple-sequence alignment system is reported which combines the techniques of genetic algorithms and pairwise dynamic programming. Genetic algorithms are stochastic approaches for efficient and robust search. By converting biomolecular sequence alignment into a problem of searching for an optimal or a near-optimal point in a solution space, a genetic algorithm is used to find match blocks very efficiently. A pairwise dynamic programming is then applied to the subsequences between the match blocks. Combining the strengths of the two methods, the system achieves high efficiency and high alignment quality. In this paper, the system is described in detail. The system's performance is analyzed and the experimental results are presented.Keywords
This publication has 29 references indexed in Scilit:
- An improved algorithm for matching biological sequencesPublished by Elsevier ,2004
- Schema survival rates and heuristic search in genetic algorithmsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Using genetic algorithms for supervised concept learningPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- CLUSTAL W: improving the sensitivity of progressive multiple sequence alignment through sequence weighting, position-specific gap penalties and weight matrix choiceNucleic Acids Research, 1994
- Genetic Algorithms for Protein Folding SimulationsJournal of Molecular Biology, 1993
- MULTICOMP: a program package for multiple sequence comparisonBioinformatics, 1992
- Motif recognition and alignment for many sequences by comparison of dot-matricesJournal of Molecular Biology, 1991
- Multiple sequence alignment by consensusNucleic Acids Research, 1986
- General methods of sequence comparisonBulletin of Mathematical Biology, 1984
- A strategy for sequence phylogeny researchNucleic Acids Research, 1982