ExpaRNA-P

ExpaRNA-P identifies matching sequence-structure motifs between two RNA sequences by computing matches within Boltzmann-distributed structure ensembles without requiring predetermined structures.

Key Features:

• Sequence-structure motif computation: Computes matching sequence-structure motifs within Boltzmann-distributed structure ensembles of RNA sequences.
• Simultaneous match-and-fold: Simultaneously matches and folds RNAs using a simultaneous alignment-and-folding approach.
• Computational complexity: Operates with quadratic time and space complexity in input length.
• Structure ensemble-based sparsification: Employs structure ensemble-based sparsification to reduce computational effort.
• Generalized chaining algorithm: Uses a generalized chaining algorithm to compute compatible subsets of sequence-structure motifs.
• Integration with ExpLoc-P and LocARNA: Provides the best chain as anchor constraints for ExpLoc-P, which are used within LocARNA alignments.
• Problem variants: Supports strict and relaxed problem variants, with the relaxed variant sensitive to compensatory mutations.
• Benchmark performance: Benchmarked on typical non-coding RNAs, showing similar accuracy to LocARNA with approximately fourfold speed-up across variants and over 30-fold speed-up for sequences around 400 nucleotides.

Scientific Applications:

• Sequence-structure motif identification: Detects common sequence-structure motifs between pairs of RNA sequences.
• Comparative RNA alignment: Anchors sequence-structure alignments in LocARNA via chains computed by ExpaRNA-P (ExpLoc-P).
• Non-coding RNA analysis: Accelerates comparative analyses of typical non-coding RNAs, including sequences up to ~400 nucleotides.
• Compensatory mutation sensitivity: Uses the relaxed variant to identify motifs that reflect compensatory mutations.

Methodology:

Computes matching motifs within Boltzmann-distributed structure ensembles by simultaneously matching and folding RNAs, applies structure ensemble-based sparsification, uses a generalized chaining algorithm to obtain compatible motif subsets, and supplies the best chain as anchor constraints for ExpLoc-P within LocARNA.