Random k-noncrossing RNA structures

DOI10.1073/PNAS.0907269106zbMATH Open1203.92026arXiv0906.5553OpenAlexW1999118179WikidataQ33564149 ScholiaQ33564149MaRDI QIDQ3069233FDOQ3069233

Authors: William Y. C. Chen, Hillary S. W. Han, Christian M. Reidys 

Publication date: 24 January 2011

Published in: Proceedings of the National Academy of Sciences (Search for Journal in Brave)

Abstract: In this paper we derive polynomial time algorithms that generate random $k$-noncrossing matchings and $k$-noncrossing RNA structures with uniform probability. Our approach employs the bijection between $k$-noncrossing matchings and oscillating tableaux and the $P$-recursiveness of the cardinalities of $k$-noncrossing matchings. The main idea is to consider the tableaux sequences as paths of stochastic processes over shapes and to derive their transition probabilities.

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

Recommendations

• Combinatorics of RNA structures with pseudoknots
• Combinatorial design of pseudoknot RNA
• Generation of RNA pseudoknot structures with topological genus filtration
• RNA pseudoknot structures with arc-length \(\geq 3\) and stack-length \(\geq \sigma \)
• Central and local limit theorems for RNA structures

Mathematics Subject Classification ID

Biochemistry, molecular biology (92C40) Markov processes (60J99)

Cites Work

• GFUN
• Random generation of combinatorial structures from a uniform distribution
• Differentiably finite power series
• A holonomic systems approach to special functions identities
• On the Vector Representations of Induced Matroids
• Fast uniform generation of regular graphs
• A unified setting for sequencing, ranking, and selection algorithms for combinatorial objects
• Combinatorics of RNA structures with pseudoknots
• Random walks in Weyl chambers and the decomposition of tensor powers
• RNA structures with pseudo-knots: graph-theoretical, combinatorial, and statistical properties
• Algorithms for Loop Matchings
• Boltzmann Samplers for the Random Generation of Combinatorial Structures
• Proportions of Irreducible Diagrams
• Combinatorics of RNA Hairpins and Cloverleaves
• Standard Young tableaux of height 4 and 5
• Predicting RNA secondary structures with pseudoknots by MCMC sampling
• Coexistence of multiple codes in messenger RNA molecules

Cited In (9)

• Generation of RNA pseudoknot structures with topological genus filtration
• Reappraising the distribution of the number of edge crossings of graphs on a sphere
• Edge crossings in random linear arrangements
• Posets and spaces of \(k\)-noncrossing RNA structures
• A generating tree approach to \(k\)-nonnesting partitions and permutations
• On the page number of RNA secondary structures with pseudoknots
• Efficient sampling of RNA secondary structures from the Boltzmann ensemble of low-energy
• Symmetric circular matchings and RNA folding
• RNA secondary structures with given motif specification: combinatorics and algorithms

This page was built for publication: Random \(k\)-noncrossing RNA structures

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