UBC Theses and Dissertations
Efficient algorithm for RNA pseudoknotted secondary structure prediction given a pseudoknot free structure Zhao, Yinglei
Pseudoknotted secondary structure prediction of nucleic acid molecules is an important problem in computational molecular biology. In this thesis, we introduce a Pseudoknot-Add algorithm for the problem of Predicting Pseudoknot Additions. In this problem, one is given as input a sequence S and pseudoknot free structure G, and the goal is to find the minimum free energy pseudoknotted structure R for S, that contains G. The Pseudoknot-Add algorithm has an overall time complexity of 0(n3), and a space complexity of 0(n3). We call the class of structures that our algorithm can predict density-2 structures. The density-2 structures include kissing hairpin structures, which occur in nature. Every density-2 structure R is a bi-secondary structure, i.e., can be partitioned into two pseudoknot free secondary structures G and G'. Our algorithm can handle pseudoknotted loops with an arbitrary number of bands.Other (9(n5) algorithms of Akutsu  and Dirks and Pierce  can not handle more than three bands and two bands respectively. The 0(n5) algorithm of Uemura et al.  can not handle density-2 structures with more than 3 bands either. With respect to given structure G, our algorithm finds the MFE density-2 structure R containing G. The structure R is not necessarily the MFE density-2 structure of the sequence 5, since G is given.
Item Citations and Data