CFP last date
22 July 2024
Reseach Article

A Hybrid Genetic Algorithm for RNA Structural Alignment

by Abdesslem Layeb, Imen Bensetira, Kenza Bouaroudj
International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 19 - Number 7
Year of Publication: 2011
Authors: Abdesslem Layeb, Imen Bensetira, Kenza Bouaroudj

Abdesslem Layeb, Imen Bensetira, Kenza Bouaroudj . A Hybrid Genetic Algorithm for RNA Structural Alignment. International Journal of Computer Applications. 19, 7 ( April 2011), 41-47. DOI=10.5120/2370-3120

@article{ 10.5120/2370-3120,
author = { Abdesslem Layeb, Imen Bensetira, Kenza Bouaroudj },
title = { A Hybrid Genetic Algorithm for RNA Structural Alignment },
journal = { International Journal of Computer Applications },
issue_date = { April 2011 },
volume = { 19 },
number = { 7 },
month = { April },
year = { 2011 },
issn = { 0975-8887 },
pages = { 41-47 },
numpages = {9},
url = { },
doi = { 10.5120/2370-3120 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
%0 Journal Article
%1 2024-02-06T20:06:24.369271+05:30
%A Abdesslem Layeb
%A Imen Bensetira
%A Kenza Bouaroudj
%T A Hybrid Genetic Algorithm for RNA Structural Alignment
%J International Journal of Computer Applications
%@ 0975-8887
%V 19
%N 7
%P 41-47
%D 2011
%I Foundation of Computer Science (FCS), NY, USA

The RNA structural alignment is one of the most challenging tasks in bioinformatics. However, finding the accurate conserved structure of a set of RNA sequences is still being a difficult task. In this work, the problem is cast as an optimization problem for which a new framework relaying on hybrid genetic algorithm is proposed. The contribution consists in using a new objective function based on the Structure Conservation Index (SCI). In order to enhance the Genetic Algorithms (GA) performances, a Simulated Annealing (SA) procedure has been used. The proposed algorithm is composed on two phases.The first phase consists of applying a genetic algorithm.In the second phase, the simulated annealing procedure is applied in order to improve the final population given by the genetic algorithm. Experiments on a wide range of data sets have shown the effectiveness of the proposed framework and its ability to achieve good quality solutions comparing to those given by others techniques.

  1. Eddy,S. R. 2001. Non-coding RNA genes and the modern RNA world. Nat Rev Genet 2(Dec 2001), 919-929.
  2. Mattick,J. S.,Makunin,I. V. 2006. Non-coding RNA. Hum Mol Genet 15 Spec N°1, R17(Apr 2006).
  3. Gorodkin,J., Heyer,L., Brunak,S. and Stormo,G. 1997. Displaying the information contents of structural RNA alignments. CABIOS, Vol. 13, 583–586.
  4. Gutell, R., Power, A., Hertz, G., Putz, E. &Stormo, G. 1992. Identifying constraints on the higher-order structure of RNA: continued development and application of comparative sequence analysis methods. Nucleic Acids Res, Vol. 20 (21), 5785–595.
  5. Zuker, M., Jaeger, J. & Turner, D. 1991. A comparison of optimal and suboptimal RNA secondary structures predicted by free energy minimization with structures determined by phylogenetic comparison. Nucleic Acids Res,Vol. 19 (10),2707–214.
  6. Han,K.-H. andKim,J.-H. 2000. Genetic quantum algorithm and its application to combinatorial optimization problem. Proc. 2000 Congr. Genetic Computation, vol. 2, La Jolla, CA, 1354–1360.
  7. Kirkpatrick, C.D. Gelart, and P.M. Vecchi. 1983. Optimization by Simulated Annealing. Science, Vol. 220, 671-680.
  8. Balaji, A.N., Jawahar, N. 2010. A Simulated Annealing Algorithm for a two-stage fixed charge distribution problem of a Supply Chain. International Journal of Operational Research, Vol. 7, No.2, 192 – 215.
  9. Washietl, S., Hofacker, I. and Stadler, P. 2005. Fast and reliable prediction of noncoding RNAs. Proc. Natl Acad. Sci. Vol. 102, 2454–2459.
  10. Gruber, A.R., Bernhart, S.H., Hofacker, I.L., Washietl, S. 2008. Strategies for measuring evolutionary conservation of RNA secondary structures. BMC Bioinformatics 9, 122.
  11. Gardner, P., Wilm, A. and Washietl, S. 2005. A benchmark of multiple sequence alignment programs upon structural RNAs. Nucleic Acids Research, Vol. 33(8) 2433–2439.
  12. Sankoff, D. and Kruskal, J. B. 1983.Time warps, string edits, and macromolecules: The theory and practice of sequence comparison.Addison Wesley.
  13. Layeb, A, Meshoul, S., andBatouche, M. 2008. Quantum Genetic Algorithm for Multiple RNA Structural Alignment in the IEEE proceedings of the 2nd Asia International Conference on Modelling& Simulation, pp. 873-877.
  14. Washietl, S. 2010. Sequence and structure analysis of noncoding RNAs. Methods in Molecular Biology, Vol. 609, 285-306.
  15. Washietl, S. and Hofacker,I. 2004. Consensus folding of aligned sequences as a new measure for the detection of functional RNAs by comparative genomics. J. Mol. Biol., Vol. 342, pp. 19–30.
  16. Hofacker, I. L.,Fekete,M., andStadler,P. F. 2002. Secondary structure prediction for aligned RNA sequences. J. Mol. Biol., Vol. 319, 1059–1066.
  17. Hofacker, I. L. 2003. Vienna RNA secondary structure server. Nucleic Acids Res, Vol. 31, 3429-3431.
  18. Okada,Y., Sato, K., and Sakakibara, Y. 2010. Improvement of structure conservation index with centroid estimators. Pacific Symposium on Bio computing, 15:88-97.
  19. Chenna, R., Sugawara, H., Koike, T., Lopez, R., Gibson,TJ., Higgins, DG., Thompson, JD. 2003. Multiple sequence alignment with the Clustal series of programs.Nucleic Acids Res., Vol. 31, 3497-3500.
  20. Thierens,D.1997.Selection schemes, elitist recombination and selection intensity. in International conference of genetic algorithm, pp. 152-159.
  21. Ziv-Ukelso, M. 2010. A faster algorithm for simultaneous alignment and folding of RNA. Journal of Computational Biology, 17(8), 1051-1065.
  22. Hamada, M., Kiryu, H., Sato, K., Mituyama, T., and Asai, K. 2009. Bioinformatics, 15; 25(4):465-473.
  23. Gesell,T., and Washietl, S. 2008.Dinucleotide controlled null models for comparative RNA gene prediction. BMC Bioinformatics, 9:248.
  24. Tahi, F.,Engelen, S., andRégnier,M. 2003. A Fast Algorithm for RNA Secondary Structure Prediction Including Pseudoknots. Third IEEE Symposium on BioInformatics and BioEngineering (BIBE'03), pp.11.
  25. Engelen, S., andTahi, F. 2010. Tfold: efficient in silico prediction of non-coding RNA secondary structures.Nucleic Acids Res; 38(7):2453-2466.
  26. Engelen, S., andTahi, F. 2007.Predicting RNA secondary structure by the comparative approach: how to select the homologous sequences. BMC Bioinformatics; 8:464.
  27. Washietl, S., Hofacker, I.L., Stadler, P.F.2005. Fast and reliable prediction of noncoding RNAs.ProcNatlAcadSci, 102(7):2454-2459.
Index Terms

Computer Science
Information Sciences


RNA Structure Prediction Genetic Algorithm Simulated Annealing Structure Conservation Index