Abstract

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.

References

• Eddy,S. R. 2001. Non-coding RNA genes and the modern RNA world. Nat Rev Genet 2(Dec 2001), 919-929.
• Mattick,J. S.,Makunin,I. V. 2006. Non-coding RNA. Hum Mol Genet 15 Spec N°1, R17(Apr 2006).
• Gorodkin,J., Heyer,L., Brunak,S. and Stormo,G. 1997. Displaying the information contents of structural RNA alignments. CABIOS, Vol. 13, 583–586.
• 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.
• 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.
• 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.
• Kirkpatrick, C.D. Gelart, and P.M. Vecchi. 1983. Optimization by Simulated Annealing. Science, Vol. 220, 671-680.
• 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.
• Washietl, S., Hofacker, I. and Stadler, P. 2005. Fast and reliable prediction of noncoding RNAs. Proc. Natl Acad. Sci. Vol. 102, 2454–2459.
• 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.
• 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.
• Sankoff, D. and Kruskal, J. B. 1983.Time warps, string edits, and macromolecules: The theory and practice of sequence comparison.Addison Wesley.
• 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.
• Washietl, S. 2010. Sequence and structure analysis of noncoding RNAs. Methods in Molecular Biology, Vol. 609, 285-306.
• 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.
• Hofacker, I. L.,Fekete,M., andStadler,P. F. 2002. Secondary structure prediction for aligned RNA sequences. J. Mol. Biol., Vol. 319, 1059–1066.
• Hofacker, I. L. 2003. Vienna RNA secondary structure server. Nucleic Acids Res, Vol. 31, 3429-3431.
• Okada,Y., Sato, K., and Sakakibara, Y. 2010. Improvement of structure conservation index with centroid estimators. Pacific Symposium on Bio computing, 15:88-97.
• 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.
• Thierens,D.1997.Selection schemes, elitist recombination and selection intensity. in International conference of genetic algorithm, pp. 152-159.
• Ziv-Ukelso, M. 2010. A faster algorithm for simultaneous alignment and folding of RNA. Journal of Computational Biology, 17(8), 1051-1065.
• Hamada, M., Kiryu, H., Sato, K., Mituyama, T., and Asai, K. 2009. Bioinformatics, 15; 25(4):465-473.
• Gesell,T., and Washietl, S. 2008.Dinucleotide controlled null models for comparative RNA gene prediction. BMC Bioinformatics, 9:248.
• 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.
• Engelen, S., andTahi, F. 2010. Tfold: efficient in silico prediction of non-coding RNA secondary structures.Nucleic Acids Res; 38(7):2453-2466.
• Engelen, S., andTahi, F. 2007.Predicting RNA secondary structure by the comparative approach: how to select the homologous sequences. BMC Bioinformatics; 8:464.
• Washietl, S., Hofacker, I.L., Stadler, P.F.2005. Fast and reliable prediction of noncoding RNAs.ProcNatlAcadSci, 102(7):2454-2459.