Open Collections

Linear time algorithm for parsing RNA secondary structure

University of British Columbia

RNA secondary structure prediction is an important problem in computational molecular biology. Experiments show that existing polynomial time prediction algorithms have limited success in predicting correctly the base pairs, i.e. secondary structure, in known biological RNA structures. One limitation of many current algorithms is that they can predict only restricted classes of structures, excluding many so-called pseudoknotted secondary structures. The type of the pseudoknotted structures that occur in biological structures, as well as the type of structures handled by current algorithms, have been poorly understood, making it difficult to assess the generality of current algorithms. In this thesis we present a comprehensive and precise classification of structural elements and loops in a secondary structure, along with a linear time algorithm for parsing secondary structures into their structural elements. The parsing algorithm, along with the classification scheme for the loops in a pseudoknotted secondary structure, can be used in analysing existing prediction algorithms to determine which known biological RNA structures can not be predicted by the algorithms. This analysis can help us to design new and more powerful prediction algorithms. Furthermore, we present two applications of our work: (i) linear time free energy calculation algorithm, and (ii) linear time test for Akutsu's[2] algorithm class. We present a linear time algorithm for calculating the free energy of a given secondary structure. This algorithm can be useful especially in heuristic prediction algorithms, as they commonly use a procedure to calculate the free energy for a given sequence and structures. We also present a linear time algorithm to test whether the prediction algorithm introduced by Akutsu[2] can handle a given structure. The result of our analysis on algorithm of Akutsu on some sets of biological structures shows that although it is proved theoretically that the class of structures handled by Akutsu's algorithm is more general than that handled by the algorithm of Dirks and Pierce [7], they can both handle the same class of given biological structures.

Thesis/Dissertation

application/pdf

2009-11-24

For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use.

http://hdl.handle.net/2429/15658

Computer Science

University of British Columbia

UBCV

DSpace