Improved Algorithms for Alignment between RNA Tertiary Structures

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.

Name thesis:degree_name

M Sc

Discipline thesis:degree_discipline

Computer Science

Year dc:date.issued

2010

Author dc:creator

• Ma, Qichan

Advisor dc:contributor.advisor

• Zhang, Kaizhong

• dynamic programming
• sequence alignment
• RNA
• RNA secondary structure
• RNA tertiary structure
• RNA structural alignment

Handle dc:identifier.uri

https://hdl.handle.net/20.500.14721/19716

OAI identifier oai:identifier

oai:uwo.scholaris.ca:20.500.14721/19716