标题: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
出版年:2019
卷:11490
页码:244-256
DOI:10.1007/978-3-030-20242-2_21
摘要: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.
收录类别:CPCI-S;EI;SCOPUS
资源类型:会议论文;期刊论文
原文链接:https://www.scopus.com/inward/record.uri?eid=2-s2.0-85066854547&doi=10.1007%2f978-3-030-20242-2_21&partnerID=40&md5=f888d23ab6ed9fc95042d1a298971ac2
TOP