Markov Chain-based Sampling for Exploring RNA Secondary Structure under\n the Nearest Neighbor Thermodynamic Model

2020/04/02 by Anna Kirkpatrick, Kirkpatrick, Anna, Kalen Patton +1
Biochemistry, Genetics and Molecular Biology · #60J10 (primary) #Combinatorics (math.CO) #FOS: Mathematics #Protein Structure and Dynamics #RNA Research and Splicing #RNA and protein synthesis mechanisms #Statistics Theory (math.ST)

paper · pdf · doi:10.48550/arxiv.2004.01089

openalex publication_date 2020/04/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We study plane trees as a model for RNA secondary structure, assigning energy\nto each tree based on the Nearest Neighbor Thermodynamic Model, and defining a\ncorresponding Gibbs distribution on the trees. Through a bijection between\nplane trees and 2-Motzkin paths, we design a Markov chain converging to the\nGibbs distribution, and establish fast mixing time results by estimating the\nspectral gap of the chain. The spectral gap estimate is established through a\nseries of decompositions of the chain and also by building on known mixing time\nresults for other chains on Dyck paths. In addition to the mathematical aspects\nof the result, the resulting algorithm can be used as a tool for exploring the\nbranching structure of RNA and its dependence on energy model parameters. The\npseudocode implementing the Markov chain is provided in an appendix.\n

Related

• An Efficient Algorithm for Exploring RNA Branching Conformations under the Nearest-Neighbor Thermodynamic Model
• RNA Secondary Structures: Complex Statics and Glassy Dynamics
• On the structure of RNA branching polytopes
• On the Asymptotic Distributions of Classes of Subtree Additive Properties of Plane Trees under the Nearest Neighbor Thermodynamic Model
• Kinetic metric for basins of attraction of RNA secondary structures and analysis of the ultrametricity of the energy landscape