Improved Approximation Algorithms for Predicting RNA Secondary Structures with Arbitrary Pseudoknots

摘要

We study three closely related problems motivated by the prediction of RNA secondary structures with arbitrary pseudoknots: the MAXIMUM BASE Pair Stackings problem proposed by Ieong et al. [19], the Maximum Stacking Base Pairs problem proposed by Lyngso [22], and the 2-Interval Pattern problem proposed by Vialette [36]. For Maximum Base Pair Stackings and Maximum Stacking Base Pairs, we present improved approximation algorithms that can incorporate covariance information from comparative analysis as explicit input of candidate base pairs. For 2-Interval Pattern, we present improved approximation algorithms on unitary and near-unitary input, and propose a new variant called Length-Weighted Balanced 2-Interval Pattern, which is natural in the nearest-neighbor energy model that emphasizes base pair stacking.