Canonical RNA Pseudoknot Structures
- 1 December 2008
- journal article
- research article
- Published by Mary Ann Liebert Inc in Journal of Computational Biology
- Vol. 15 (10) , 1257-1273
- https://doi.org/10.1089/cmb.2008.0121
Abstract
In this paper, we study k-noncrossing, σ-canonical RNA pseudoknot structures with minimum arc-length greater or equal to four. Let Tk, σ[4] (n) denote the number of these structures. We derive exact enumeration results by computing the generating function Tk, σ[4] (z) = ∑n Tk, σ[4] (n)zn and derive the asymptotic formulas Tk, 3[4] (n) ∼ ck n−(k−1)2−(k−1/2) (γk, 3[4])−n for k = 3, …, 9. In particular, we have for k = 3, T3, 3[4] (n) ∼ c3 n−5 2.0348n. Our results show that the set of biophysically relevant RNA pseudoknot structures is surprisingly small and suggest a new structure class as target for prediction algorithms.Keywords
All Related Versions
This publication has 18 references indexed in Scilit:
- Pseudoknot RNA Structures with Arc-Length ≥4Journal of Computational Biology, 2008
- Assessing the Exceptionality of Network MotifsJournal of Computational Biology, 2008
- Crossings and nestings of matchings and partitionsTransactions of the American Mathematical Society, 2006
- Dynamic programming algorithms for RNA secondary structure prediction with pseudoknotsDiscrete Applied Mathematics, 2000
- A dynamic programming algorithm for RNA structure prediction including pseudoknots 1 1Edited by I. TinocoJournal of Molecular Biology, 1999
- Tree adjoining grammars for RNA structure predictionTheoretical Computer Science, 1999
- Random Walk in a Weyl ChamberProceedings of the American Mathematical Society, 1992
- A holonomic systems approach to special functions identitiesJournal of Computational and Applied Mathematics, 1990
- Rapid dynamic programming algorithms for RNA secondary structureAdvances in Applied Mathematics, 1986
- Differentiably Finite Power SeriesEuropean Journal of Combinatorics, 1980