Multiple RNA Interaction: Beyond Two

The interaction of two RNA molecules involves a complex interplay between folding and binding that warranted recent developments in RNA-RNA interaction algorithms. However, biological mechanisms in which more than two RNAs take part in an interaction also exist. It is reasonable to believe that interactions involving multiple RNAs are generally more complex to be treated pairwise. In addition, given a pool of RNAs, it is not trivial to predict which RNAs interact without sufficient biological knowledge. Therefore, structures resulting from multiple RNA interactions often cannot be predicted by the existing algorithms that handle RNAs pairwise and may simply favor the best interacting pair. We propose a system for multiple RNA interaction that overcomes the difficulties mentioned above by formulating a combinatorial optimization problem called Pegs and Rubber Bands. A solution to this problem encodes a structure of interacting RNAs. The problem, not surprisingly, is NP-hard. However, our experiments with approximation algorithms and heuristics for the problem suggest that this formulation is adequate to predict known interaction patterns of multiple RNAs. In general, however, the optimal solution obtained does not necessarily correspond to the actual structure observed in biological experiments. Moreover, a structure produced by interacting RNAs may not be unique. We extend our approach to generate multiple suboptimal solutions. By clustering these solutions, we are able to reveal representatives that correspond to realistic structures. Specifically, our results on the U2-U6 complex with introns in the spliceosome of human/yeast and the CopA-CopT complex in E. coli are consistent with published biological structures.