Return to search

A general RNA secondary structure algorithm with vertical tree grammar

Our understanding of the functions played by RNA molecules is expanded with the understanding of RNA structures. Except for primary structure, RNA molecules present pairings within a sequence, which is called RNA secondary structure. Since its discovery, RNA secondary structure has drawn considerable attention because it is widely appeared.
Many programs for RNA secondary structure prediction have been developed, including [4, 20, 38, 39, 46]. Based on our knowledge, however, there is a family of RNA secondary structure which can not be covered by any of these algorithms. And even without considering this family, none of programs can cover all other structures in Rfam data-set. These structures are found to be important in many biological processes, for example, chromosome maintenance, RNA processing, protein biosynthesis. And efficient structure prediction can give direction for experimental investigations. Here, we present a general algorithm with a new grammar: Vertical Tree Grammar (VTG) which has stochastic context-free grammar architecture for RNA secondary structure prediction. VTG significantly expands the class of structures that can be handled, including all structures that can be covered by other paper, and all structures in Rfam data-set. Our algorithm runs in O(n^6) time, and it's precision is reasonable high, with average sensitivity and specificity over
70%. / published_or_final_version / Computer Science / Master / Master of Philosophy

Identiferoai:union.ndltd.org:HKU/oai:hub.hku.hk:10722/196439
Date January 2013
CreatorsLiu, Xinyi, 刘欣怡
ContributorsLam, TW, Yiu, SM
PublisherThe University of Hong Kong (Pokfulam, Hong Kong)
Source SetsHong Kong University Theses
LanguageEnglish
Detected LanguageEnglish
TypePG_Thesis
RightsCreative Commons: Attribution 3.0 Hong Kong License, The author retains all proprietary rights, (such as patent rights) and the right to use in future works.
RelationHKU Theses Online (HKUTO)

Page generated in 0.0021 seconds