• Refine Query
  • Source
  • Publication year
  • to
  • Language
  • 1
  • Tagged with
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • About
  • The Global ETD Search service is a free service for researchers to find electronic theses and dissertations. This service is provided by the Networked Digital Library of Theses and Dissertations.
    Our metadata is collected from universities around the world. If you manage a university/consortium/country archive and want to be added, details can be found on the NDLTD website.
1

An efficient algorithm for an optimal modular compression. Application to the analysis of genetic sequences. /Un algorithme rapide pour une compression modulaire optimale. Application à l'analyse de séquences génétiques.

Delgrange, Olivier 05 June 1997 (has links)
Abstract : A lossless compression algorithm often applies the same coding scheme on the whole sequence to be compressed. Therefore, some factors of the sequence are shortened while others are lengthened. In this work, we propose an optimization algorithm of compression methods which breaks off the coding where it is not profitable, so that some segments of the initial sequence are copied as they are instead of being coded. The achieved compression is said modular, meaning that the compressed sequence is a sequel of compressed segments and copied segments. Under specific hypotheses, our algorithm computes an optimal modular compression in time O(n log n) where n is the length of the sequence. We show that our optimization method can be advantageously used to analyze data, and particularly genetic sequences. The Kolmogorov complexity theory brings to light the usefulness of compression when analyzing sequences. The work consists of three parts. The first one introduces the classical concepts of compression and coding, as well as the new concept of ICL codes for the integers. The second one presents the compression optimization algorithm by liftings that uses ICL codes. Finally, the third part presents applications of the compression optimization by liftings, especially in the context of genetic sequence analysis. With the specific problem of the localization of approximate tandem repeats, we show how the compression optimization algorithm by liftings can be used to localize regular segments and irregular segments of a sequence in a precise and optimal way. This comeback to experimentation makes it possible to analyze sequences that contain several thousands of symbols within the space of a few seconds. /Résumé : Une méthode de compression sans perte d'informations applique souvent le même schéma de codage d'un bout à l'autre de la séquence à comprimer. Certains facteurs de la séquence sont ainsi raccourcis mais malheureusement d'autres sont rallongés. Dans ce travail, nous proposons un algorithme d'optimisation de compression qui rompt le codage là ou il n'est pas intéressant en recopiant des morceaux de la séquence initiale. La compression obtenue est dite modulaire : la séquence comprimée est une succession de morceaux comprimés et de morceaux recopiés tels quels. Sous certaines hypothèses, notre algorithme fournit une compression modulaire optimale en temps O(n log n) où n est la longueur de la séquence. Nous montrons que notre méthode de compression peut avantageusement être utilisée pour analyser des données et plus particulièrement des séquences génétiques. La théorie de la complexité de Kolmogorov éclaire l'idée d'analyse de séquences par compression. Le travail comporte trois parties. La première introduit les concepts classiques de compression et de codage, ainsi que le concept nouveau de codage ICL d'entiers. La seconde développe l'algorithme d'optimisation de compression par liftings qui utilise les codes ICL. La dernière partie présente des applications de l'optimisation de compression par liftings, plus particulièrement dans le domaine de l'analyse de séquences génétiques. Nous montrons, à l'aide du problème spécifique de localisation de répétitions en tandem approximatives, comment l'algorithme d'optimisation par liftings peut être utilisé pour localiser précisément et de manière optimale les segments réguliers et les segments non réguliers des séquences. Il s'agit d'un retour à l'expérience qui permet l'analyse de séquences de plusieurs centaines de milliers de bases en quelques secondes.

Page generated in 0.1752 seconds