Date of Award
2010
Degree Type
Thesis
Degree Name
Master of Science
Program
Computer Science
Supervisor
Dr. Kaizhong Zhang
Abstract
RNA is an important molecule which performs a wide range of functions in biological systems. The comparison between RNA secondary and tertiary structures has received much attention recently. It is a well known fact that structural features of RNAs are among the most significant factors in the molecular mechanisms involved in their functions. The presumption is that, to a preserved biological function there corresponds a preserved molecular structure. Therefore, the ability to compare RNA structures is useful. Furthermore, in many problems involving RNAs, it is required to have an alignment between RNA structures in addition to a similarity measure. Computing alignment between RNA tertiary structures is NP-hard and MAX SNP-hard. In this research, we present algorithms for computing the alignment between two RNA tertiary structures. For simple tertiary structures, we can compute the optimal alignment efficiently. For moderate tertiary structures, we adopt the constrained alignment approach. Although the result produced by constrained alignment is not guaranteed to be an optimal solution, in practice it would be reasonable. Experimental tests show that our algorithms can be used to compute alignment between RNA tertiary structures in practical applications.
Recommended Citation
Ma, Qichan, "Improved Algorithms for Alignment between RNA Tertiary Structures" (2010). Digitized Theses. 4497.
https://ir.lib.uwo.ca/digitizedtheses/4497