Back to search

University of British Columbia

Efficient algorithm for RNA pseudoknotted secondary structure prediction given a pseudoknot free structure

Abstract

dc:description

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.

Degree

thesis:*
Name thesis:degree_name
Master of Science - MSc
Level thesis:degree_level
master's
Discipline thesis:degree_discipline
Computer Science
Grantor dc:publisher
University of British Columbia
Year dc:date
2005

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Zhao, Yinglei

Rights

dc:rights
Statement dc:rights
  • 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.
Language dc:language
eng

Identifiers

dc:identifier.*
Handle dc:identifier
http://hdl.handle.net/2429/17000

Chain of custody

source
Harvested from
University of British Columbia
Base URL
circle.library.ubc.ca/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Zhao, Yinglei. Efficient algorithm for RNA pseudoknotted secondary structure prediction given a pseudoknot free structure. master's thesis, University of British Columbia, 2005. http://hdl.handle.net/2429/17000