Improved Algorithms for Alignment between RNA Tertiary Structures
type: CreativeWork
description: 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.
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.
author: Ma, Qichan
keywords: dynamic programming, sequence alignment, RNA, RNA secondary structure, RNA tertiary structure, RNA structural alignment
date published: 2010-01-01
date modified: 2026-07-27T21:56:07Z
provider: Western University
publisher: Networked Digital Library of Theses and Dissertations
type: WebPage
source organization: Western University

PropertyValue
property ID: Handle
value: https://hdl.handle.net/20.500.14721/19716