Sequence matching algorithms and pairing of noncoding RNAs

Sergei Nechaev, M. Tamm, Olga ValbaarXiv 2010 · DOI · arXiv

Abstract

A new statistical method of alignment of two heteropolymers which can form hierarchical cloverleaf-like secondary structures is proposed. This offers a new constructive algorithm for quantitative determination of binding free energy of two noncoding RNAs with arbitrary primary sequences. The alignment of ncRNAs differs from the complete alignment of two RNA sequences: in ncRNA case we align only the sequences of nucleotides which constitute pairs between two different RNAs, while the secondary structure of each RNA comes into play only by the combinatorial factors affecting the entropic contribution of each molecule to the total cost function. The proposed algorithm is based on two observations: i) the standard alignment problem is considered as a zero-temperature limit of a more general statistical problem of binding of two associating heteropolymer chains; ii) this last problem is generalized onto the sequences with hierarchical cloverleaf-like structures (i.e. of RNA-type). Taking zero-temperature limit at the very end we arrive at the desired "cost function" of the system with account for entropy of side cactus-like loops. Moreover, we have demonstrated in detail how our algorithm enables to solve the "structure recovery" problem. Namely, we can predict in zero-temperature limit the cloverleaf-like (i.e. secondary) structure of interacting ncRNAs by knowing only their primary sequences.

Introduction

Standard sequence alignment tools, such as those used to find the Longest Common Subsequence, typically treat DNA and RNA as linear strings of characters. However, noncoding RNAs (ncRNAs) are biologically active molecules that fold into intricate "cloverleaf" or "cactus-like" secondary structures. These internal folds significantly influence how two ncRNAs interact.

Sequence alignment representation showing matches, mismatches, and gaps corresponding to structural loops.

When two ncRNAs bind, the process is governed not just by primary sequence complementarity but by the entropic cost of their internal folds. A gap in a sequence alignment is not merely a missing nucleotide; it often represents a loop within a complex structure. Existing algorithms frequently fail to balance the energy gained from inter-molecular pairing against the entropic penalty of intra-molecular folding. This research bridges this gap by providing a mathematically rigorous framework to calculate the binding free energy of structured heteropolymers.

Methodology: Alignment as a Physical Process

The proposed approach shifts the paradigm from computer science heuristics to statistical mechanics. The core innovation lies in treating sequence alignment as the zero-temperature limit ($T \to 0$) of a physical binding process between two chains.

Schematic of two interacting heteropolymer chains (chain 1 and chain 2) forming inter-chain contacts and internal loops.

To account for the internal folding of each RNA, the researchers introduced self-consistent "Dyson-type" equations. These equations allow for the calculation of the partition function—a measure of all possible states—for each chain's "cactus-like" topology. This topology includes structures where loops can branch, but "pseudoknots" (crossing arcs) are forbidden to maintain mathematical tractability. The resulting algorithm calculates a "cost function" representing the ground-state free energy. While standard linear alignment runs in $O(mn)$ time, this structural approach requires $O(m^2 \times n^2)$ time, where $m$ and $n$ are the sequence lengths.

Key Insights and Results

The algorithm is "reversible," meaning that once the free energy matrix is calculated, one can work backward to "recover" the most likely secondary structure of the interacting pair. This "structure recovery" was validated using synthetic trial sequences, including short 7-nucleotide pairs and longer 75-nucleotide sequences.

In trials with 75-nucleotide sequences, the cactus-like model identified a ground state energy (total matches) of 51, compared to only 48 found by the linear model. This demonstrates that accounting for internal structure allows the algorithm to discover more optimal pairing configurations that linear searches overlook. Furthermore, statistical analysis of random ensembles showed that structured RNAs are more efficient at finding matches, with a higher scaling coefficient ($k_c \approx 0.92$) for average free energy compared to linear chains ($k_l \approx 0.65$).

Conclusion and Future Directions

While the current model provides a robust framework for ncRNA alignment, it has limitations. The explicit exclusion of pseudoknots, while necessary for tractability, ignores a rare but biologically significant structural feature. Additionally, the $O(m^2n^2)$ computational complexity makes the algorithm better suited for the detailed analysis of specific RNA pairs rather than large-scale genomic searches. Future work may involve refining physical constraints, such as minimal loop lengths, to better match real-world biological data.

Summary updated

Abstract

A new statistical method of alignment of two heteropolymers which can form hierarchical cloverleaf-like secondary structures is proposed. This offers a new constructive algorithm for quantitative determination of binding free energy of two noncoding RNAs with arbitrary primary sequences. The alignment of ncRNAs differs from the complete alignment of two RNA sequences: in ncRNA case we align only the sequences of nucleotides which constitute pairs between two different RNAs, while the secondary structure of each RNA comes into play only by the combinatorial factors affecting the entropc contribution of each molecule to the total cost function. The proposed algorithm is based on two observations: i) the standard alignment problem is considered as a zero-temperature limit of a more general statistical problem of binding of two associating heteropolymer chains; ii) this last problem is generalized onto the sequences with hierarchical cloverleaf-like structures (i.e. of RNA-type). Taking zero-temperature limit at the very end we arrive at the desired "cost function" of the system with account for entropy of side cactus-like loops. Moreover, we have demonstrated in detail how our algorithm enables to solve the "structure recovery" problem. Namely, we can predict in zero-temperature limit the cloverleaf-like (i.e. secondary) structure of interacting ncRNAs by knowing only their primary sequences.
BibTeX
@misc{nechaev2010sequence,
  author = {Sergei Nechaev and M. Tamm and Olga Valba},
  title = {{Sequence matching algorithms and pairing of noncoding RNAs}},
  year = {2010},
  eprint = {1011.2605},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1011.2605},
}

Loading related content...

Figure