Multiple sequence alignment using the hidden Markov model trained by an improved quantum-behaved particle swarm optimization. (English) Zbl 1250.68239
Summary: Multiple sequence alignment (MSA) is an NP-complete and important problem in bioinformatics. For MSA, Hidden Markov Models (HMMs) are known to be powerful tools. However, the training of HMMs is computationally hard so that metaheuristic methods such as simulated annealing (SA), evolutionary algorithms (EAs) and particle swarm optimization (PSO), have been employed to tackle the training problem. In this paper, quantum-behaved particle swarm optimization (QPSO), a variant of PSO, is analyzed mathematically firstly, and then an improved version is proposed to train the HMMs for MSA. The proposed method, called diversity-maintained QPSO (DMQPO), is based on the analysis of QPSO and integrates a diversity control strategy into QPSO to enhance the global search ability of the particle swarm. To evaluate the performance of the proposed method, we use DMQPSO, QPSO and other algorithms to train the HMMs for MSA on three benchmark datasets. The experiment results show that the HMMs trained with DMQPSO and QPSO yield better alignments for the benchmark datasets than other most commonly used HMM training methods such as Baum-Welch and PSO.
MSC:
| 68T20 | Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) |
| 68Q12 | Quantum algorithms and complexity in the theory of computing |
| 92C40 | Biochemistry, molecular biology |
Keywords:
multiple sequence alignment; hidden Markov model; parameter optimization; quantum-behaved particle swarm optimization; population diversityReferences:
| [1] | Angeline, P. J., Evolutionary optimization versus particle swarm optimization: philosophy and performance differences, Evolutionary Programming VII, Lecture Notes in Computer Science, 1447, 601-610 (1998) |
| [2] | Araújo, R.deA., Swarm-based translation-invariant morphological prediction method for financial time series forecasting, Information Sciences, 180, 4784-4805 (2010) · Zbl 1237.91241 |
| [3] | P. Baldi, Y. Chauvin, T. Hunkapiller, M.A. McClure, Hidden Markov Models of biological primary sequence information, in: Proceedings of National Academy of Sciences USA, vol. 91, 1994, pp. 1059-1063.; P. Baldi, Y. Chauvin, T. Hunkapiller, M.A. McClure, Hidden Markov Models of biological primary sequence information, in: Proceedings of National Academy of Sciences USA, vol. 91, 1994, pp. 1059-1063. |
| [4] | Baum, L. E.; Petrie, T.; Soules, G.; Weiss, N., A maximization technique occurring in the statistical analysis of probabilistic functions of Markov chains, Annals of Mathematical Statistics, 41, 164-171 (1970) · Zbl 0188.49603 |
| [5] | Cai, Y.; Sun, J.; Wang, J.; Ding, Y.; Tian, N.; Liao, X.; Xu, W., Optimizing the codon usage of synthetic gene with QPSO algorithm, Journal of Theoretical Biology, 254, 123-127 (2008) · Zbl 1400.92180 |
| [6] | W. Chen, J. Sun, Y. Ding, W. Fang, W. Xu, Clustering of gene expression data with quantum-behaved particle swarm optimization, in: Proceedings of the Twenty First International Conference on Industrial, Engineering and Other Applications of Applied Intelligent Systems (IEA/AIE 2008), 2008, pp. 388-396.; W. Chen, J. Sun, Y. Ding, W. Fang, W. Xu, Clustering of gene expression data with quantum-behaved particle swarm optimization, in: Proceedings of the Twenty First International Conference on Industrial, Engineering and Other Applications of Applied Intelligent Systems (IEA/AIE 2008), 2008, pp. 388-396. |
| [7] | K. Chellapilla, G.B. Fogel, Multiple sequence alignmentusing evolutionary programming, in: Proceedings of the First Congress on Evolution Composition, 1999, pp. 445-452.; K. Chellapilla, G.B. Fogel, Multiple sequence alignmentusing evolutionary programming, in: Proceedings of the First Congress on Evolution Composition, 1999, pp. 445-452. |
| [8] | Chica, M.; Cordón, Ó.; Damas, S.; Bautista, J., Multiobjective constructive heuristics for the 1/3 variant of the time and space assembly line balancing problem: ACO and random greedy search, Information Sciences, 180, 3465-3487 (2010) |
| [9] | M. Clerc, The swarm and the queen: towards a deterministic and adaptive particle swarm optimization, in: Proceedings of 1999 Congress on Evolutionary Computation, 1999, pp. 1951-1957.; M. Clerc, The swarm and the queen: towards a deterministic and adaptive particle swarm optimization, in: Proceedings of 1999 Congress on Evolutionary Computation, 1999, pp. 1951-1957. |
| [10] | Clerc, M.; Kennedy, J., The particle swarm-explosion, stability and convergence in a multidimensional complex space, IEEE Transactions on Evolutionary Computation, 6, 58-73 (2002) |
| [11] | Coelho, L. S.; Alotto, P., Global optimization of electromagnetic devices using an exponential quantum-behaved particle swarm optimizer, IEEE Transactions on Magenetics, 44, 1074-1077 (2008) |
| [12] | Coelho, L. S., A quantum particle swarm optimizer with chaotic mutation operator, Chaos, Solitons & Fractals, 37, 1409-1418 (2008) |
| [13] | Du, W.; Li, B., Multi-strategy ensemble particle swarm optimization for dynamic optimization, Information Sciences, 178, 3096-3109 (2008) · Zbl 1283.90047 |
| [14] | S.R. Eddy, Multiple alignment using Hidden Markov Models, in: Proceedings of the International Conference on Intelligent Systems for Molecular Biology, 1995, pp. 114-120.; S.R. Eddy, Multiple alignment using Hidden Markov Models, in: Proceedings of the International Conference on Intelligent Systems for Molecular Biology, 1995, pp. 114-120. |
| [15] | Ellabib, I.; Calamai, P.; Basir, O., Exchange strategies for multiple ant colony system, Information Sciences, 177, 1248-1264 (2007) |
| [16] | Elhossini, A.; Areibi, S.; Dony, R., Strength pareto particle swarm optimization and hybrid EA-PSO for multi-objective optimization, Evolutionary Computation, 18, 127-156 (2010) |
| [17] | Feng, D. F.; Doolittle, R. F., Progressive sequence alignment as a prerequisite to correct phylogenetic trees, Journal of Molecular Evolution, 25, 351-360 (1987) |
| [18] | Gao, F., Parameters estimation on-line for Lorenz system by a novel quantum-behaved particle swarm optimization, Chinese Physics B, 17, 1196-1201 (2008) |
| [19] | Gao, H.; Xu, W.; Sun, J.; Tang, Y., Multilevel thresholding for image segmentation through an improved quantum-behaved particle swarm algorithm, IEEE Transactions on Instrumentation and Measurement, 59, 934-946 (2010) |
| [20] | S. Henikoff, J.G. Henikoff, Amino acid substitution matrices from protein blocks, in: Proceedings of National Academy of Sciences USA, vol. 89, 1992, pp. 10915-10919.; S. Henikoff, J.G. Henikoff, Amino acid substitution matrices from protein blocks, in: Proceedings of National Academy of Sciences USA, vol. 89, 1992, pp. 10915-10919. |
| [21] | Z. Huang, Y.J. Wang, C.J. Yang, C.Z. Wu, A new improved quantum-behaved particle swarm optimization model, in: Proceedings of the 5th IEEE Conference on Industrial Electronics and Applications, 2009, pp. 1560-1564.; Z. Huang, Y.J. Wang, C.J. Yang, C.Z. Wu, A new improved quantum-behaved particle swarm optimization model, in: Proceedings of the 5th IEEE Conference on Industrial Electronics and Applications, 2009, pp. 1560-1564. |
| [22] | Janson, S.; Middendorf, M., A hierarchical particle swarm optimizer and its adaptive variant, IEEE Transactions on Systems, Man and Cybernetics, Part B: Cybernetics, 6, 1272-1282 (2005) |
| [23] | Karplus, K.; Barrett, C.; Hughey, R., Hidden Markov Models for detecting remote protein homologies, Bioinformatics, 14, 846-856 (1998) |
| [24] | J. Kennedy, R.C. Eberhart, Particle swarm optimization, in: Proceedings of IEEE International Conference on Neural Networks, 1995, pp. 1942-1948.; J. Kennedy, R.C. Eberhart, Particle swarm optimization, in: Proceedings of IEEE International Conference on Neural Networks, 1995, pp. 1942-1948. |
| [25] | J. Kennedy, Bare bones particle swarms, in: Proceedings of IEEE Swarm Intelligence Symposium, Indianapolis, IN, 2003, pp. 80-87.; J. Kennedy, Bare bones particle swarms, in: Proceedings of IEEE Swarm Intelligence Symposium, Indianapolis, IN, 2003, pp. 80-87. |
| [26] | Kim, J.; Pramanik, S.; Chung, M. J., Multiple sequence alignment using simulated annealing, Bioinformatics, 10, 419-426 (1994) |
| [27] | Krogh, A.; Brown, M.; Mian, I. S.; Sjolander, K.; Haussler, D., Hidden Markov Models in computational biology: applications to protein modeling, Journal of Molecular Biology, 235, 1501-1531 (1994) |
| [28] | Kwong, S.; Chau, C.; Man, K.; Tang, K., Optimisation of HMM topology and its model parameters by genetic algorithm, Pattern Recognition, 34, 509-522 (2001) · Zbl 0991.68070 |
| [29] | Lee, Z.-J.; Su, S.-F.; Chuang, C.-C.; Liu, K.-H., Genetic algorithm with ant colony optimization (GA-ACO) for multiple sequence alignment, Applied Soft Computing, 8, 55-78 (2008) |
| [30] | X.J. Lei, A.L. Fu, Two-dimensional maximum entropy image segmentation method based on quantum-behaved particle swarm optimization algorithm, in: Proceedings of Fourth International Conference on Nature Computation, 2008, pp. 692-696.; X.J. Lei, A.L. Fu, Two-dimensional maximum entropy image segmentation method based on quantum-behaved particle swarm optimization algorithm, in: Proceedings of Fourth International Conference on Nature Computation, 2008, pp. 692-696. |
| [31] | Li, S.-Y.; Wang, R.-G.; Hu, W.-W.; Sun, J.-Q., A new QPSO based BP neural network for face detection, Advances in Soft Computing, Fuzzy Information and Engineering, vol. 40 (2007), Springer |
| [32] | Li, X., Niching without niching parameters: particle swarm optimization using a ring topology, IEEE Transactions on Evolutionary Computation, 14, 150-169 (2010) |
| [33] | J. Liu, W.B. Xu, J. Sun, Quantum-behaved particle swarm optimization with mutation operator, in: Proceedings of the 17th IEEE International Conference on Tools with Artificial Intelligence, 2005, pp. 237-240.; J. Liu, W.B. Xu, J. Sun, Quantum-behaved particle swarm optimization with mutation operator, in: Proceedings of the 17th IEEE International Conference on Tools with Artificial Intelligence, 2005, pp. 237-240. |
| [34] | Lukashin, A. V.; Engelbrecht, J.; Brunak, S., Multiple alignment using simulated annealing: branch point definition in human mRNA splicing, Nucleic Acids Research, 20, 2511-2516 (1992) |
| [35] | Mikki, S. M.; Kishk, A. A., Quantum particle swarm optimization for electromagnetics, IEEE Transactions on Antennas and Propagation, 54, 2764-2775 (2006) |
| [36] | Mongillo, G.; Deneve, S., Online learning with Hidden Markov Models, Neural Computation, 20, 1706-1716 (2008) · Zbl 1147.68646 |
| [37] | Montes de Oca, M. A.; Stutzle, T.; Birattari, M.; Dorigo, M., Frankenstein’s PSO: a composite particle swarm optimization algorithm, IEEE Transactions on Evolutionary Computation, 13, 1120-1132 (2009) |
| [38] | Mount, D. W., Bioinformatics: Sequence and Genome Analysis (2001), Cold Spring Harbor Laboratory Press |
| [39] | Notredame, C.; Higgins, D. G., SAGA: sequence alignment by genetic algorithm, Nucleic Acids Research, 24, 1515-1524 (1996) |
| [40] | Omkara, S. N.; Khandelwala, R.; Ananthb, T. V.S.; Naika, G. N.; Gopalakrishnana, S., Quantum behaved particle swarm optimization (QPSO) for multi-objective design optimization of composite structures, Expert Systems with Applications, 36, 11312-11322 (2009) |
| [41] | M. Pant, R. Thangaraj, A. Abraham, A new quantum behaved particle swarm optimization, in: Proceedings of the 10th Annual Conference on Genetic and Evolutionary Computation, 2008, pp. 87-94.; M. Pant, R. Thangaraj, A. Abraham, A new quantum behaved particle swarm optimization, in: Proceedings of the 10th Annual Conference on Genetic and Evolutionary Computation, 2008, pp. 87-94. |
| [42] | Pant, M.; Thangaraj, R.; SinghSobol, V. P., Sobal mutated quantum particle swarm optimization, International Journal of Recent Trends in Engineering, 1, 95-99 (2009) |
| [43] | Poli, R., Mean and variance of the sampling distribution of particle swarm optimizers during stagnation, IEEE Transactions on Evolutionary Computation, 13, 712-721 (2009) |
| [44] | Parrott, D.; Li, X., Locating and tracking multiple dynamic optima by a particle swarm model using speciation, IEEE Transactions on Evolutionary Computation, 10, 440-458 (2006) |
| [45] | L.R. Rabiner, A tutorial on Hidden Markov Models and selected applications in speech recognition, in: Proceedings of the IEEE, 1989, pp. 257-285.; L.R. Rabiner, A tutorial on Hidden Markov Models and selected applications in speech recognition, in: Proceedings of the IEEE, 1989, pp. 257-285. |
| [46] | Rasmussen, T. K.; Krink, T., Improved Hidden Markov Model training for multiple sequence alignment by a particle swarm optimization-evolutionary algorithm hybrid, BioSystems, 72, 5-17 (2003) |
| [47] | J. Riget, J.S. Vesterstrøm, A Diversity-Guided Particle Swarm Optimizer - The ARPSO, Technical Report, University of Aarhus, Denmark, 2002.; J. Riget, J.S. Vesterstrøm, A Diversity-Guided Particle Swarm Optimizer - The ARPSO, Technical Report, University of Aarhus, Denmark, 2002. |
| [48] | Sabata, S. L.; Coelho, L. S.; Abrahamc, A., MESFET DC model parameter extraction using quantum particle swarm optimization, Microelectronics Reliability, 49, 660-666 (2009) |
| [49] | Sonnhammer, E. L.; Eddy, S. R.; Durbin, R., Pfam: a comprehensive database of protein families based on seed alignments, Proteins, 28, 405-420 (1997) |
| [50] | Y. Shi, R.C. Eberhart, A modified particle swarm optimizer, in: Proceedings of IEEE International Conference on Evolutionary Computation, 1998, pp. 69-73.; Y. Shi, R.C. Eberhart, A modified particle swarm optimizer, in: Proceedings of IEEE International Conference on Evolutionary Computation, 1998, pp. 69-73. |
| [51] | Slimane, M.; Venturini, G.; de Beauville, J. A.; Brouard, T.; Brandeau, A., Optimizing Hidden Markov Models with a genetic algorithm, Lecture Notes in Computer Science, 1063, 384-396 (1996) |
| [52] | Stoye, J.; Evers, D.; Meyer, F., Rose: generating sequence families, Bioinformatics, 14, 157-163 (1998) |
| [53] | J. Sun, B. Feng, W.B. Xu, Particle swarm optimization with particles having quantum behavior, in: Proceedings of Congress on Evolutionary Computation, Portland, USA, June 2004, pp. 326-331.; J. Sun, B. Feng, W.B. Xu, Particle swarm optimization with particles having quantum behavior, in: Proceedings of Congress on Evolutionary Computation, Portland, USA, June 2004, pp. 326-331. |
| [54] | J. Sun, W.B. Xu, B. Feng, A global search strategy of quantum-behaved particle swarm optimization, in: Proceedings of IEEE Conference on Cybernetics and Intelligent Systems, Singapore, December 2004, pp. 111-116.; J. Sun, W.B. Xu, B. Feng, A global search strategy of quantum-behaved particle swarm optimization, in: Proceedings of IEEE Conference on Cybernetics and Intelligent Systems, Singapore, December 2004, pp. 111-116. |
| [55] | J. Sun, W.B. Xu, B. Feng, AddTaptive parameter control for quantum-behaved particle swarm optimization on individual level, in: Proceedings of IEEE International Conference on Systems, Man and Cybernetics, Hawaii, October 2005, vol. 4, pp. 3049-3054.; J. Sun, W.B. Xu, B. Feng, AddTaptive parameter control for quantum-behaved particle swarm optimization on individual level, in: Proceedings of IEEE International Conference on Systems, Man and Cybernetics, Hawaii, October 2005, vol. 4, pp. 3049-3054. |
| [56] | J. Sun, W.B. Xu, B. Ye, Quantum-behaved particle swarm optimization clustering algorithm, in: Proceedings of the International Conference on Advanced Data Mining and Applications, 2006, pp. 340-347.; J. Sun, W.B. Xu, B. Ye, Quantum-behaved particle swarm optimization clustering algorithm, in: Proceedings of the International Conference on Advanced Data Mining and Applications, 2006, pp. 340-347. |
| [57] | Sun, J.; Liu, J.; Xu, W. B., Using quantum-behaved particle swarm optimization algorithm to solve non-linear programming problems, International Journal of Computer Mathematics, 84, 261-272 (2007) · Zbl 1116.65072 |
| [58] | Sun, J.; Fang, W.; Wang, D.; Xu, W., Solving the economic dispatch problem with a modified quantum-behaved particle swarm optimization method, Energy Conversion and Management, 50, 2967-2975 (2009) |
| [59] | J. Sun, W. Fang, Z. Xie, C.-H. Lai, W. Xu, Particle swarm optimization with particles having quantum behavior: convergence analysis and performance evaluation, submitted for publication.; J. Sun, W. Fang, Z. Xie, C.-H. Lai, W. Xu, Particle swarm optimization with particles having quantum behavior: convergence analysis and performance evaluation, submitted for publication. |
| [60] | Thompson, J. D.; Higgins, D. G.; Gibson, T. J., CLUSTALW: improving the sensitivity of progressive multiple sequence alignment through sequence weighting, position-specific gap penalties and weight matrix choice, Nucleotide Acids Research, 22, 4673-4680 (1994) |
| [61] | Thompson, J.; Plewniak, F.; Poch, O., A comprehensive comparison of multiple sequence alignment programs, Nucleotide Acids Research, 27, 2682-2690 (1999) |
| [62] | R. Thomsen, Evolving the topology of Hidden Markov Models using evolutionary algorithms, in: Proceedings of Parallel Problem Solving from Nature VII (PPSN), 2002, pp. 861-870.; R. Thomsen, Evolving the topology of Hidden Markov Models using evolutionary algorithms, in: Proceedings of Parallel Problem Solving from Nature VII (PPSN), 2002, pp. 861-870. |
| [63] | Tripathi, P. K.; Bandyopadhyay, S.; Pal, S. K., Multi-objective particle swarm optimization with time variant inertia and acceleration coefficients, Information Sciences, 177, 5033-5049 (2007) · Zbl 1121.90130 |
| [64] | Twomey, C.; Stützle, T.; Dorigo, M.; Manfrin, M.; Birattari, M., An analysis of communication policies for homogeneous multi-colony ACO algorithms, Information Sciences, 180, 2390-2404 (2010) |
| [65] | R.K. Ursem, Diversity-Guided evolutionary algorithms, in: Proceedings of the Parallel Problem Solving from Nature Conference, 2002, pp. 462-471.; R.K. Ursem, Diversity-Guided evolutionary algorithms, in: Proceedings of the Parallel Problem Solving from Nature Conference, 2002, pp. 462-471. |
| [66] | Wang, L.; Jiang, T., On the complexity of multiple sequence alignment, Journal of Computational Biology, 1, 337-348 (1994) |
| [67] | J. Wang, Y. Zhou, Quantum-behaved particle swarm optimization with generalized local search operator for global optimization, in: Proceedings of International Conference on Intelligent Computing, 2007, pp. 344-352.; J. Wang, Y. Zhou, Quantum-behaved particle swarm optimization with generalized local search operator for global optimization, in: Proceedings of International Conference on Intelligent Computing, 2007, pp. 344-352. |
| [68] | Wang, Y.; Yang, Y., Particle swarm optimization with preference order ranking for multi-objective optimization, Information Sciences, 179, 1944-1959 (2009) |
| [69] | Wu, Q.; Law, R., Complex system fault diagnosis based on a fuzzy robust wavelet support vector classifier and an adaptive Gaussian particle swarm optimization, Information Sciences, 180, 4514-4528 (2010) · Zbl 1207.68254 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
