T. Akutsu, Dynamic programming algorithms for RNA secondary structure prediction with pseudoknots, Discrete Applied Mathematics, vol.104, issue.1-3, pp.45-62, 2000.
DOI : 10.1016/S0166-218X(00)00186-4

C. Alkan, E. Karakoc, J. H. Nadeau, S. C. Sahinalp, and K. Zhang, RNA???RNA Interaction Prediction and Antisense RNA Target Search, Journal of Computational Biology, vol.13, issue.2, pp.267-282, 2006.
DOI : 10.1089/cmb.2006.13.267

P. P. Amaral, M. B. Clark, D. K. Gascoigne, M. E. Dinger, and J. S. Mattick, lncRNAdb: a reference database for long noncoding RNAs, Nucleic Acids Research, vol.39, issue.Database, pp.39-146, 2011.
DOI : 10.1093/nar/gkq1138

J. Atkins, R. Gesteland, and T. Cech, RNA Worlds : From Life's Origins to Diversity in Gene Regulation. Cold Spring Harbor Perspectives in Biology, 2011.

H. M. Berman, J. Westbrook, Z. Feng, G. Gilliland, T. N. Bhat et al., The Protein Data Bank, Nucleic Acids Research, vol.28, issue.1, pp.235-242, 2000.
DOI : 10.1093/nar/28.1.235

M. Bon, G. Vernizzi, H. Orland, and A. Zee, Topological Classification of RNA Structures, Journal of Molecular Biology, vol.379, issue.4, pp.900-911, 2008.
DOI : 10.1016/j.jmb.2008.04.033

A. Busch, A. S. Richter, and R. Backofen, IntaRNA: efficient prediction of bacterial sRNA targets incorporating target site accessibility and seed regions, Bioinformatics, vol.24, issue.24, pp.242849-2856, 2008.
DOI : 10.1093/bioinformatics/btn544

R. B. Cary and G. D. Stormo, Graph-theoretic approach to RNA modeling using comparative data, Proceedings International Conference on Intelligent Systems for Molecular Biology, pp.75-80, 1995.

Y. Ding, C. Y. Chan, and C. E. Lawrence, RNA secondary structure prediction by centroids in a Boltzmann weighted ensemble, RNA, vol.11, issue.8, pp.1157-1166, 2005.
DOI : 10.1261/rna.2500605

. Encode-project and . Consortium, Identification and analysis of functional elements in 1% of the human genome by the ENCODE pilot project, Nature, vol.447, issue.7146, pp.799-816, 2007.

T. W. Fawcett and A. D. Higginson, Heavy use of equations impedes communication among biologists, Proceedings of the National Academy of Sciences, pp.11735-11739, 2012.
DOI : 10.1073/pnas.1205259109

T. W. Fawcett and A. D. Higginson, Reply to Chitnis and Smith, Fernandes, Gibbons, and Kane: Communicating theory effectively requires more explanation, not fewer equations, Proceedings of the National Academy of Sciences, pp.3058-3059, 2012.
DOI : 10.1073/pnas.1213721109

E. Freyhult, V. Moulton, and P. Clote, Boltzmann probability of RNA structural neighbors and riboswitch detection, Bioinformatics, vol.23, issue.16, pp.2054-2062, 2007.
DOI : 10.1093/bioinformatics/btm314

P. P. Gardner and R. Giegerich, A comprehensive comparison of comparative RNA structure prediction approaches, BMC Bioinformatics, vol.5, issue.1, p.140, 2004.
DOI : 10.1186/1471-2105-5-140

F. Gavril, Algorithms for a maximum clique and a maximum independent set of a circle graph, Networks, vol.1, issue.3, pp.261-273, 1973.
DOI : 10.1002/net.3230030305

J. Gibbons, Do not throw equations out with the theory bathwater, Proceedings of the National Academy of Sciences, p.3054, 2012.
DOI : 10.1073/pnas.1212498109

S. Griffiths-jones, A. Bateman, M. Marshall, A. Khanna, and S. R. Eddy, Rfam: an RNA family database, Nucleic Acids Research, vol.31, issue.1, pp.439-441, 2003.
DOI : 10.1093/nar/gkg006

I. L. Hofacker, M. Fekete, and P. F. Stadler, Secondary Structure Prediction for Aligned RNA Sequences, Journal of Molecular Biology, vol.319, issue.5, pp.1059-1066, 2002.
DOI : 10.1016/S0022-2836(02)00308-X
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.461.9804

C. Höner-zu-siederdissen, S. H. Bernhart, P. F. Stadler, and I. L. Hofacker, A folding algorithm for extended RNA secondary structures, Bioinformatics, vol.27, issue.13, pp.27-129, 2011.
DOI : 10.1093/bioinformatics/btr220

T. Kasami, An efficient recognition and syntax-analysis algorithm for context-free languages, 1965.

N. B. Leontis and E. Westhof, Geometric nomenclature and classification of RNA base pairs, RNA, vol.7, issue.4, pp.499-512, 2001.
DOI : 10.1017/S1355838201002515

V. Levenshtein, Binary codes capable of correcting deletions, insertions, and reversals, Soviet Physics Doklady, vol.10, pp.707-717, 1966.

R. B. Lyngsø, Complexity of Pseudoknot Prediction in Simple Models, Proceedings of ICALP, pp.919-931, 2004.
DOI : 10.1007/978-3-540-27836-8_77

R. B. Lyngsø and C. N. Pedersen, RNA Pseudoknot Prediction in Energy-Based Models, Journal of Computational Biology, vol.7, issue.3-4, pp.409-427, 2000.
DOI : 10.1089/106652700750050862

D. H. Mathews, J. Sabina, M. Zuker, and D. H. Turner, Expanded sequence dependence of thermodynamic parameters improves prediction of RNA secondary structure, Journal of Molecular Biology, vol.288, issue.5, pp.911-940, 1999.
DOI : 10.1006/jmbi.1999.2700

J. S. Mccaskill, The equilibrium partition function and base pair binding probabilities for RNA secondary structure, Biopolymers, vol.24, issue.6-7, pp.1105-1119, 1990.
DOI : 10.1002/bip.360290621

U. Mückstein, H. Tafer, J. Hackermüller, S. H. Bernhart, P. F. Stadler et al., Thermodynamics of RNA-RNA binding, Bioinformatics, vol.22, issue.10, pp.221177-1182, 2006.
DOI : 10.1093/bioinformatics/btl024

E. P. Nawrocki, D. L. Kolbe, and S. R. Eddy, Infernal 1.0: inference of RNA alignments, Bioinformatics, vol.25, issue.10, pp.1335-1337, 2009.
DOI : 10.1093/bioinformatics/btp157

R. Nussinov, G. Pieczenik, J. Griggs, and D. Kleitman, Algorithms for Loop Matchings, SIAM Journal on Applied Mathematics, vol.35, issue.1, pp.68-82, 1978.
DOI : 10.1137/0135006

M. Parisien and F. Major, The MC-Fold and MC-Sym pipeline infers RNA structure from sequence data, Nature, vol.349, issue.7183, pp.51-55, 2008.
DOI : 10.1038/nature06684

Y. Ponty, Bio-algorithmique des ARN : petite promenade aux interfaces, 1024 -Bulletin de la société informatique de France SIF -Institut Henri Poincaré, 11 rue Pierre et Marie Curie, pp.23-53
URL : https://hal.archives-ouvertes.fr/hal-01077506

D. Sankoff, Simultaneous Solution of the RNA Folding, Alignment and Protosequence Problems, SIAM Journal on Applied Mathematics, vol.45, issue.5, pp.810-825, 1985.
DOI : 10.1137/0145048

S. Sheikh, R. Backofen, and Y. Ponty, Impact of the Energy Model on the Complexity of RNA Folding with Pseudoknots, Combinatorial Pattern Matching, pp.321-333, 2012.
DOI : 10.1007/978-3-642-31265-6_26
URL : https://hal.archives-ouvertes.fr/hal-00670232

T. Smith and M. Waterman, Identification of common molecular subsequences, Journal of Molecular Biology, vol.147, issue.1, pp.195-197, 1981.
DOI : 10.1016/0022-2836(81)90087-5

I. Tinoco, O. C. Uhlenbeck, and M. D. Levine, Estimation of Secondary Structure in Ribonucleic Acids, Nature, vol.5, issue.5293, pp.362-367, 1971.
DOI : 10.1038/230362a0

H. Touzet and O. Perriquet, CARNAC: folding families of related RNAs, Nucleic Acids Research, vol.32, issue.Web Server, pp.142-145, 2004.
DOI : 10.1093/nar/gkh415

D. H. Turner and D. H. Mathews, NNDB: the nearest neighbor parameter database for predicting stability of nucleic acid secondary structure, Nucleic Acids Research, vol.38, issue.Database, pp.280-282, 2010.
DOI : 10.1093/nar/gkp892

J. Waldisphl and Y. Ponty, An Unbiased Adaptive Sampling Algorithm for the Exploration of RNA Mutational Landscapes Under Evolutionary Pressure, Journal of Computational Biology, vol.18, issue.11, pp.1465-1479, 2011.
DOI : 10.1089/cmb.2011.0181

S. Wuchty, W. Fontana, I. L. Hofacker, and P. Schuster, Complete suboptimal folding of RNA and the stability of secondary structures, Biopolymers, vol.49, issue.2, pp.145-165, 1999.
DOI : 10.1002/(SICI)1097-0282(199902)49:2<145::AID-BIP4>3.3.CO;2-7

M. Zuker, On finding all suboptimal foldings of an RNA molecule, Science, vol.244, issue.4900, pp.48-52, 1989.
DOI : 10.1126/science.2468181

M. Zuker and A. B. Jacobson, Using reliability information to annotate RNA secondary structures, RNA, vol.4, issue.6, pp.669-679, 1998.
DOI : 10.1017/S1355838298980116

M. Zuker and D. Sankoff, RNA secondary structures and their prediction, Bulletin of Mathematical Biology, vol.9, issue.Suppl. 2, pp.591-621, 1984.
DOI : 10.1007/BF02459506

M. Zuker and P. Stiegler, Optimal computer folding of large RNA sequences using thermodynamics and auxiliary information, Nucleic Acids Research, vol.9, issue.1, pp.133-148, 1981.
DOI : 10.1093/nar/9.1.133

V. L. Arlazarov, E. A. Dinic, M. A. Kronrod, and I. A. Faradev, On economical construction of the transitive closure of a directed graph, Soviet Mathematics? Doklady, vol.11, issue.5, pp.1209-1210, 1970.

S. Aviran, C. Trapnell, J. B. Lucks, S. A. Mortimer, S. Luo et al., Modeling and automation of sequencing-based characterization of RNA structure, Proceedings of the National Academy of Sciences, vol.108, issue.27, pp.11069-11074, 2011.
DOI : 10.1073/pnas.1106541108

R. Backofen, D. Tsur, S. Zakov, and M. , Sparse RNA folding: Time and space efficient algorithms, Journal of Discrete Algorithms, vol.9, issue.1, pp.12-31, 2010.
DOI : 10.1016/j.jda.2010.09.001

A. Busch and R. Backofen, INFO-RNA--a fast approach to inverse RNA folding, Bioinformatics, vol.22, issue.15, pp.1823-1831, 2006.
DOI : 10.1093/bioinformatics/btl194

R. Chikhi and G. Rizk, Space-efficient and exact de Bruijn graph representation based on a Bloom filter, Algorithms for Molecular Biology, vol.8, issue.1, p.22, 2013.
DOI : 10.1101/gr.131383.111
URL : https://hal.archives-ouvertes.fr/hal-00753930

Z. Duan, M. Andronescu, K. Schutz, C. Lee, J. Shendure et al., A genome-wide 3C-method for characterizing the three-dimensional architectures of genomes, Methods, vol.58, issue.3, pp.277-288, 2012.
DOI : 10.1016/j.ymeth.2012.06.018

P. Flajolet and R. Sedgewick, Analytic combinatorics, 2009.
DOI : 10.1017/CBO9780511801655
URL : https://hal.archives-ouvertes.fr/inria-00072739

Y. Frid and D. Gusfield, A simple, practical and complete O -time Algorithm for RNA folding using the Four-Russians Speedup, Algorithms for Molecular Biology, vol.36, issue.20, p.13, 2010.
DOI : 10.1093/nar/gkn544

J. A. Garcia-martin, P. Cote, and I. Dotu, RNAiFOLD: A CONSTRAINT PROGRAMMING ALGORITHM FOR RNA INVERSE FOLDING AND MOLECULAR DESIGN, Journal of Bioinformatics and Computational Biology, vol.11, issue.02, p.23600819, 2013.
DOI : 10.1142/S0219720013500017

R. Giegerich and C. Meyer, Algebraic Dynamic Programming, AMAST, pp.349-364, 2002.
DOI : 10.1007/3-540-45719-4_24
URL : https://hal.archives-ouvertes.fr/hal-00857801

R. Giegerich and H. Touzet, Modeling Dynamic Programming Problems over Sequences and Trees with Inverse Coupled Rewrite Systems, Algorithms, vol.7, issue.1, pp.62-144, 2014.
DOI : 10.3390/a7010062
URL : https://hal.archives-ouvertes.fr/hal-01084318

I. L. Hofacker, C. Flamm, C. Heine, M. T. Wolfinger, G. Scheuermann et al., BarMap: RNA folding on dynamic energy landscapes, RNA, vol.16, issue.7, pp.1308-1316, 2010.
DOI : 10.1261/rna.2093310

I. L. Hofacker, W. Fontana, P. Stadler, L. Bonhoeffer, M. Tacker et al., Schnelle Faltung und Vergleich von Sekund???rstrukturen von RNA, Monatshefte f???r Chemie Chemical Monthly, vol.157, issue.2, pp.167-188, 1994.
DOI : 10.1007/BF00818163

F. Lefebvre, An optimized parsing algorithm well suited to RNA folding, ISMB, pp.222-230, 1995.

W. A. Lorenz and P. Clote, Computing the Partition Function for Kinetically Trapped RNA Secondary Structures, PLoS ONE, vol.101, issue.13, p.16178, 2011.
DOI : 10.1371/journal.pone.0016178.t002

R. B. Lyngsø, J. W. Anderson, E. Sizikova, A. Badugu, T. Hyland et al., Frnakenstein: multiple target inverse RNA folding, BMC Bioinformatics, vol.13, issue.1, p.260, 2012.
DOI : 10.1093/nar/gkg068

J. Manuch, C. Thachuk, L. Stacho, and A. Condon, NP-completeness of the energy barrier problem without pseudoknots and temporary arcs, Natural Computing, vol.406, issue.2008, pp.391-405, 2011.
DOI : 10.1007/s11047-010-9239-4

G. Rodrigo, T. E. Landrain, and A. Jaramillo, De novo automated design of small RNA circuits for engineering synthetic riboregulation in living cells, Proceedings of the National Academy of Sciences, vol.109, issue.38, pp.15271-15276, 2012.
DOI : 10.1073/pnas.1203831109

M. Salson, T. Lecroq, M. Léonard, and L. Mouchard, A four-stage algorithm for updating a Burrows???Wheeler transform, Theoretical Computer Science, vol.410, issue.43, pp.4350-4359, 2009.
DOI : 10.1016/j.tcs.2009.07.016
URL : https://hal.archives-ouvertes.fr/hal-00469113

G. Sauthoff, S. Janssen, and R. Giegerich, Bellman's GAP, Proceedings of the 13th international ACM SIGPLAN symposium on Principles and practices of declarative programming, PPDP '11, pp.29-40, 2011.
DOI : 10.1145/2003476.2003484

J. Ule, K. Jensen, A. Mele, and R. B. Darnell, CLIP: A method for identifying protein???RNA interaction sites in living cells, Methods, vol.37, issue.4, pp.376-386, 2005.
DOI : 10.1016/j.ymeth.2005.07.018

J. G. Underwood, A. V. Uzilov, S. Katzman, C. S. Onodera, J. E. Mainzer et al., FragSeq: transcriptome-wide RNA structure probing using high-throughput sequencing, Nature Methods, vol.5, issue.12, pp.995-1001, 2010.
DOI : 10.1038/nmeth.1529

L. G. Valiant, General context-free recognition in less than cubic time, Journal of Computer and System Sciences, vol.10, issue.2, pp.308-314, 1975.
DOI : 10.1016/S0022-0000(75)80046-8

M. S. Waterman and T. F. Smith, RNA secondary structure: a complete mathematical analysis, Mathematical Biosciences, vol.42, issue.3-4, pp.257-266, 1978.
DOI : 10.1016/0025-5564(78)90099-8

K. Wetterstrand, DNA sequencing cost : Data from the NHGRI genome sequencing program (GSP), 2014.

A. Xayaphoummine, T. Bucher, F. Thalmann, and H. Isambert, Prediction and statistics of pseudoknots in RNA structures using exactly clustered stochastic simulations, Proceedings of the National Academy of Sciences, vol.100, issue.26, pp.15310-15315, 2003.
DOI : 10.1073/pnas.2536430100
URL : https://hal.archives-ouvertes.fr/hal-00000641

S. Zakov, D. Tsur, and M. Ziv-ukelson, Reducing the worst case running times of a family of RNA and CFG problems, using Valiant's approach, Algorithms for Molecular Biology, vol.6, issue.1, p.20, 2011.
DOI : 10.1007/978-3-642-21458-5_37

M. Zuker and D. Sankoff, RNA secondary structures and their prediction, Bulletin of Mathematical Biology, vol.9, issue.Suppl. 2, pp.591-621, 1984.
DOI : 10.1007/BF02459506