Pseudoknots by Maximizing the Number of Stacking Pairs

Title: Pseudoknots by Maximizing the Number of Stacking Pairs

Research Question: How can we predict the secondary structure of RNA with the maximum number of stacking pairs, even when allowing pseudoknots?

Methodology: The researchers proposed two approximation algorithms with worst-case approximation ratios of 1/2 and 1/3 for planar and general secondary structures, respectively. They used dynamic programming and linear-time algorithms.

Results: They showed that allowing pseudoknots makes it NP-hard to maximize the number of stacking pairs in a planar secondary structure. This result contrasts with previous NP-hard results based on energy functions.

Implications: These findings provide new insights into the computational complexity of predicting RNA secondary structures with pseudoknots. The algorithms can be used to improve the efficiency of predicting RNA structures, which is crucial for understanding their functions in cells.

Link to Article: https://arxiv.org/abs/0111051v1 Authors: arXiv ID: 0111051v1