Approximating the maximum multiple RNA interaction problem

RNA interactions are fundamental in many cellular processes, where two or more RNA molecules can be involved. Multiple RNA interactions are also believed to be much more complex than pairwise interactions. Recently, multiple RNA interaction prediction has been formulated as a maximization problem. Here we extensively examine this optimization problem under several biologically meaningful interaction models. We present a polynomial time algorithm for the problem when the order of interacting RNAs is known and pseudoknot interactions are allowed; for the general problem without an assumed RNA order, we prove the NP-hardness for both variants (allowing and disallowing pseudoknot interactions), and present a constant ratio approximation algorithm for each of them.

Authors

• Weitian Tong
• Randy Goebel Department of Computing Science, University of Alberta, Edmonton, Canada Alberta Machine Intelligence Institute, University of Alberta, Edmonton, Canada
• Tian Liu
• Guohui Lin

Keywords

• RNA interaction
• Maximum weight b-matching
• Acyclic 2-matching
• Approximation algorithm
• Worst case performance ratio