Abstract
This paper introduces a caching enabled parallel multi-objective tri-level particle swarm optimization algorithm (MO-3LPPSO) with objective to address a challenging NP-hard problem from bioinformatics i.e. structural alignment of complex RNA sequences. MO-3LPPSO implements master-slave topology based communication strategy on the parallely connected machines via message passing interface (MPI). Level 1 of the proposed algorithm acquires the optimal alignment of the sequences distributed on slave processors in the order of their complexities. Further, the aligned sequences along with their alignment scores are stored on the master processor. In the second level, the secondary structures of all the gbest aligned sequences of level 1 is obtained. Each sequence set is distributed on a slave processors, that constructs secondary structure of all sequences from the set. The alignment scores and secondary structure scores obtained from level 1 and level 2, now move towards level 3, forming a bi-objective optimization problem with the objectives to maximize sequence similarity score and minimize free energy score for most stable RNA secondary structure. The top-level non-dominated solutions are extracted further in level three and the external archive in Ctrie is updated. The improvement from MO-TLPSO to MO-3LPPSO has been remarkable in the sense: inclusion of Ctrie enables the algorithm to work with multi-client environment for handling RNA structural alignment queries; implementation of parallelization facilitates structural alignment of highly complex massive datasets of RNA sequences. Further, the difference between the time taken by MO-TLPSO and MO-3LPPSO is found extremely significant, as confirmed by non-parametric statistical test Mann-Whitney U test. Further, the structural alignment of highly complex sequence sets is performed by MO-3LPPSO, which is tested for prediction accuracy and processing time. The algorithm is found producing highly accurate results at significantly lesser processing time.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Cao B, Zhao J, Zhihan L, Liu X, Yang S, Kang X, Kang K (2017) Distributed parallel particle swarm optimization for multi-objective and many-objective large-scale optimization. IEEE Access Spec Sect Big Data Anal Internet Things Cyber Phys Syst 5:8214–8221
Zhou Y, Tan Y (2011) GPU based parallel multi-objective particle swarm optimization International. J Artif Intell 7(A11):125–141
Handl J, Kell DB, Knowles J (2007) Multiobjective optimization in bioinformatics and computational biology. IEEE/ACM Trans Comput Biol Bioinform 4(2):279–292
Briandais RDL (1959) File searching using variable length keys. In: Proceedings of the western joint computer conference, pp 295–298
Fredkin E (1960) Trie memory. Commun ACM 3(9):490–499
Bagwell P (2001) Ideal hash trees. Technical report
Prokopec A, Bagwell P, Odersky M (2011) Cache-aware lock-free concurrent hash tries. Technical report
Lalwani S, Sharma H, Verma A, Deep K (2017) Minimization of makespan for parallel machines using PSO to enhance caching of MSA based multi-query processes. In: Proceeding of 7th international conference on soft computing for problem solving (SocProS), 2017, India, Advances in intelligent systems and computing, vol 2, pp 193–205
Borer PN, Dengler B, Tinoco I, Uhlenbeck OC (1974) Stability of ribonucleic acid double-stranded helices. J Mol Biol 86:843–853
Lalwani S, Kumar R, Gupta N (2014) Sequence-structure alignment techniques for RNA: a comprehensive survey. Adv Life Sci 4(1):21–35
Dowell RD, Eddy SR (2006) Efficient pairwise RNA structure prediction and alignment using sequence alignment constraints. BMC Bioinform 7:400
Kemena C, Bussotti G, Capriotti E, Marti-Renom MA, Notredame C (2013) Using tertiary structure for the computation of highly accurate multiple RNA alignments with the SARA-Coffee package. Bioinformatics 29(9):1112–1119
Mortimer SA, Weeks KM (2007) A fast-acting reagent for accurate analysis of RNA secondary and tertiary structure by SHAPE chemistry. J Am Chem Soc 129(14):4144–4145
Schnattinger T, Schoning U, Kestler HA (2013) Structural RNA alignment by multi-objective optimization. Bioinformatics 29(13):1607–1613
Taneda A (2008) An efficient genetic algorithm for structural RNA pairwise alignment and its application to non-coding RNA discovery in yeast. BMC Bioinform 9:521
Lalwani S, Kumar R, Deep K (2017) Multi-objective two-level swarm intelligence approach for multiple RNA sequence-structure alignment. Swarm Evolut Comput 34:130–144
Mathews DH, Sabina J, Zuker M, Turner DH (1999) Expanded sequence dependence of thermodynamic parameters improves prediction of RNA secondary structure. J Mol Biol 288:911–940
Wiese KC, Glen E (2003) A permutation-based genetic algorithm for the RNA folding problem: a critical look at selection strategies, crossover operators, and representation issues. Biosystems 72:29–41
Mathews DH, Disney MD, Childs JL, Schroeder SJ, Zuker M, Turner DH (2004) Incorporating chemical modification constraints into a dynamic programming algorithm for prediction of RNA secondary structure. Proc Natl Acad Sci 109:7287–7292
Kennedy JF, Eberhart RC (1995) Particle swarm optimization. In: Proceedings of IEEE international conference on neural networks, Piscataway, pp 1942–1948
Chellapilla K, Fogel GB (1999) Multiple sequence alignment using evolutionary programming. In: Proceedings of the 1999 congress on evolutionary computation, Washington DC, vol 1, pp 445–452
Lindgreen S, Gardner PP, Krogh A (2007) MASTR: multiple alignment and structure prediction of non-coding RNAs using simulated annealing. Bioinformatics 23(24):3304–3311
Lalwani S, Kumar R, Gupta N (2016) An efficient two-level swarm intelligence approach for RNA secondary structure prediction based on improved bi-objective minimum free energy scores. Swarm Evolut Comput 27:68–79
Lalwani S, Kumar R, Gupta N (2016) An efficient two-level swarm intelligence approach for multiple sequence alignment. Comput Inform 35(4):963–985
Deb K (2001) Multi-objective optimization using evolutionary algorithms, systems and optimization, 1st edn. Wiley-Interscience Series, New York
Lalwani S, Singhal S, Kumar R, Gupta N (2013) A comprehensive survey: applications of multi-objective particle swarm optimization (MOPSO) algorithm. Trans Comb 2(1):39–101
Taneda A (2010) Multi-objective pairwise RNA sequence alignment. BMC Bioinform 26(19):2383–2390
Wilm A, Mainz I, Steger G (2006) An enhanced RNA alignment benchmark for sequence alignment programs. Algorithms Mol Biol 1:19
Will S, Joshi T, Hofacker IL, Stadler PF, Backofen R (2012) LocARNA-P: accurate boundary prediction and improved detection of structural RNAs. RNA 18(5):900–914
Gropp W, Lusk E, Skjellum A (1999) Using MPI: portable parallel programming with the message-passing interface. MIT Press, Cambridge, p 1
Zhang GW, Zhan ZH, Du KJ, Lin Y, Chen WN, Li JJ, Zhang J (2015) Parallel particle swarm optimization using message passing interface. In: Proceedings of the 18th asia pacific symposium on intelligent and evolutionary systems, vol 1, Singapore, pp 55–64
Acknowledgements
The first author (S.L.) gratefully acknowledges Science and Engineering Research Board, DST, Government of India for the fellowship (PDF/2016/000008). We are thankful to Dr. Krishna Mohan from BISR, Jaipur, India for his valuable suggestions throughout the work.
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
About this article
Cite this article
Lalwani, S., Sharma, H. Multi-objective three level parallel PSO algorithm for structural alignment of complex RNA sequences. Evol. Intel. 14, 1251–1259 (2021). https://doi.org/10.1007/s12065-018-00198-y
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s12065-018-00198-y