doi: 10.4304/jsw.6.2.233-240
Approximation Algorithm and Scheme for RNA Maximum Weighted Stacking
- School of Computer Science and Technology, Shandong Economic University, Jinan, China
Abstract
Pseudoknotted RNA structure prediction is an important problem in bioinformatics. Existing polynomial time algorithms have no performance guarantee or can handle only limited types of pseudoknots. In this paper for the general problem of pseudoknotted RNA structure prediction, maximum weighted stacking problem is presented based on stacking actions, and its polynomial time approximation algorithm with <em>O</em>(<em>nlogn</em>) time and <em>O</em>(<em>n</em>) space and polynomial time approximation scheme are given. The approximate performance ratio of this approximation algorithm is 3. Compared with existing polynomial time algorithm, they have exact approximation performance and can predict arbitrary pseudoknots.
Keywords
- RNA structure
- appproximation algorithm
How to Cite
Hengwu Li, Huijian Han, and Zhenzhong Xu, "Approximation Algorithm and Scheme for RNA Maximum Weighted Stacking," Journal of Software, vol. 6, no. 2, pp. 233-240, 2011. https://doi.org/ 10.4304/jsw.6.2.233-240
Copyright & License
Copyright © 2011 by the authors. This is an open access article distributed under the Creative Commons Attribution License which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited (CC BY 4.0).