S. F. Altschul and B. W. Erickson, Significance of nucleotide sequence alignments: a method for random sequence permutation that preserves dinucleotide and codon usage, Molecular biology and evolution, vol.2, issue.6, pp.526-564, 1985.

P. Clote, An Efficient Algorithm to Compute the Landscape of Locally Optimal RNA Secondary Structures with Respect to the Nussinov???Jacobson Energy Model, Journal of Computational Biology, vol.12, issue.1, pp.83-101, 2005.
DOI : 10.1089/cmb.2005.12.83

P. Clote, RNALOSS: a web server for RNA locally optimal secondary structures, Nucleic Acids Research, vol.33, issue.Web Server, pp.600-604, 2005.
DOI : 10.1093/nar/gki382

S. R. Eddy, How do RNA folding algorithms work?, Nature Biotechnology, vol.22, issue.11, pp.1457-1458, 2004.
DOI : 10.1016/S0959-440X(00)00088-9

D. J. Evers and R. Giegerich, Reducing the Conformation Space in RNA Structure Prediction, 2001.

P. P. Gardner, J. Daub, J. G. Tate, E. P. Nawrocki, D. L. Kolbe et al., Rfam: updates to the RNA families database, Nucleic Acids Research, vol.37, issue.Database, pp.136-140, 2009.
DOI : 10.1093/nar/gkn766

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

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

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

N. R. Markham and M. Zuker, UNAFold, Bioinformatics: Structure, Function and Applications, vol.453, pp.3-31, 2008.
DOI : 10.1007/978-1-60327-429-6_1

D. H. Matthews, J. Sabrina, 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. Mattick and I. V. Makunin, Non-coding RNA, Human Molecular Genetics, vol.15, issue.90001, pp.17-29, 2006.
DOI : 10.1093/hmg/ddl046

J. Moon and L. Moser, On cliques in graphs, Israel Journal of Mathematics, vol.3, issue.1, pp.23-28, 1965.
DOI : 10.1007/BF02760024

R. Nussinov and A. B. Jacobson, Fast algorithm for predicting the secondary structure of singlestranded RNA, Proc. Nat. Acad. Sci. USA, pp.77-6309, 1980.

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

P. Steffen, B. Voss, M. Rehmsmeier, J. Reeder, and R. Giegerich, RNAshapes: an integrated RNA analysis package based on abstract shapes, Bioinformatics, vol.22, issue.4, pp.500-503, 2006.
DOI : 10.1093/bioinformatics/btk010

B. Voss, C. Meyer, and R. Giegerich, Evaluating the predictability of conformational switching in RNA, Bioinformatics, vol.20, issue.10, pp.1573-1582, 2004.
DOI : 10.1093/bioinformatics/bth129

R. Walczak, E. Westhof, P. , P. Carbon, and A. Krol, A novel RNA structural motif in the selenocysteine insertion element of eukaryotic selenoprotein mRNAs, RNA, vol.2, pp.367-379, 1996.

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

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

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 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

. Proof, We first establish that for all i and j, all elements of MJ(i, j) are structures maximal for juxtaposition . The proof is by recurrence on j ? i

?. If-i, MJ(i, j) contains only the empty structure ?, and this structure is locally optimal

?. If and =. , Definition 3 implies that S is maximal for juxtaposition on BP[y+1..j]. Thus S is in MJ(y+1, j) by recurrence hypothesis. Then rule (3a) applies and S is in MJ(i, j)

?. If and >. , Moreover, it is maximal for juxtaposition on BP[i + 1..j] by Definition 3. So, by recurrence hypothesis, S is in MJ(i + 1, j) It remains to show that it is transferred to MJ(i, j) If no base pair of BP starts at position i, then rule (2) applies, and S is also in MJ(i, j) If not, consider any base pair of the form (i, y) in BP. Since x > i, (i, y) does not belong to S. As S is maximal for juxtaposition on BP[i, BP[i + 1

. Lemma-3, Given a structure S in MJ(i, j), let b be the first base pair of S not nested in b. S belongs to Filter (b, MJ(i, j)) if, and only if, such a b exists and is conflicting with b