2011 | OriginalPaper | Buchkapitel
Prediction of Minimum Free Energy Structure for Simple Non-standard Pseudoknot
verfasst von : Thomas K. F. Wong, S. M. Yiu
Erschienen in: Biomedical Engineering Systems and Technologies
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. 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.