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. ,
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
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
How do RNA folding algorithms work?, Nature Biotechnology, vol.22, issue.11, pp.1457-1458, 2004. ,
DOI : 10.1016/S0959-440X(00)00088-9
Reducing the Conformation Space in RNA Structure Prediction, 2001. ,
Rfam: updates to the RNA families database, Nucleic Acids Research, vol.37, issue.Database, pp.136-140, 2009. ,
DOI : 10.1093/nar/gkn766
Schnelle Faltung und Vergleich von Sekund???rstrukturen von RNA, Monatshefte f. Chemie, pp.167-188, 1994. ,
DOI : 10.1007/BF00818163
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
Computing the Partition Function for Kinetically Trapped RNA Secondary Structures, PLoS ONE, vol.101, issue.13, 2011. ,
DOI : 10.1371/journal.pone.0016178.t002
UNAFold, Bioinformatics: Structure, Function and Applications, vol.453, pp.3-31, 2008. ,
DOI : 10.1007/978-1-60327-429-6_1
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
Non-coding RNA, Human Molecular Genetics, vol.15, issue.90001, pp.17-29, 2006. ,
DOI : 10.1093/hmg/ddl046
On cliques in graphs, Israel Journal of Mathematics, vol.3, issue.1, pp.23-28, 1965. ,
DOI : 10.1007/BF02760024
Fast algorithm for predicting the secondary structure of singlestranded RNA, Proc. Nat. Acad. Sci. USA, pp.77-6309, 1980. ,
Algorithms for Loop Matchings, SIAM Journal on Applied Mathematics, vol.35, issue.1, pp.68-82, 1978. ,
DOI : 10.1137/0135006
RNAshapes: an integrated RNA analysis package based on abstract shapes, Bioinformatics, vol.22, issue.4, pp.500-503, 2006. ,
DOI : 10.1093/bioinformatics/btk010
Evaluating the predictability of conformational switching in RNA, Bioinformatics, vol.20, issue.10, pp.1573-1582, 2004. ,
DOI : 10.1093/bioinformatics/bth129
A novel RNA structural motif in the selenocysteine insertion element of eukaryotic selenoprotein mRNAs, RNA, vol.2, pp.367-379, 1996. ,
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
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
On finding all suboptimal foldings of an RNA molecule, Science, vol.244, issue.4900, pp.48-52, 1989. ,
DOI : 10.1126/science.2468181
RNA secondary structures and their prediction, Bulletin of Mathematical Biology, vol.9, issue.Suppl. 2, pp.591-621, 1984. ,
DOI : 10.1007/BF02459506
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
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 ,
MJ(i, j) contains only the empty structure ?, and this structure is locally optimal ,
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) ,
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 ,
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 ,