Multiple sequence alignment using modified dynamic programming and particle swarm optimization
- 1 June 2008
- journal article
- research article
- Published by Informa UK Limited in Journal of the Chinese Institute of Engineers
- Vol. 31 (4), 659-673
- https://doi.org/10.1080/02533839.2008.9671419
Abstract
Dynamic Programming (DP) is widely used in Multiple Sequence Alignment (MSA) problems. However, when the number of the considered sequences is more than two, multiple dimensional DP may suffer from large storage and computational complexities. Often, progressive pairwise DP is employed for MSA. However, such an approach also suffers from local optimum problems. In this paper, we present a hybrid algorithm for MSA. The algorithm combines the pairwise DP and the particle swarm optimization (PSO) techniques to overcome the above drawbacks. In the algorithm, pairwise DP is used to align sequences progressively and PSO is employed to avoid the result of alignment being trapped into local optima. Several existing MSA tools are employed for comparison. The experimental results show excellent performance of the proposed algorithm.Keywords
This publication has 24 references indexed in Scilit:
- MAFFT version 5: improvement in accuracy of multiple sequence alignmentNucleic Acids Research, 2005
- Particle swarm optimization in electromagneticsIEEE Transactions on Antennas and Propagation, 2004
- MUSCLE: multiple sequence alignment with high accuracy and high throughputNucleic Acids Research, 2004
- T-coffee: a novel method for fast and accurate multiple sequence alignment 1 1Edited by J. ThorntonJournal of Molecular Biology, 2000
- Toward efficient multiple molecular sequence alignment: a system of genetic algorithm and dynamic programmingIEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), 1997
- CLUSTAL W: improving the sensitivity of progressive multiple sequence alignment through sequence weighting, position-specific gap penalties and weight matrix choiceNucleic Acids Research, 1994
- An improved algorithm for matching biological sequencesJournal of Molecular Biology, 1982
- Identification of common molecular subsequencesJournal of Molecular Biology, 1981
- A linear space algorithm for computing maximal common subsequencesCommunications of the ACM, 1975
- A general method applicable to the search for similarities in the amino acid sequence of two proteinsJournal of Molecular Biology, 1970