French Flag

Algorithmics for biological structures:
tree edit for RNA secondary structure comparison

Laurent Tichit

Advisor: Serge Dulucq

Abstract:

RNA molecules play a fundamental role in the chemical processes that occur within the cell. This dissertation deals with the comparison of RNA secondary structures. These structures were formalized by M.S. Waterman in the late 70's and account for a major part of the structural informations known for the RNA molecules. Based on an approach similar to that of Shapiro and Viennot, we represent them by labeled ordered rooted trees.
First, we review the state of the art in the field of comparison algorithms between tree structures and consider many extensions of them. The algorithm family that we study is based on a generalization of the methods for computing a distance between sequences used for the genome comparison.
We focus our work on one of the best (in terms of complexity) edit distance computation algorithms between ordered rooted trees: the Zhang-Shasha algorithm, and present an exact analysis of its complexity.
Secondly, we generalize some sequence comparison methods to tree structures. We propose two new algorithms for the computation of the local score between two unordered and ordered rooted trees. We also propose an extension of the Zhang-Shasha algorithm that defines a densified edit distance between trees.
Finally, we present some results from a biological point of view and apply this set of improvements to RNA secondary structures. These improvements concern structural compression, the local edit distance and densified edit distance of RNA secondary structures.
As a conclusion, we present a software tool for compararing secondary structures, that implements the improvements developed in this thesis.

Keywords:

Algorithmics, Rooted Tree, RNA, Comparison, Complexity, Metric, Dynamic Programming , Generating Function, Secondary Structure.

Ph.D. Dissertation:

In Postscript version.

Valid HTML 4.01!