ExpaRNA-P: simultaneous exact pattern matching and folding of RNAs

Abstract

Background: Identifying sequence-structure motifs common to two RNAs can speed up the comparison of structural RNAs substantially. The core algorithm of the existent approach ExpaRNA solves this problem for a priori known input structures. However, such structures are rarely known; moreover, predicting them computationally is no rescue, since single sequence structure prediction is highly unreliable.

Results: The novel algorithm ExpaRNA-P computes exactly matching sequence-structure motifs in entire Boltzmann-distributed structure ensembles of two RNAs; thereby we match and fold RNAs simultaneously, analogous to the well-known "simultaneous alignment and folding" of RNAs. While this implies much higher flexibility compared to ExpaRNA, ExpaRNA-P has the same very low complexity (quadratic in time and space), which is enabled by its novel structure ensemble-based sparsification. Furthermore, we devise a generalized chaining algorithm to compute compatible subsets of ExpaRNA-P's sequence-structure motifs. Resulting in the very fast RNA alignment approach ExpLoc-P, we utilize the best chain as anchor constraints for the sequence-structure alignment tool LocARNA. ExpLoc-P is benchmarked in several variants and versus state-of-the-art approaches. In particular, we formally introduce and evaluate strict and relaxed variants of the problem; the latter makes the approach sensitive to compensatory mutations. Across a benchmark set of typical non-coding RNAs, ExpLoc-P has similar accuracy to LocARNA but is four times faster (in both variants), while it achieves a speed-up over 30-fold for the longest benchmark sequences (≈400nt). Finally, different ExpLoc-P variants enable tailoring of the method to specific application scenarios. ExpaRNA-P and ExpLoc-P are distributed as part of the LocARNA package. The source code is freely available at http://www.bioinf.uni-freiburg.de/Software/ExpaRNA-P .

Conclusions: ExpaRNA-P's novel ensemble-based sparsification reduces its complexity to quadratic time and space. Thereby, ExpaRNA-P significantly speeds up sequence-structure alignment while maintaining the alignment quality. Different ExpaRNA-P variants support a wide range of applications.

Figure 1

The ExpLoc-P pipeline. Using EPMs as anchor constraints to speed up RNA structure alignments.

Figure 2

Visualization of the pattern matching definition. Two different illustrations of the notion pattern matching are shown in (A) and (B). For the light gray pattern matching, we have $\mathcal{ℳ}=\{2\sim 2,3\sim 3,9\sim 13,10\sim 14,11\sim 15\}$ and $\mathcal{S}=\left\{\right(2,11\sim 2,15),(3,10\sim 3,14\left)\right\}$. Note that the two separated regions in both sequences are connected through base pairs. Furthermore, the set of structure matches is $\mathcal{ℳ}{|}_{\mathcal{S}}=\{2\sim 2,3\sim 3,10\sim 14,11\sim 15\}$ and the set of sequence matches is $\mathcal{ℳ}\setminus \mathcal{ℳ}{|}_{\mathcal{S}}=\{9\sim 13\}$. The pattern matching can be extended by the base pair match shown in dark gray, i.e., ${\mathcal{ℳ}}^{\prime }=\mathcal{ℳ}\cup \{1\sim 1,12\sim 16\}$ and ${\mathcal{S}}^{\prime }=\mathcal{S}\cup \left\{\right(1,12\sim 1,16\left)\right\}$. $(\mathcal{ℳ},\mathcal{S})$, the EPM shown in light gray, is a strict EPM, whereas $({\mathcal{ℳ}}^{\prime },{\mathcal{S}}^{\prime })$, the EPM extended by the dark gray part, is a relaxed EPM as mismatches in structure matches occur. (C) shows an example of an invalid matching. Separately, both the small and the big matched gray parts are valid EPMs, but together they do not form a valid EPM as the two individual parts are not connected.

Figure 3

Visualization of maximal EPMs. Matches of green bases refer to exact matches and red ones to inexact (structure) matches. (A-C) EPM A is not maximal since there exists a larger (strict) EPM (B or C). EPMs B and C can be maximal simultaneously since in each case some base matches have different parents. (A and D-F) EPM D is generated from A by appending an inexact structure match and has a lower score than A. Further extending the EPM leads to higher scores again (E and F). D is not maximal since A has the same parents and a higher score. A is not maximal because there exist (relaxed) EPMs E and F with the same parents and higher scores. Among A, D, E, and F, only F is maximal.

Figure 4

Recursion equations. Recursions for computing the significant strict EPMs and relaxed EPMs, respectively. These equations are visualized in Figure 5.

Figure 5

Recursion visualization. Visualization of the recursions to compute the matrix entries $L^{\mathit{\text{ijkl}}}(j^{\prime },l^{\prime }),G_{\text{A}}^{\mathit{\text{ijkl}}}(j^{\prime },l^{\prime }),G_{\text{AB}}^{\mathit{\text{ijkl}}}(j^{\prime },l^{\prime }),L{R}^{\mathit{\text{ijkl}}}(j^{\prime },l^{\prime }),D(\mathit{\text{ij}},\mathit{\text{kl}}),F(j^{\prime },l^{\prime })$ and the auxiliary matrix H ^ijkl(j ^′,l ^′).

Figure 6

Comparison of ExpLoc-P variants. (A) Alignment quality (SPS) vs. sequence identity. (B) Coverage vs. sequence identity. Dependencies are visualized as LOWESS curves.

Figure 7

Comparison with sequence-structure alignment methods. (A) Comparison of alignment quality vs. sequence identity. (B) Comparison of speedup over LocARNA vs. length (LOWESS).