A New Approximation Algorithm for the Maximum Stacking Base Pairs Problem from RNA Secondary Structures Prediction
| Autor: | Daming Zhu, Haitao Jiang, Aizhong Zhou, Jiong Guo |
|---|---|
| Rok vydání: | 2017 |
| Předmět: |
0301 basic medicine
business.industry Base pair 0206 medical engineering Stacking RNA Approximation algorithm 02 engineering and technology Combinatorics 03 medical and health sciences 030104 developmental biology RNA Sequence Local search (optimization) business Time complexity 020602 bioinformatics Rna secondary structure prediction |
| Zdroj: | Combinatorial Optimization and Applications ISBN: 9783319711492 COCOA (1) |
| DOI: | 10.1007/978-3-319-71150-8_7 |
| Popis: | 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(n^{14})\), since we adopt 1-substitution and special 2-substitutions in the local improvement steps. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|