TY - GEN
T1 - Approximation algorithms for the maximum multiple RNA interaction problem
AU - Tong, Weitian
AU - Goebel, Randy
AU - Liu, Tian
AU - Lin, Guohui
PY - 2013
Y1 - 2013
N2 - RNA interactions are fundamental in many cellular processes, which can involve two or more RNA molecules. 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.
AB - RNA interactions are fundamental in many cellular processes, which can involve two or more RNA molecules. 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.
KW - Acyclic 2-matching
KW - Approximation algorithm
KW - Maximum weight b-matching
KW - RNA interaction
KW - Worst case performance ratio
UR - http://www.scopus.com/inward/record.url?scp=84893032545&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-03780-6_5
DO - 10.1007/978-3-319-03780-6_5
M3 - Conference article
AN - SCOPUS:84893032545
SN - 9783319037790
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 49
EP - 59
BT - Combinatorial Optimization and Applications - 7th International Conference, COCOA 2013, Proceedings
T2 - 7th International Conference on Combinatorial Optimization and Applications, COCOA 2013
Y2 - 12 December 2013 through 14 December 2013
ER -