标题:Approximation algorithm of RNA folding including pseudoknots
作者:Liu, Zhendong
作者机构:[Liu, Zhendong ] School of Computer Science and Technology, Shandong University, Jinan 250101, China;[Liu, Zhendong ] School of Computer Science and T 更多
通讯作者:Liu, Z.
来源:International Review on Computers and Software
出版年:2012
卷:7
期:6
页码:2942-2946
关键词:Approximation algorithm; MFE principle; N-Stem; Pseudoknots; RNA structure
摘要:Computational prediction of RNA secondary structure is among the few problems that can be solved satisfactory in polynomial. Based on MFE principle and the relative stability of the n-stems in RNA molecules, Minimum Free Energy method is adopted widely to predict RNA secondary structure, an improved approximation algorithm is presented to predict RNA pseudoknotted structure, the algorithm can solve arbitrary nested or parallel pseudoknots,the algorithm takes O(n3) time and O(n2) space. This algorithm not only reduces the time complexity to O(n3), but also widens the maximum length of the sequence. The preliminary experimental test on the RNA sub-sequences in PseudoBase confirm that the algorithm outperforms other known algorithms in predicting accuracy, specificity and sensitivity. © 2012 Praise Worthy Prize S.r.l. - All rights reserved.
收录类别:EI;SCOPUS
Scopus被引频次:4
资源类型:期刊论文
原文链接:https://www.scopus.com/inward/record.uri?eid=2-s2.0-84873294078&partnerID=40&md5=19cd4e55d790ef7c4f3b3d463bb4200a
TOP