Random k-noncrossing RNA structures

DOI10.1073/PNAS.0907269106MaRDI QIDQ3069233zbMATH OpenOpenAlexWikidataFDO

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)

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

Mathematics Subject Classification ID

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

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.

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

Cites work

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

Cited in

(11)

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

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)