Methods for Analyzing RNA Pseudoknots via Chord Diagrams and Intersection Graphs

Rayan Ibrahim and Allison H. Moore · 2025

Read Methods for Analyzing RNA Pseudoknots via Chord Diagrams and Intersection Graphs by Rayan Ibrahim and Allison H. Moore (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2512-19939.txt.

Introduction

Rayan Ibrahim and Allison Moore give RNA pseudoknots a graph-based yardstick. RNA strands fold into complex shapes. Pseudoknots form when paired parts interleave. They resist strict counting and sorting. Chord diagrams picture such shapes, with arcs for paired bases. The method builds the diagram's intersection graph. It adds a distance-based metric on that graph.

In this frame, a pseudoknot gets a formal definition. It rests on a weighted vertex cover of the graph, built from a split of the diagram. The method yields a strict algorithm. It counts pseudoknots and sorts secondary structures. It stays alert to three-dimensional traits as well. The code runs in MATLAB. Tests used structures from the bpRNA-1m database. They confirmed that genus is a robust gauge of pseudoknot complexity.

Catalog record

CREATORRayan Ibrahim and Allison H. Moore
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE50 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2512-19939

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Methods for Analyzing RNA Pseudoknots via Chord Diagrams and Intersection Graphs Rayan Ibrahim and Allison H. Moore Abstract . RNA molecules are known to form complex secondary structures including pseudoknots. A systematic framework for the enumeration, classification and prediction of secondary structures is critical to determine the biological significance of the molecular configurations of RNA. Chord diagrams are mathematical objects widely used to represent RNA secondary structures and to analyze structural motifs, however a mathematically rigorous enumeration of pseudoknots remains a challenge. We introduce a method that incorporates a distance-based metric τ \tau to analyze the intersection graph of a chord diagram associated with a pseudoknotted structure. In particular, our method formally defines a pseudoknot in terms of a weighted vertex cover of a certain intersection graph constructed from a partition of the chord diagram representing the nucleotide sequence of the RNA molecule. In this graph-theoretic context, we introduce a rigorous algorithm that enumerates pseudoknots, classifies secondary structures, and is sensitive to three-dimensional topological features. We implement our methods in MATLAB and test the algorithm on pseudoknotted structures from the bpRNA-1m database. Our findings confirm that genus is a robust quantifier of pseudoknot complexity. 1. Introduction Ribonucleic acid (RNA) is a molecule essential to many functions of life, notably gene expression, cellular communication, and the storage and transfer of genetic information. The primary structure of RNA refers to the sequence of its four nitrogenous bases adenine (A), guanine (G), cytosine (C), and uracil (U), attached along a sugar-phosphate backbone [ 14 ] . It is well known that RNA molecules fold into a variety of secondary and tertiary structures related to their natural functions via complementary Watson-Crick base pairings and other pairings [ 36 , 14 ] . Common secondary structure motifs include hairpin loops, stems (i.e. ‘stacks’), bulges, interior loops, multiloops, single-stranded regions, and pseudoknots [ 22 ] , [ 12 , Figure 1] (see Figure 4 ). A pseudoknot is a secondary structure motif representing a three-dimensional folding pattern. Pseudoknots were first recognized in the study of the turnip yellow mosaic virus [ 24 , 13 ] , but the term was coined in [ 31 ] . The simplest type of pseudoknotted structure is an H-type pseudoknot, formed when nucleobases along the loop of a hairpin bond with nucleobases elsewhere along the sequence [ 6 ] . A variety of pseudoknot motifs have been characterized including H-type, K-type, L-type, and M-type motifs [ 18 , 1 ] . RNA secondary structures may be represented graphically with chord diagrams , objects common in enumerative combinatorics and topology. In the representation of an RNA secondary structure, bonded pairs are indicated by arcs (‘chords’) along a line segment or circle. A precursor to a chord diagram representing secondary structures appears in [ 33 ] as a connection to predictive models using base-pairing matrices [ 32 ] . There, RNA secondary structures were defined as simple planar graphs on a set of n labeled points such that a path along the n points represents the primary structure, with other edges representing bonds between bases [ 33 , Definition 2.1] . These planar graphs correspond to crossingless chord diagrams, which have since been studied extensively as models for secondary structures [ 5 , 23 , 35 , 34 , 21 , 26 ] . Pseudoknots occur only when the corresponding chord diagrams contain chords that cross each other. Despite the relative simplicity of a chord diagram, there is no greed-upon method for quantifying the complexity of RNA pseudoknotting. A naive count of crossings overemphasizes contributions from helical stacking, and different methods for reducing parallel bonds may yield different enumerations of pseudoknots. Moreover, existing methods may ignore some topological features of the 3D conformation. We investigate these discrepancies in Sections 2.2 and 3.1 . Our goal is to construct a mathematically rigorous and topologically robust framework for quantifying pseudoknot complexity in RNA, presented in the familiar language of graph theory and building upon conventions implicitly assumed in the bpRNA method [ 12 ] and bpRNA-1m database [ 11 ] . The bpRNA-1m database aggregates over 100K RNA secondary structures from seven sources [ 9 , 37 , 25 , 17 , 8 , 15 , 3 ] . Internal annotation routines and the enumeration of pseudoknots and other structural motifs are conducted via the algorithmic tool bpRNA [ 12 ] . This database provides the primary test case for our graph-theoretic procedures. The strategy presented here verifies the reproducibility of both our methods and those of the bpRNA tool [ 12 ] , while illustrating discrepancies resulting from topological conformations. Section 2 develops a mathematical formulation of pseudoknotting using chord diagrams and intersection graphs. The relevant graph theoretical background is reviewed in Section 2.1 , and we prove a relationship between vertex cover numbers and the genus of a chord diagram in Theorem 2.6 . In Section 2.2 , we investigate precedent theories of pseudoknotting and convey these notions into our mathematical framework. Specifically, we use a weighted vertex cover of an intersection graph constructed from a partition of the chord diagram corresponding to an RNA molecule to give a precise enumeration of pseudoknots. In Section 3 , we introduce the \tau -reduction algorithm , which systematically reduces the complexity of a chord diagram to quantify pseudoknots in a robust manner that takes into account 3D topological features, including nestings, crossings, and a distance-based threshold \tau . An explicit MATLAB implementation of our algorithm is provided in Github [ 16 ] . Examples 2.11 and 2.12 in this section demonstrate discrepancies in the existing methodology that are corrected by our current methods. In Section 4 we present the results of our analyses. We report quantities of pseudoknots, improving upon previous methods. In [ 5 ] it was shown that these basic motifs constitute the irreducible pseudoknots of genus equal to one (see Section 4.3 for a discussion on genus). Moreover, they posit that the topological genus of a chord diagram provides a classification of RNA secondary structures with pseudoknots. Our analysis in Section 4.3 together with Theorem 2.6 confirms that even with additional topological considerations, genus is a robust classifier of pseudoknot complexity. 2. Combinatorial Theory 2.1. Chord Diagrams A linear chord diagram D is a set of n points on an oriented line segment together with a (partial) matching of the points. Circular chord diagrams are obtained by joining the endpoints of the segment; however we will restrict to linear chord diagrams throughout. We denote chords as pairs c=(\ell,r) , where \ell and r denote left and right endpoints, respectively. Because chord diagrams are matchings, \ell<r , and no two chords share an endpoint. By convention, a set of chords is indexed by left endpoints. Definition 2.1 . For any two chords c_{1} and c_{2} , there are three possibilities: (a) c_{1} and c_{2} form a crossing : \ell_{1}<\ell_{2}<r_{1}<r_{2} . (b) c_{1} and c_{2} form a nesting : \ell_{1}<\ell_{2}<r_{2}<r_{1} . (c) c_{1} and c_{2} are independent : \ell_{1}<r_{1}<\ell_{2}<r_{2} . Further, a k -crossing is a set of chords (\ell_{1},r_{1}),(\ell_{2},r_{2}),\dots,(\ell_{k},r_{k}) such that \ell_{1}<\ell_{2}<\cdots<\ell_{k}<r_{1}<r_{2}<\cdots<r_{k} . A k -nesting is a set of chords (\ell_{1},r_{1}),(\ell_{2},r_{2}),\dots,(\ell_{k},r_{k}) such that \ell_{1}<\ell_{2}<\cdots<\ell_{k}<r_{k}<r_{k-1}<\cdots<r_{1} . Figure 1. Top left: A 3

Read the complete text