The rainbow spectrum of RNA secondary structures

DOI10.1007/S11538-018-0411-9MaRDI QIDQ1670472zbMATH OpenOpenAlexWikidataFDO

Authors Thomas J. X. Li, Christian M. Reidys

Publication date 5 September 2018

Published in Bulletin of Mathematical Biology (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1806.03333

zbMATH Keywords

arcgapgenerating functionlength spectrumrainbowsecondary structuresingularity analysis

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Protein sequences, DNA sequences (92D20)

Abstract: In this paper we analyze the length-spectrum of rainbows in RNA secondary structures. A rainbow in a secondary structure is a maximal arc with respect to the partial order induced by nesting. We show that there is a significant gap in this length-spectrum. We shall prove that there asymptotically almost surely exists a unique longest rainbow of length at least $n-O(n^{1/2})$ and that with high probability any other rainbow has finite length. We show that the distribution of the length of the longest rainbow converges to a discrete limit law and that, for finite $k$, the distribution of rainbows of length $k$, becomes for large $n$ a negative binomial distribution. We then put the results of this paper into context, comparing the analytical results with those observed in RNA minimum free energy structures, biological RNA structures and relate our findings to the sparsification of folding algorithms.

Recommendations

• The block spectrum of RNA pseudoknot structures
• Asymptotic enumeration of RNA secondary structure
• General combinatorics of RNA secondary structure
• Asymptotic expected number of base pairs in optimal secondary structure for random RNA using the Nussinov--Jacobson energy model
• Asymptotic number of hairpins of saturated RNA secondary structures

Cites work

• A Study of Accessible Motifs and RNA Folding Complexity
• Analytic combinatorics
• Combinatorics of RNA Hairpins and Cloverleaves
• Combinatorics of RNA secondary structures
• Computation of Generating Functions for Biological Molecules
• Expected distance between terminal nucleotides of RNA secondary structures
• scientific article; zbMATH DE number 3675903 (Why is no real title available?)
• scientific article; zbMATH DE number 718142 (Why is no real title available?)
• Irreducibility in RNA structures
• Linear trees and RNA secondary structure
• On finding all suboptimal foldings of an RNA molecule
• On some new sequences generalizing the Catalan and Motzkin numbers
• On the decomposition of \(k\)-noncrossing RNA structures
• Rapid dynamic programming algorithms for RNA secondary structure
• RNA secondary structure: a complete mathematical analysis
• RNA secondary structures and their prediction
• Spaces of RNA secondary structures
• Sparse RNA folding: time and space efficient algorithms

Cited in

(3)

• Improving RNA secondary structure prediction via state inference with deep recurrent neural networks
• The block spectrum of RNA pseudoknot structures
• Combinatorics on the joint distribution of hairpins and stacks in RNA secondary structures

Describes a project that uses

Uses Software

• ViennaRNA
• RNAsubopt
• RNAfold
• PseudoViewer3

This page was built for publication: The rainbow spectrum of RNA secondary structures

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1670472)