Login Register Cart 0
Generic placeholder image

Recent Advances in Computer Science and Communications

Editor-in-Chief

ISSN (Print): 2666-2558
ISSN (Online): 2666-2566

Back
Journal Home About Journal Editorial Board Current Issue Volumes/Issues
Subscribe
Research Article

An Implementation of Three-level Multi-objective ABC Algorithm for RNA Multiple Structural Alignment

Author(s): Soniya Lalwani*, Harish Sharma and Kusum Deep

Volume 13, Issue 1, 2020

Page: [68 - 76] Pages: 9

DOI: 10.2174/2213275912666181128121104

Price: $65

conference banner
Abstract

Background: Structural alignment of ribose nucleic acid (RNA) is one of the most challenging multi-objective real world problems from the field of bioinformatics.

Objective: RNA molecules are less stable; hence they require inclusion of most stable secondary structure during their alignment. Therefore, the structural alignment requires the consideration of similarity score and structure score, as two objectives. Trade-off between these two objectives exists since obtaining optimum similarity score at concurrent optimum structure score is not possible. This paper presents artificial bee colony algorithm based three level multi-objective approach for performing structural alignment of RNA sequences, namely MO-3LABC.

Methods: Algorithm firstly builds the secondary structure of all sequences at minimum free energy (MFE). Then sequence alignment is performed in level one at average percent sequence identity (APSI) score based gap length, optimized by ABC algorithm. Level two now builds the secondary structure of these aligned sequences based on base-pair probability and co-variation. Now the scores of level one and level two move towards level three for multi-objective optimization at Pareto optimality criteria with few additional strategies.

Results: The results of MO-3LABC are compared with an already established efficient strategy MO-TLPSO; multi-objective two level strategy based on particle swarm optimization. The outputs are compared for pairwise and multiple sequence alignment datasets at prediction accuracy and solution quality criteria.

Conclusion: MO-3LABC is found significantly better than MO-TLPSO at all the four evaluation criteria for both the datasets.

Keywords: RNA structural alignment, artificial bee colony algorithm, non-dominated solutions, multiple sequence alignment, multi-objective optimization, pareto optimal solutions, conflicting objectives.

Graphical Abstract

[1]
A. Taneda, "Multi-objective pairwise RNA sequence alignment", Bioinformatics, vol. 26, pp. 2383-2390, 2010.
[http://dx.doi.org/10.1093/bioinformatics/btq439] [PMID: 20679330]
[2]
T. Schnattinger, U. Schöning, and H.A. Kestler, "Structural RNA alignment by multi-objective optimization", Bioinformatics, vol. 29, pp. 1607-1613, 2013.
[http://dx.doi.org/10.1093/bioinformatics/btt188] [PMID: 23620356]
[3]
R. Dowell, and S. Eddy, "Efficient pairwise RNA structure prediction and alignment using sequence alignment constraints", In: BMC Bioinformatics, vol. Vol. 7. 2006.
[4]
I. Holmes, "Accelerated probabilistic inference of RNA structure evolution", BMC Bioinformatics, vol. 6, p. 73, 2005.
[http://dx.doi.org/10.1186/1471-2105-6-73] [PMID: 15790387]
[5]
M. Bauer, G.W. Klau, and K. Reinert, "Accurate multiple sequence-structure alignment of RNA sequences using combinatorial optimization", BMC Bioinformatics, vol. 8, p. 271, 2007.
[http://dx.doi.org/10.1186/1471-2105-8-271] [PMID: 17662141]
[6]
A.O. Harmanci, G. Sharma, and D.H. Mathews, "Efficient pairwise RNA structure prediction using probabilistic alignment constraints in Dynalign", BMC Bioinformatics, vol. 8, p. 130, 2007.
[http://dx.doi.org/10.1186/1471-2105-8-130] [PMID: 17445273]
[7]
J.H. Havgaard, E. Torarinsson, and J. Gorodkin, "Fast pairwise structural RNA alignments by pruning of the dynamical programming matrix", PLOS Comput. Biol., vol. 3, pp. 1896-1908, 2007.
[http://dx.doi.org/10.1371/journal.pcbi.0030193] [PMID: 17937495]
[8]
H. Kiryu, Y. Tabei, T. Kin, and K. Asai, "Murlet: A practical multiple alignment tool for structural RNA sequences", Bioinformatics, vol. 23, pp. 1588-1598, 2007.
[http://dx.doi.org/10.1093/bioinformatics/btm146] [PMID: 17459961]
[9]
S. Will, K. Reiche, I.L. Hofacker, P.F. Stadler, and R. Backofen, "Inferring noncoding RNA families and classes by means of genome-scale structure-based clustering", PLOS Comput. Biol., vol. 3, p. pp. e65, 2007.
[http://dx.doi.org/10.1371/journal.pcbi.0030065] [PMID: 17432929]
[10]
S. Lindgreen, P.P. Gardner, and A. Krogh, "MASTR: Multiple alignment and structure prediction of non-coding RNAs using simulated annealing", Bioinformatics, vol. 23, pp. 3304-3311, 2007.
[http://dx.doi.org/10.1093/bioinformatics/btm525] [PMID: 18006551]
[11]
A. Taneda, "An efficient genetic algorithm for structural RNA pairwise alignment and its application to non-coding RNA discovery in yeast", BMC Bioinformatics, vol. 9, p. 521, 2008.
[http://dx.doi.org/10.1186/1471-2105-9-521] [PMID: 19061486]
[12]
J. Reeder, and R. Giegerich, "Consensus shapes: An alternative to the Sankoff algorithm for RNA consensus structure prediction", Bioinformatics, vol. 21, pp. 3516-3523, 2005.
[http://dx.doi.org/10.1093/bioinformatics/bti577] [PMID: 16020472]
[13]
X. Xu, Y. Ji, and G.D. Stormo, "RNA Sampler: A new sampling based algorithm for common RNA secondary structure prediction and structural alignment", Bioinformatics, vol. 23, pp. 1883-1891, 2007.
[http://dx.doi.org/10.1093/bioinformatics/btm272] [PMID: 17537756]
[14]
C.B. Do, C.S. Foo, and S. Batzoglou, "A max-margin model for efficient simultaneous alignment and folding of RNA sequences", Bioinformatics, vol. 24, pp. i68-i76, 2008.
[http://dx.doi.org/10.1093/bioinformatics/btn177] [PMID: 18586747]
[15]
M. Hamada, K. Sato, H. Kiryu, T. Mituyama, and K. Asai, "Centroid align: Fast and accurate aligner for structured RNAs by maximizing expected sum-of-pairs score", Bioinformatics, vol. 25, pp. 3236-3243, 2009.
[http://dx.doi.org/10.1093/bioinformatics/btp580] [PMID: 19808876]
[16]
I.M. Meyer, and I. Miklós, "SimulFold: Simultaneously inferring RNA structures including pseudoknots, alignments, and trees using a Bayesian MCMC framework", PLOS Comput. Biol., vol. 3, p. pp. e149, 2007.
[http://dx.doi.org/10.1371/journal.pcbi.0030149] [PMID: 17696604]
[17]
J. Kennedy, and R.C. Eberhart, Particle swarm optimizationIn the Proceedings of IEEE International Conference on Neural Networks, Piscataway, NJ, USA, 1995.
[http://dx.doi.org/10.1109/ICNN.1995.488968]
[18]
S. Lalwani, R. Kumar, and K. Deep, "Multi-objective two-level swarm intelligence approach for multiple RNA sequence-structure alignment", Swarm Evol. Comput., vol. 34, pp. 130-144, 2017.
[http://dx.doi.org/10.1016/j.swevo.2017.02.002]
[19]
S. Lalwani, R. Kumar, and N. Gupta, "An efficient two-level swarm intelligence approach for RNA secondary structure prediction based on improved bi-objective minimum free energy scores", Swarm Evol. Comput., vol. 27, pp. 68-79, 2016.
[http://dx.doi.org/10.1016/j.swevo.2015.09.008]
[20]
S. Lalwani, R. Kumar, and N. Gupta, "Sequence-structure alignment techniques for RNA: A comprehensive survey", Adv. Life Sci., vol. 4, pp. 21-35, 2014.
[21]
D.H. Mathews, M.D. Disney, J.L. Childs, S.J. Schroeder, M. Zuker, and D.H. Turner, "Incorporating chemical modification constraints into a dynamic programming algorithm for prediction of RNA secondary structure", Proc. Natl. Acad. Sci. USA, vol. 101, pp. 7287-7292, 2004.
[http://dx.doi.org/10.1073/pnas.0401799101] [PMID: 15123812]
[22]
S. Siebert, and R. Backofen, "MARNA: Multiple alignment and consensus structure prediction of RNAs based on sequence structure comparisons", Bioinformatics, vol. 21, pp. 3352-3359, 2005.
[http://dx.doi.org/10.1093/bioinformatics/bti550] [PMID: 15972285]
[23]
A. Wilm, I. Mainz, and G. Steger, "An enhanced RNA alignment benchmark for sequence alignment programs", Algorithms Mol. Biol., vol. 1, p. 19, 2006.
[http://dx.doi.org/10.1186/1748-7188-1-19] [PMID: 17062125]
[24]
S. Lalwani, R. Kumar, and N. Gupta, "An efficient two-level swarm intelligence approach for multiple sequence alignment", Comput. Inf., vol. 35, pp. 963-985, 2016.
[25]
D. Karaboga, and B. Basturk, "On the performance of Artificial Bee Colony (ABC) algorithm", Appl. Soft Comput., vol. 8, pp. 687-697, 2008.
[http://dx.doi.org/10.1016/j.asoc.2007.05.007]
[26]
B. Karaboga, C. Ozturk, and N. Karaboga, "A comprehensive survey: Artificial Bee Colony (ABC) algorithm and applications", Artif. Intell. Rev., vol. 42, pp. 21-57, 2014.
[http://dx.doi.org/10.1007/s10462-012-9328-0]
[27]
K. Deb, "Multi-objective optimization using evolutionary algorithms", IEEE Trans. Evol. Comput., vol. 6, pp. 182-197, 2002.
[http://dx.doi.org/10.1109/4235.996017]
[28]
K. Deb, "Multiobjective optimization using evolutionary algorithms", In: Wiley-Interscience series in Systems and Optimization, 2001.
[29]
P.P. Gardner, A. Wilm, and S. Washietl, "A benchmark of multiple sequence alignment programs upon structural RNAs", Nucleic Acids Res., vol. 33, pp. 2433-2439, 2005.
[http://dx.doi.org/10.1093/nar/gki541] [PMID: 15860779]
[30]
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 Res., vol. 22, pp. 4673-4680, 1994.
[http://dx.doi.org/10.1093/nar/22.22.4673] [PMID: 7984417]
[31]
K. Katoh, K. Misawa, K. Kuma, and T. Miyata, "MAFFT: A novel method for rapid multiple sequence alignment based on fast fourier transform", Nucleic Acids Res., vol. 30, pp. 3059-3066, 2002.
[http://dx.doi.org/10.1093/nar/gkf436] [PMID: 12136088]
[32]
D. Dalli, A. Wilm, I. Mainz, and G. Steger, "STRAL: Progressive alignment of non-coding RNA using base pairing probability vectors in quadratic time", Bioinformatics, vol. 22, pp. 1593-1599, 2006.
[http://dx.doi.org/10.1093/bioinformatics/btl142] [PMID: 16613908]

Rights & Permissions Print Cite
Article Metrics
2
© 2024 Bentham Science Publishers | Privacy Policy