Bi-alignments as Models of Incongruent Evolution of RNA Sequence and Secondary Structure

Maria Waldl, Sebastian Will, Michael T. Wolfinger, Ivo L. Hofacker, Peter F. StadlerCIBB 2019 · DOI

TL;DR

This paper introduces "bi-alignments," a novel framework to model the evolutionary divergence of RNA sequence and secondary structure. By treating sequence and structure alignments separately and then aligning these alignments, they can capture cases where RNA evolution prioritizes structural integrity over strict sequence homology, a phenomenon observed in real biological data.

What Problem Does This Paper Address?

RNA molecules, crucial for various biological processes, fold into complex 3D structures that are often essential for their function. Traditionally, evolutionary models assume that sequence and structure evolve in lockstep – homologous nucleotides should form homologous base pairs. This "congruent evolution" assumption is the basis for many RNA alignment algorithms, like Sankoff's. However, the authors observe that in some cases, RNA structures can be preserved even if the underlying sequences change significantly, leading to analogous base pairs formed by non-homologous nucleotides. This "incongruent evolution" poses a challenge for existing alignment methods, which might misinterpret these structural shifts or overpredict base pair changes. The paper aims to develop a computational framework that can accurately model and detect this incongruent evolution.

Methods

The core innovation is the concept of bi-alignments. A bi-alignment consists of three components:

  1. U: An alignment representing sequence homology between two RNA sequences.
  2. V: An alignment representing structural homology (analogous base pairs) between the same two RNA sequences.
  3. W: An alignment of U and V, which captures the relative shifts between conserved sequence and conserved structure.

Essentially, a bi-alignment can be viewed as a four-way alignment. The scoring function for a bi-alignment separately scores the sequence alignment (U) and the structure alignment (V), and then penalizes "shifts" detected in W. Shifts occur when the gap patterns in U and V differ for a given column, indicating a misalignment between sequence and structure. The authors propose a dynamic programming approach to optimize this scoring function. They also discuss generalizations to "poly-alignments" for comparing multiple structures or multiple types of alignments.

Datasets

The authors use the Rfam database (specifically Rfam 14.1) as their primary dataset. They compare Rfam's curated seed alignments with re-alignments generated by MAFFT. This comparison allows them to identify families where the sequence and structure alignments significantly disagree, suggesting incongruent evolution. They also mention using a subset of 1181 families from Rfam with small to medium-sized alignments for their survey.

Key Insights and Ideas

  • Incongruent evolution is real and common: Their survey of Rfam suggests that incongruent evolution is not a rare phenomenon, affecting a notable percentage of structured ncRNA families.
  • Bi-alignments offer a more accurate model: By decoupling sequence and structure alignment, bi-alignments can better capture evolutionary scenarios where structure is conserved despite sequence divergence.
  • Shifts are key indicators: The "shift" penalty in bi-alignments is crucial for quantifying the degree of incongruence between sequence and structure evolution.
  • Existing methods have limitations: Standard RNA alignment algorithms that assume congruent evolution may fail to accurately represent families exhibiting incongruent evolution, potentially leading to misinterpretations of evolutionary history and base pair dynamics.

Key Results

  • Their survey of Rfam identified 709 cases where Rfam alignments differed from MAFFT re-alignments, indicating potential incongruent evolution.
  • Using their bi-alignment algorithm, they found 143 cases with at least one evolutionary shift event across 72 different Rfam families, suggesting plausible evolutionary shift events.
  • They developed and provide a Python implementation of their bi-alignment algorithm called BiAlign, which is freely available.

Limitations and Future Work

  • Parameter tuning: The authors acknowledge that they used "ad hoc" parameters for base similarities, indel, and shift costs. They suggest that training a more realistic scoring model, potentially using probabilistic methods and empirical data, would be beneficial.
  • Structure approximation: The current structure-based alignment models are based on a simplified scoring function that approximates structure similarity. More powerful RNA structure alignment approaches, potentially incorporating context-free grammar rules (like Sankoff's algorithm), could be explored for greater accuracy.
  • Generalization to other molecules: The authors suggest investigating whether similar phenomena can be detected in proteins at the level of secondary structures.
  • Further exploration of Sankoff-style bi-alignments: They mention that Sankoff-style bi-alignments, which integrate sequence and structure more deeply, will be detailed in a forthcoming contribution.

Summary updated

BibTeX
@inproceedings{waldl2019bi,
  author = {Maria Waldl and Sebastian Will and Michael T. Wolfinger and Ivo L. Hofacker and Peter F. Stadler},
  title = {{Bi-alignments as Models of Incongruent Evolution of RNA Sequence and Secondary Structure}},
  booktitle = {CIBB},
  year = {2019},
  doi = {10.1007/978-3-030-63061-4\_15},
}
Figure