Advertisement
Published in:
2011 | OriginalPaper | Chapter
Prediction of Minimum Free Energy Structure for Simple Non-standard Pseudoknot
Authors : Thomas K. F. Wong, S. M. Yiu
Published in: Biomedical Engineering Systems and Technologies
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Predicting the secondary structure with minimum free energy of an RNA molecule is an important problem in computational biology. Unfortunately, the problem is in general NP-hard if there are pseudoknots in the structure. Existing algorithms usually target at some restricted classes of pseudoknots. In this paper, we extend the current classification of pseudoknots to capture more complicated pseudoknots, namely the simple non-standard pseudoknots of degree
k
. We provide an algorithm to compute the structure with minimum free energy for this type of pseudoknots of degree 4 which covers all known secondary structures of RNAs in this class. Our algorithm runs in
O
(
m
4
) time where
m
is the length of the input RNA sequence.