PhD of Eric Rivals

Compresssion Algorithms and Applications to Genetic Sequence Analysis

I did my PhD thesis at Lille 1 University in the Laboratoire d'Informatique Fondamentale de Lille (Computer Science Lab. of Lille 1 University). I have ben directed by Pr.Max Dauchet and Pr.Jean-Paul Delahaye.

Title: Compresssion Algorithms and Applications to Genetic Sequence Analysis

Defended on the 10th of January 1996

**Jury**
President	Alain HÉNAUT	Université de Versailles-Saint-Quentin
Rapporteurs	Maxime CROCHEMORE	Université de Marne la Vallée
	Alain HÉNAUT	Université de Versailles-Saint-Quentin
Examinateurs	Didier ARQUÈS	Université de Marne la Vallée
	Max DAUCHET	Université de Lille I
	Jean-Paul DELAHAYE	Université de Lille I
	Christian GAUTIER	Université de Lyon I
	Mireille RÉGNIER	INRIA Rocquencourt

Supports

Abstract

Fetch Postscript file

Supports

This work was supported by:

the French Ministry of Education and Research MESR by the mean of an "Allocation de recherches MESR"
the Groupement De Recherches "Informatique et Génomes" (G.D.R. 1029) a research initiave of the C.N.R.S. (Centre National de Recherches Scientifiques)
the Groupement de Recherches et d'Études sur les Génomes (so called G.I.P. G.R.E.G.)
the Groupement De Recherches CNRS "Algorithme, Modélisation et Infographie" (G.D.R. AMI)

Abstract

Genetic study of organisms is a major research field in biology. The sequencing of complete genomes yields a huge quantity of raw data, which are sequences over a four letters alphabet. To truly understand those sequences, the biologists need sequences analysis methods. We use the framework of Kolmogorov complexity. The Kolmogorov complexity of a sequence is the length of its more compressed description. The main idea of the theory states that the compression of a sequence is intrinsically linked with its understanding. A compression scheme uses a property to compress an object. The more the description is compressed, the more the property is relevant for the given object. Keeping in mind this idea, we design compression schemes which are dedicated to genetic sequences, and allows:

the identification and the encoding of regularities spread over a long sequence, such as repeats;
the detection of small motifs tandem repeats in order to find low complexity segments, called DOS-DNA by biologists.

The investigation of the nature and distribution of DOS-DNA allows us to identify a constant property in the organization of yeast chromosomes. Last part of our work is about defining an effective notion of optimal representation under structural conditions. We compare our definition to existing approaches, then we show its robustness and usability for texts of natural pattern.

Fetch Postscript File

To fetch the gziped postscript file of the complete thesis in French click here PhD Thesis

Eric Rivals