标题：Maximum Stacking Base Pairs: Hardness and Approximation by Nonlinear LP-Rounding
作者：Liu, Lixin; Jiang, Haitao; Liu, Peiqiang; Zhu, Binhai; Zhu, Daming
通讯作者：Jiang, Haitao;Jiang, HT;Jiang, HT
作者机构：[Liu, Lixin] Shandong Univ, Sch Software, Jinan 250100, Shandong, Peoples R China.; [Jiang, Haitao; Zhu, Daming] Shandong Univ, Sch Comp Sci & Techn 更多
会议名称：15th International Symposium on Bioinformatics Research and Applications (ISBRA)
会议日期：JUN 03-06, 2019
来源：BIOINFORMATICS RESEARCH AND APPLICATIONS, ISBRA 2019
摘要：Maximum stacking base pairs is a fundamental combinatorial problem from RNA secondary structure prediction under the energy model. The basic maximum stacking base pairs problem can be described as: given an RNA sequence, find a maximum number of base pairs such that each chosen base pair has at least one parallel and adjacent partner (i.e., they form a stacking). This problem is NP-hard, no matter whether the candidate base pairs follow the biology principle or are given explicitly as input. This paper investigates a restricted version of this problem where the base pairs are given as input and each base is associated with at most k (a constant) base pairs. We show that this restricted version is still APX-hard, even if the base pairs are weighted. Moreover, by a non-linear LP-rounding method, we present an approximation algorithm with a factor 32(k-1)(3)e(3)8(k-1)e-1. Applying our algorithms on the simulated data, the actual approximation factor is in fact much better than this theoretical bound.