Phase transition in random planar diagrams and RNA-type matching

Andrey Y. Lokhov, Olga Valba, M. Tamm, Sergei NechaevPhysical 2013 · DOI · arXiv

Abstract

We study the planar matching problem, defined by a symmetric random matrix with independent identically distributed entries, taking values zero and one. We show that the existence of a perfect planar matching structure is possible only above a certain critical density, $p_c$, of allowed contacts. Using a formulation of the problem in terms of Dyck paths and a matrix model of planar contact structures, we provide an analytical estimation for the value of the transition point, $p_c$, in the thermodynamic limit. This estimation is close to the critical value, $p_c \approx 0.379$, obtained in numerical simulations based on an exact dynamical programming algorithm. We characterize the corresponding critical behavior of the model and discuss the relation of the perfect-imperfect matching transition to the known molten-glass transition in the context of random RNA secondary structure formation. In particular, we provide strong evidence supporting the conjecture that the molten-glass transition at $T=0$ occurs at $p_c$.

Introduction

The planar matching problem involves connecting $L$ points on a line in pairs using $L/2$ links under two primary constraints: planarity and admissibility. Planarity requires that no two links cross, a topological constraint common in RNA secondary structure folding where pseudoknots are generally avoided. Admissibility is governed by a random matrix $A$, where a link between points $i$ and $j$ is allowed only if $A_{ij}=1$. This problem serves as a classic Constraint Satisfaction Problem (CSP), analogous to the SAT-UNSAT transition. The central question is identifying the critical density $p$ of allowed contacts at which a perfect matching becomes impossible.

Methodology

The researchers employed four distinct analytical and numerical techniques to estimate the critical threshold:

  1. Naive Mean-Field Theory: Assumes independence of planar diagrams, predicting $p_c = 0.25$.
  2. Combinatorial "Corner Counting": Focuses on local "corners" (adjacent links) in Dyck paths, refining the estimate to $p_c \approx 0.35$.
  3. Matrix Field Theory: Utilizes a $1/N$ expansion from quantum field theory to derive a self-consistent propagator equation, yielding $p_c \approx 0.455$.
  4. Numerical Simulations: An exact dynamic programming algorithm (similar to the Nussinov algorithm) was used to find ground states for chain lengths $L$ ranging from 500 to 2000, averaged over 10,000 instances per data point.

Results and Scaling Behavior

Numerical simulations pinpoint the phase transition at $p_c \approx 0.379$. Near this threshold, the fraction of perfect matchings $\eta_L(p)$ exhibits a sharp transition that becomes increasingly vertical as the chain length $L$ increases.

Numerical evidence for the phase transition at $p_c \approx 0.379$ and its scaling collapse.

Scaling analysis reveals that the data collapses onto a single curve when plotted against $(p - p_c)L^\nu$, with a critical exponent $\nu \approx 0.5$. In the perfect phase ($p > p_c$), the number of missing links (gaps) vanishes exponentially with $L$, whereas in the imperfect phase ($p < p_c$), a finite fraction of vertices remains unpaired, following power-law decay.

Discussion: The RNA Connection

The transition at $p_c$ is physically linked to the molten-glass transition in RNA. In the "molten" phase, the structure is flexible and universal, while in the "glassy" phase, the specific sequence disorder dictates a frozen, unique structure.

Phase diagram in the $(p, T)$ plane illustrating the transition from glassy to molten phases and its termination at $p_c$.

The study provides strong evidence that the molten-glass transition curve in the temperature-density $(p, T)$ plane terminates exactly at $p_c$ when the temperature $T = 0$. This identifies $p_c$ as the zero-temperature boundary of the glassy phase, where the lack of allowed contacts prevents the formation of a perfect, stable structure.

Conclusion

This work bridges abstract combinatorics and polymer physics, identifying a critical threshold for perfect planar matching. While analytical approximations vary, numerical results consistently point to $p_c \approx 0.379$. Future work could incorporate more realistic constraints like minimum loop lengths or limited pseudoknots to further refine the model's biological relevance.

Summary updated

Abstract

We study the planar matching problem, defined by a symmetric random matrix with independent identically distributed entries, taking values zero and one. We show that the existence of a perfect planar matching structure is possible only above a certain critical density, p(c), of allowed contacts (i.e., of ones). Using a formulation of the problem in terms of Dyck paths and a matrix model of planar contact structures, we provide an analytical estimation for the value of the transition point, p(c), in the thermodynamic limit. This estimation is close to the critical value, p(c)≈0.379, obtained in numerical simulations based on an exact dynamical programming algorithm. We characterize the corresponding critical behavior of the model and discuss the relation of the perfect-imperfect matching transition to the known molten-glass transition in the context of random RNA secondary structure formation. In particular, we provide strong evidence supporting the conjecture that the molten-glass transition at T=0 occurs at p(c).
BibTeX
@inproceedings{lokhov2013phase,
  author = {Andrey Y. Lokhov and Olga Valba and M. Tamm and Sergei Nechaev},
  title = {{Phase transition in random planar diagrams and RNA-type matching}},
  booktitle = {Physical},
  year = {2013},
  doi = {10.1103/physreve.88.052117},
}
Figure