Open Collections

Abstract

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 [12] and Dirks and Pierce [8] can not handle more than three bands and two bands respectively. The 0(n5) algorithm of Uemura et al. [13] 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.