标题：A new approximation algorithm for the maximum stacking base pairs problem from RNA secondary structures prediction
作者：Zhou, Aizhong ;Jiang, Haitao ;Guo, Jiong ;Zhu, Daming
作者机构：[Zhou, Aizhong ;Guo, Jiong ] School of Computer Science and Technology, School of Mathematics and System Science, Shandong University, Jinan, China;[J 更多
会议名称：11th International Conference on Combinatorial Optimization and Applications, COCOA 2017
会议日期：16 December 2017 through 18 December 2017
来源：Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
摘要：This paper investigates the problem of maximum stacking base pairs from RNA secondary structure prediction. The basic version of maximum stacking base pairs problem as: given an RNA sequence, to find a maximum number of base pairs where each base pair is involved in a stacking. Ieong et al. showed this problem to be NP-hard, where the candidate base pairs follow some biology principle and are given implicitly. In this paper, we study the version of this problem that the candidate base pairs are given explicitly as input, and present a new approximation algorithm for this problem by the local search method, improving the approximation factor from 5/2 to 7/3. The time complexity is within O(n14), since we adopt 1-substitution and special 2-substitutions in the local improvement steps. © Springer International Publishing AG 2017.