The Brain Storm Dynamic Technique DBSO-MSA for Efficiently Resolving Multiple Sequence Alignment
DOI:
https://doi.org/10.13052/jmm1550-4646.18411Keywords:
Multiple sequence alignment, Brain storm optimization algorithm, Dynamic population, dynamic cluster size.Abstract
Multiple Sequence Alignment (MSA) is a critical step in molecular biology. Different techniques are having been proposed for obtaining optimal alignments, still, there is a need of developing accurate and efficient techniques for optimal sequence alignment. One of the efficient techniques among the swarm optimization families is Brain Storm Optimization Technique based on human social behavior has achieved success in numerous applications. However, population divergence plays a major role in obtaining better solutions for optimization problems. Therefore, high diverged populations obtain optimal results. The multiple sequences alignment is an efficient optimization for dataset analysis but hidden samples do not get tracked by MSA. Therefore DBSO_MSA model requirement is there to crossover limitations of the above model. This paper proposed a dynamic clustered and populated Brain Storm Optimization Algorithm for obtaining more optimal alignment solutions for the Multiple Sequence Alignment problem (DBSO-MSA). The dynamic nature with respect to the number of clusters and population generation at every iteration is incorporated into BSO. The number of solutions and cluster size at each iteration is controlled by the probability variable either it increases or decreases the solution space to explore more diversification in obtaining alignments for the MSA problem. The experiments show DBSO-MSA effectively improves the alignment score on the benchmark sequence datasets compared to the Classical BSO and other evolutionary algorithms.
Downloads
References
J. Pei, “Multiple protein sequence alignment,” Curr. Opin. Struct. Biol., vol. 18, no. 3, pp. 382–386, 2008, doi: 10.1016/j.sbi.2008.03.007.
M. Kayed and A. A. Elngar, “NestMSA: a new multiple sequence alignment algorithm,” J. Supercomput., vol. 76, no. 11, pp. 9168–9188, 2020, doi: 10.1007/s11227-020-03206-0.
L. Wang and T. Jiang, “On the Complexity of Multiple Sequence Alignment,” J. Comput. Biol., vol. 1, no. 4, pp. 337–348, 1994, doi: 10.1089/cmb.1994.1.337.
J. C. Gelly, A. P. Joseph, N. Srinivasan, and A. G. De Brevern, “IPBA: A tool for protein structure comparison using sequence alignment strategies,” Nucleic Acids Res., vol. 39, no. SUPPL. 2, pp. 18–23, 2011, doi: 10.1093/nar/gkr333.
S. Hicks, D. A. Wheeler, S. E. Plon, and M. Kimmel, “Prediction of missense mutation functionality depends on both the algorithm and sequence alignment employed,” Hum. Mutat., vol. 32, no. 6, pp. 661–668, 2011, doi: 10.1002/humu.21490.
D. A. Morrison, “Multiple Sequence Alignment is not a Solved Problem,” 2018, [Online]. Available: http://arxiv.org/abs/1808.07717.
S. B. Needleman and C. D. Wunsch, “A general method applicable to the search for similarities in the amino acid sequence of two proteins,” J. Mol. Biol., vol. 48, no. 3, pp. 443–453, Mar. 1970, doi: 10.1016/0022-2836(70)90057-4.
T. F. Smith and M. S. Waterman, “Identification of common molecular subsequences,” J. Mol. Biol., vol. 147, no. 1, pp. 195–197, Mar. 1981, doi: 10.1016/0022-2836(81)90087-5.
D.-F. Feng and R. F. Doolittle, “Progressive sequence alignment as a prerequisitetto correct phylogenetic trees,” J. Mol. Evol., vol. 25, no. 4, pp. 351–360, Aug. 1987, doi: 10.1007/BF02603120.
R. Chenna et al., “Multiple sequence alignment with the Clustal series of programs,” Nucleic Acids Res., vol. 31, no. 13, pp. 3497–3500, 2003, doi: 10.1093/nar/gkg500.
K. Katoh and D. M. Standley, “MAFFT multiple sequence alignment software version 7: Improvements in performance and usability,” Mol. Biol. Evol., vol. 30, no. 4, pp. 772–780, 2013, doi: 10.1093/molbev/mst010.
T. Lassmann and E. L. L. Sonnhammer, “Kalign - An accurate and fast multiple sequence alignment algorithm,” BMC Bioinformatics, vol. 6, pp. 1–9, 2005, doi: 10.1186/1471-2105-6-298.
J. Kim, S. Pramanik, and M. J. Chung, “Multiple sequence alignment using simulated annealing,” Bioinformatics, vol. 10, no. 4, pp. 419–426, 1994, doi: 10.1093/bioinformatics/10.4.419.
C. Gondro and B. P. Kinghorn, “A simple genetic algorithm for multiple sequence alignment.,” Genet. Mol. Res., vol. 6, no. 4, pp. 964–82, Oct. 2007, [Online]. Available: https://pubmed.ncbi.nlm.nih.gov/18058716/.
R. C. Addawe, J. M. Addawe, M. R. K. Sueno, and J. C. Magadia, “Differential evolution-simulated annealing for multiple sequence alignment,” J. Phys. Conf. Ser., vol. 893, no. 1, 2017, doi: 10.1088/1742-6596/893/1/012061.
S. Lalwani, R. Kumar, and N. Gupta, “Efficient two-level swarm intelligence approach for multiple sequence alignment,” Comput. Informatics, vol. 35, no. 4, pp. 963–985, 2016.
Y. Shi, “Brain storm optimization algorithm,” Lect. Notes Comput. Sci. (including Subser. Lect. Notes Artif. Intell. Lect. Notes Bioinformatics), vol. 6728 LNCS, no. PART 1, pp. 303–309, 2011, doi: 10.1007/978-3-642-21515-5_36.
S. Cheng, Q. Qin, J. Chen, and Y. Shi, “Brain storm optimization algorithm: a review,” Artif. Intell. Rev., vol. 46, no. 4, pp. 445–458, 2016, doi: 10.1007/s10462-016-9471-0.
Y. Yang, Y. Shi, and S. Xia, “Advanced discussion mechanism-based brain storm optimization algorithm,” Soft Comput., vol. 19, no. 10, pp. 2997–3007, 2015, doi: 10.1007/s00500-014-1463-x.
A. Cervantes-Castillo and E. Mezura-Montes, “A modified brain storm optimization algorithm with a special operator to solve constrained optimization problems,” Appl. Intell., vol. 50, no. 12, pp. 4145–4161, 2020, doi: 10.1007/s10489-020-01763-8.
Y. Yu, S. Gao, Y. Wang, Z. Lei, J. Cheng, and Y. Todo, “A Multiple Diversity-Driven Brain Storm Optimization Algorithm with Adaptive Parameters,” IEEE Access, vol. 7, pp. 126871–126888, 2019, doi: 10.1109/ACCESS.2019.2939353.
J. Liu, H. Peng, Z. Wu, J. Chen, and C. Deng, “Multi-strategy brain storm optimization algorithm with dynamic parameters adjustment,” Appl. Intell., vol. 50, no. 4, pp. 1289–1315, 2020, doi: 10.1007/s10489-019-01600-7.
S. Cheng, Y. Shi, Q. Qin, Q. Zhang, and R. Bai, “Population Diversity Maintenance In Brain Storm Optimization Algorithm,” J. Artif. Intell. Soft Comput. Res., vol. 4, no. 2, pp. 83–97, 2014, doi: 10.1515/jaiscr-2015-0001.
P. Jeevana Jyothi, K. P. K, S. M. Raiyyan, and T. Rajasekhar, “MSA: An Application of Brain Storm Optimization Algorithm,” SSRN Electron. J., 2020, doi: 10.2139/ssrn.3646174.
J. Teo, “Exploring dynamic self-adaptive populations in differential evolution,” Soft Comput., vol. 10, no. 8, pp. 673–686, 2006, doi: 10.1007/s00500-005-0537-1.
H. Wang, S. Rahnamayan, and Z. Wu, “Adaptive Differential Evolution with variable population size for solving high-dimensional problems,” 2011 IEEE Congr. Evol. Comput. CEC 2011, pp. 2626–2632, 2011, doi: 10.1109/CEC.2011.5949946.
K. Chellapilla and G. B. Fogel, “Multiple sequence alignment using evolutionary programming,” Proc. 1999 Congr. Evol. Comput. CEC 1999, vol. 1, no. February 1999, pp. 445–452, 1999, doi: 10.1109/CEC.1999.781958.
J. D. Thompson, F. Plewniak, and O. Poch, “A comprehensive comparison of multiple sequence alignment programs,” Nucleic Acids Res., vol. 27, no. 13, pp. 2682–2690, 1999, doi: 10.1093/nar/27.13.2682.
G. P. S. Raghava, S. M. J. Searle, P. C. Audley, J. D. Barber, and G. J. Barton, “OXBench: A benchmark for evaluation of protein multiple sequence alignment accuracy,” BMC Bioinformatics, vol. 4, pp. 1–23, 2003, doi: 10.1186/1471-2105-4-47.
