Volume 5 Number 7 (Jul. 2010)
Home > Archive > 2010 > Volume 5 Number 7 (Jul. 2010) >
JCP 2010 Vol.5(7): 1100-1104 ISSN: 1796-203X
doi: 10.4304/jcp.5.7.1100-1104

Fast Algorithm for Pseudoknotted RNA Structure Prediction

Hengwu Li
School of Computer Science and Technology, Shandong Economic University, Jinan 250014, China

Abstract—Pseudoknotted RNA structure prediction is an important problem in bioinformatics. 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(n3) 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(n2) 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%.

Index Terms—RNA structure, algorithm, pseudoknots

[PDF]

Cite: Hengwu Li, " Fast Algorithm for Pseudoknotted RNA Structure Prediction," Journal of Computers vol. 5, no. 7, pp. 1100-1104, 2010.

General Information

ISSN: 1796-203X
Abbreviated Title: J.Comput.
Frequency: Bimonthly
Editor-in-Chief: Prof. Liansheng Tan
Executive Editor: Ms. Nina Lee
Abstracting/ Indexing: DBLP, EBSCO,  ProQuest, INSPEC, ULRICH's Periodicals Directory, WorldCat,etc
E-mail: jcp@iap.org
  • Nov 14, 2019 News!

    Vol 14, No 11 has been published with online version   [Click]

  • Mar 20, 2020 News!

    Vol 15, No 2 has been published with online version   [Click]

  • Dec 16, 2019 News!

    Vol 14, No 12 has been published with online version   [Click]

  • Sep 16, 2019 News!

    Vol 14, No 9 has been published with online version   [Click]

  • Aug 16, 2019 News!

    Vol 14, No 8 has been published with online version   [Click]

  • Read more>>