Université Lille1 - Sciences et Technologies Un algorithme rapide pour une compression modulaire optimale : application à l'analyse de séquences génétiques An efficient algorithm for an optimal modular compression. Application to genetic sequence analysis 005.746 Données Compression (informatique) Algorithmes optimaux Kolmogorov, Équation de Text Electronic Thesis or Dissertation fr 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à où 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) ou 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. application/pdf 1 : 1 Mo https://pepite-depot.univ-lille.fr/LIBRE/Th_Num/1997/50376-1997-165.pdf Delgrange Olivier 1900-01-01 057606544 1997LIL10081 1997-01-01 Informatique Université Lille1 - Sciences et Technologies 026404184 Doctorat non oui ddc:000 ASCII PDF 9999