Approximating the Maximum Multiple RNA Interaction Problem
Full Text: 1-s2.0-S0304397514003107-main.pdf
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.
Citation
W. Tong, R. Goebel, T. Liu, G. Lin. "Approximating the Maximum Multiple RNA Interaction Problem". Theoretical Computer Science, 556, pp 63-70, October 2014.| Keywords: | RNA interaction, Maximum weight b-matching, Acyclic 2-matching, Approximation algorithm, Worst case performance ratio |
| Category: | In Journal |
| Web Links: | DOI |
| Elsevier |
BibTeX
@article{Tong+al:14,
author = {Weitian Tong and Randy Goebel and Tian Liu and Guohui Lin},
title = {Approximating the Maximum Multiple RNA Interaction Problem},
Volume = "556",
Pages = {63-70},
journal = {Theoretical Computer Science},
year = 2014,
}Last Updated: February 13, 2020Submitted by Sabina P
