Volume 17 • Issue 2 • PP: 1-10 • 2025
Analysis of Objective Functions for Ribonucleic Acid Multiple Sequence Alignment Fusion Based on Harmony Search Algorithm
View PDF Abstract
Four kinds of smaller molecules known as ribonucleotide bases-adenine (A), cytosine (C), guanine (G), and uracil (U) combine to form the linear molecule known as ribonucleic acid (RNA). Aligning multiple sequences is a fundamental task in bioinformatics. This paper studies the correlation of different objective functions applying to RNA multiple sequence alignment (MSA) fusion generated by the Harmony search-based method. Experiments are performed on the BRAliBase dataset containing different numbers of test groups. The correlation of the alignment score and the quality obtained is compared against coffee, sum-of-pairs (SP), weight sum-of-pairs (WSP), NorMD, and MstatX. The results indicate that COFFEE and SP objective functions achieved a correlation coefficient (R²) of 0.96 and 0.92, respectively, when compared to the reference alignments, demonstrating their effectiveness in producing high-quality alignments. In addition, the sum-of-pairs takes less time than the COFFEE objective function for the same number of iterations on the same RNA benchmark.
Keywords
References
[1] J. A. Doudna, and T. R. Cech, “The Chemical Repertoire of Natural Ribozymes,” Nature, vol. 418, no. 6894, pp. 222-228, 2002.
[2] L. Anbarasu, P. Narayanasamy, and V. Sundararajan, “Multiple molecular sequence alignment by island parallel genetic algorithm,” Current Science, vol. 78, no. 7, pp. 858-863, 2000.
[3] T. Paruchuri, G. R. Kancharla, S. Dara, R. K. Yadav, S. S. Jadav, S. Dhamercherla, and A. Vidyarthi, “Nature Inspired Algorithms for Solving Multiple Sequence Alignment Problem: A Review,” Archives of Computational Methods in Engineering, vol. 29, no. 7, pp. 5237-5258, 2022.
[4] T. Paruchuri, G. R. Kancharla, and S. Dara, “Solving multiple sequence alignment problems by using a swarm intelligent optimization based approach,” International Journal of Electrical and Computer Engineering, vol. 13, no. 1, pp. 1097-1104, 2023.
[5] Q. Bani Baker, R. A. Al-Hussien, and M. Al-Ayyoub, “Accelerating Multiple Sequence Alignments Using Parallel Computing,” Computation, vol. 12, no. 2, pp. 32, 2024.
[6] S. H. Almanza-Ruiz, A. Chavoya, and H. A. Duran-Limon, “Parallel protein multiple sequence alignment approaches: a systematic literature review,” Journal of Supercomputing, vol. 79, no. 2, pp. 1201-1234, 2023.
[7] D. Sundfeld, and A. C. M. A. De Melo, "MSA-GPU: Exact multiple sequence alignment using GPU." pp. 47-58.
[8] J. D. Thompson, D. G. Higgins, and T. J. Gibson, “Clustal-W - Improving the Sensitivity of Progressive Multiple Sequence Alignment through Sequence Weighting, Position-Specific Gap Penalties and Weight Matrix Choice,” Nucleic Acids Research, vol. 22, no. 22, pp. 4673-4680, Nov 11, 1994.
[9] T. Lassmann, and E. L. L. Sonnhammer, “Automatic assessment of alignment quality,” Nucleic Acids Research, vol. 33, no. 22, pp. 7120-7128, 2005.
[10] R. Durbin, Biological sequence analysis: probabilistic models of proteins and nucleic acids, Cambridge, UK.: Cambridge university press, 1998.
[11] H. Carrillo, and D. Lipman, “The Multiple Sequence Alignment Problem in Biology,” Siam Journal on Applied Mathematics, vol. 48, no. 5, pp. 1073-1082, Oct, 1988.
[12] S. F. Altschul, R. J. Carroll, and D. J. Lipman, “Weights for Data Related by a Tree,” Journal of Molecular Biology, vol. 207, no. 4, pp. 647-653, Jun 20, 1989.
[13] J. D. Thompson, F. Plewniak, R. Ripp, J. C. Thierry, and O. Poch, “Towards a reliable objective function for multiple sequence alignments,” Journal of Molecular Biology, vol. 314, no. 4, pp. 937-951, Dec 7, 2001.
[14] C. G. Gcollet, “MstatX: A Multiple Alignment Analyser. GitHub,” 2010.
[15] C. Notredame, L. Holm, and D. G. Higgins, “COFFEE: An objective function for multiple sequence alignments,” Bioinformatics, vol. 14, no. 5, pp. 407-422, 1998.
[16] J. D. Thompson, and O. Poch, “New challenges and strategies for multiple sequence alignment in the proteomics era,” The proteomics protocols handbook, pp. 475-492, 2005.
[17] H. B. Nicholas, A. J. Ropelewski, and D. W. Deerfield, “Strategies for multiple sequence alignment,” Biotechniques, vol. 32, no. 3, pp. 572-591, Mar, 2002.
[18] D. J. Lipman, S. F. Altschul, and J. D. Kececioglu, “A Tool for Multiple Sequence Alignment,” Proceedings of the National Academy of Sciences of the United States of America, vol. 86, no. 12, pp. 4412-4415, Jun, 1989.
[19] O. Gotoh, “A Weighting System and Algorithm for Aligning Many Phylogenetically Related Sequences,” Computer Applications in the Biosciences, vol. 11, no. 5, pp. 543-551, Oct, 1995.
[20] F. B. R. Zablocki, “Multiple Sequence Alignment using Particle Swarm Optimization,” Department of Computer Science, University of Pretoria, 2007.
[21] J. D. Thompson, J. C. Thierry, and O. Poch, “RASCAL: rapid scanning and correction of multiple sequence alignments,” Bioinformatics, vol. 19, no. 9, pp. 1155-1161, Jun 12, 2003.
[22] J. Muller, C. J. Creevey, J. D. Thompson, D. Arendt, and P. Bork, “AQUA: automated quality improvement for multiple sequence alignments,” Bioinformatics, vol. 26, no. 2, pp. 263-265, Jan 15, 2010.
[23] M. Vingron, and P. R. Sibbald, “Weighting in Sequence Space - a Comparison of Methods in Terms of Generalized Sequences,” Proceedings of the National Academy of Sciences of the United States of America, vol. 90, no. 19, pp. 8777-8781, Oct 1, 1993.
[24] O. Gotoh, “Consistency of Optimal Sequence Alignments,” Bulletin of Mathematical Biology, vol. 52, no. 4, pp. 509-525, 1990.
[25] M. Vingron, and P. Argos, “Motif Recognition and Alignment for Many Sequences by Comparison of Dot-Matrices,” Journal of Molecular Biology, vol. 218, no. 1, pp. 33-43, Mar 5, 1991.
[26] J. Kececioglu, "The maximum weight trace problem in multiple sequence alignment," Combinatorial Pattern Matching, Lecture Notes in Computer Science A. Apostolico, M. Crochemore, Z. Galil and U. Manber, eds., pp. 106-119: Springer Berlin Heidelberg, 1993.
[27] C. Notredame, D. G. Higgins, and J. Heringa, “T-Coffee: A novel method for fast and accurate multiple sequence alignment,” Journal of Molecular Biology, vol. 302, no. 1, pp. 205-217, Sep 8, 2000.
[28] K. Katoh, and H. Toh, “Recent developments in the MAFFT multiple sequence alignment program,” Briefings in Bioinformatics, vol. 9, no. 4, pp. 286-298, Jul, 2008.
[29] I. Van Walle, I. Lasters, and L. Wyns, “Align-m - a new algorithm for multiple alignment of highly divergent sequences,” Bioinformatics, vol. 20, no. 9, pp. 1428-1435, Jun 12, 2004.
[30] W. S. J. Valdar, “Scoring residue conservation,” Proteins: Structure, Function, and Bioinformatics, vol. 48, no. 2, pp. 227-241, 2002.
[31] J. Fredrik, and T. Hiroyuki, “A comparative study of conservation and variation scores,” BMC Bioinformatics, vol. 11, pp. 388, 2010.
[32] T. Riaz, Y. Wang, and L. Kuo-Bin, “A Tabu Search Algorithm for Post-Processing Multiple Sequence Alignment,” Journal of Bioinformatics & Computational Biology, vol. 3, no. 1, pp. 145-156, 2005.
[33] Y. Wang, T. Riaz, E. ENERLY, S. ZENG, and K. B. Li, "A Position-Specific and Consistency-Based Objective Function for Iterative Multiple Sequence Alignment."
[34] Z. W. Geem, J. H. Kim, and G. V. Loganathan, “A new heuristic optimization algorithm: Harmony search,” Simulation, vol. 76, no. 2, pp. 60-68, Feb, 2001.
[35] G. Ingram, and T. Zhang, “Overview of applications and developments in the harmony search algorithm,” Music-Inspired Harmony Search Algorithm, pp. 15-37, 2009.
[36] X.-S. Yang, "Harmony Search as a Metaheuristic Algorithm," Music-Inspired Harmony Search Algorithm, Studies in Computational Intelligence Z. Geem, ed., pp. 1-14: Springer Berlin Heidelberg, 2009.
[37] S. Wang, R. R. Gutell, and D. P. Miranker, “Biclustering as a method for RNA local multiple sequence alignment,” Bioinformatics, vol. 23, no. 24, pp. 3289-3296, Dec 15, 2007.
[38] R. C. Edgar, “MUSCLE: a multiple sequence alignment method with reduced time and space complexity,” Bmc Bioinformatics, vol. 5, pp. 1-19, Aug 19, 2004.
Cite This Article
Choose your preferred format