Dynamic programming algorithms for RNA secondary structure prediction with pseudoknots Export

@article{Akutsu-2000, abstract = {This paper shows simple dynamic programming algorithms for RNA secondary structure prediction with pseudoknots. For a basic version of the problem (i.e., maximizing the number of base pairs), this paper presents an O(n4) time exact algorithm and an O(n4-[delta]) time approximation algorithm. The latter one outputs, for most RNA sequences, a secondary structure in which the number of base pairs is at least 1-[var epsilon] of the optimal, where [var epsilon],[delta] are any constants satisfying 0<[var epsilon],[delta]<1. Several related results are shown too.}, author = {Akutsu, Tatsuya}, citeulike-article-id = {652534}, citeulike-linkout-0 = {http://dx.doi.org/10.1016/S0166-218X(00)00186-4}, citeulike-linkout-1 = {http://linkinghub.elsevier.com/retrieve/pii/S0166-218X(00)00186-4}, citeulike-linkout-2 = {http://www.sciencedirect.com/science/article/B6TYW-40WDSSK-3/2/966d49d8e468ce13e37420f65f632db0}, citeulike-linkout-3 = {http://portal.acm.org/citation.cfm?id=351046}, day = {15}, doi = {10.1016/S0166-218X(00)00186-4}, issn = {0166218X}, journal = {Discrete Applied Mathematics}, keywords = {approximation-algorithms, computational-biology, dynamic-programming, pseudoknot, rna-secondary-structure}, month = {August}, number = {1-3}, pages = {45--62}, posted-at = {2009-05-15 11:57:02}, priority = {2}, title = {Dynamic programming algorithms for RNA secondary structure prediction with pseudoknots}, url = {http://dx.doi.org/10.1016/S0166-218X(00)00186-4}, volume = {104}, year = {2000} }

TY - JOUR ID - Akutsu-2000 L3 - citeulike-article-id:652534 N2 - This paper shows simple dynamic programming algorithms for RNA secondary structure prediction with pseudoknots. For a basic version of the problem (i.e., maximizing the number of base pairs), this paper presents an O(n4) time exact algorithm and an O(n4-[delta]) time approximation algorithm. The latter one outputs, for most RNA sequences, a secondary structure in which the number of base pairs is at least 1-[var epsilon] of the optimal, where [var epsilon],[delta] are any constants satisfying 0<[var epsilon],[delta]<1. Several related results are shown too. IS - 1-3 JF - Discrete Applied Mathematics SN - 0166218X EP - 62 TI - Dynamic programming algorithms for RNA secondary structure prediction with pseudoknots VL - 104 SP - 45 KW - approximation-algorithms KW - computational-biology KW - dynamic-programming KW - pseudoknot KW - rna-secondary-structure AU - Akutsu, Tatsuya PY - 2000/08/15/ UR - http://dx.doi.org/10.1016/S0166-218X(00)00186-4 ER -