2001/11/20 by Samuel Ieong, Ieong, Samuel, Ming-Yang Kao +11
Biochemistry, Genetics and Molecular Biology · Computer Science · #Advanced biosensing and bioanalysis techniques #Computational Engineering #DNA and Nucleic Acid Chemistry #Data Structures and Algorithms (cs.DS) #F2.2 #FOS: Biological sciences #FOS: Computer and information sciences #Finance #G2.3 #J.3 #Quantitative Biology (q-bio) #RNA and protein synthesis mechanisms #and Science (cs.CE) #cs.CE #cs.DS #q-bio
paper · pdf · doi:10.48550/arxiv.cs/0111051
A preliminary version of this work appeared in Proceedings of the IEEE International Symposium on Bio-Informatics & Biomedical Engineering (BIBE 2001), Washington, DC, 2001
arxiv created 2001/11/20 · openalex publication_date 2001/11/20 · arxiv updated 2009/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The paper investigates the computational problem of predicting RNA secondary structures. The general belief is that allowing pseudoknots makes the problem hard. Existing polynomial-time algorithms are heuristic algorithms with no performance guarantee and can only handle limited types of pseudoknots. In this paper we initiate the study of predicting RNA secondary structures with a maximum number of stacking pairs while allowing arbitrary pseudoknots. We obtain two approximation algorithms with worst-case approximation ratios of 1/2 and 1/3 for planar and general secondary structures,respectively. For an RNA sequence of n bases, the approximation algorithm for planar secondary structures runs in O(n3) time while that for the general case runs in linear time. Furthermore, we prove that allowing pseudoknots makes it NP-hard to maximize the number of stacking pairs in a planar secondary structure. This result is in contrast with the recent NP-hard results on psuedoknots which are based on optimizing some general and complicated energy functions.