Fast Algorithm for Pseudoknotted RNA Structure Prediction
|
| Title | Fast Algorithm for Pseudoknotted RNA Structure Prediction |
| Authors | |
| Abstract | Existing polynomial time algorithms can handle only limited types of pseudoknots, or have too high time or space to predict long sequences. In this paper a heuristic algorithm is presented to maximize stems and predict arbitrary pseudoknots with O(n^3) time and O(n) space for a large scale of 5000 bases. Compared with maximum weighted matching algorithm, our algorithm reduce space complexity from O(n^2) to O(n); and the experimental results show that its sensitivity is improved from 80% to 87.8%, and specificity is increased from 53.7% to 75.9%. Compared with genetic algorithm with the accuracy of 83.3% and simulated annealing algorithm with the accuracy of 79.7%, our algorithm increases the predicted accuracy to 87.5%. |
| Publisher | ACADEMY PUBLISHER |
| Date | 2010-07-01 |
| Source | Journal of Computers Vol 5, No 7 (2010) |
| Rights | Copyright © ACADEMY PUBLISHER - All Rights Reserved.To request permission, please check out URL: http://www.academypublisher.com/copyrightpermission.html. |