Note ABES Compression et indexation de séquences annotées Compressing and indexing labeled sequences Algorithmique du texte Indexation de texte Transformée de Burrows-Wheeler Wavelet Tree 005.741 Structures de données (informatique) Bioinformatique Données -- Compression (informatique) Indexation automatique Immunologie Cette thèse en algorithmique du texte étudie la compression, l'indexation et les requêtes sur un texte annoté. Un texte annoté est un texte sur lequel nous ajoutons des informations. Ce peut être par exemple une recombinaison V(D)J, un marqueur de globules blancs, où le texte est une séquence ADN et les annotations sont des noms de gènes. Le système immunitaire d'une personne se représente par un ensemble de recombinaisons V(D)J. Avec le séquençage à haut débit, on peut avoir accès à des millions de recombinaisons V(D)J qui sont stockées et doivent pouvoir être retrouvées et comparées rapidement.La première contribution de ce manuscrit est une méthode de compression d'un texte annoté qui repose sur le principe du stockage par références. Le texte est découpé en facteurs pointant vers les séquences annotées déjà connues. La seconde contribution propose deux index pour un texte annoté. Ils utilisent une transformée de Burrows-Wheeler indexant le texte ainsi qu'un Wavelet Tree stockant les annotations. Ces index permettent des requêtes efficaces sur le texte, les annotations ou les deux. Nous souhaitons à terme utiliser l'un de ces index pour indexer des recombinaisons V(D)J obtenues dans des services d'hématologie lors du diagnostic et du suivi de patients atteints de leucémie. This thesis in text algorithm studies the compression, indexation and querying on a labeled text. A labeled text is a text to which we add information. For example: a V(D)J recombination, a marker for lymphocytes, where the text is a DNA sequence and the labels are the genes' names. A person's immune system can be represented with a set of V(D)J recombinations. With high-throughput sequencing, we have access to millions of V(D)J recombinations which are stored and need to be recovered and compared quickly.The first contribution of this manuscript is a compression method for a labeled text which uses the concept of storage by references. The text is divided into sections which point to pre-established labeled sequences. The second contribution offers two indexes for a labeled text. Both use a Burrows-Wheeler transform to index the text and a Wavelet Tree to index the labels. These indexes allow efficient queries on text, labels or both. We would like to use one of these indexes on V(D)J recombinations which are obtained with hematology services from the diagnostic or follow-up of patients suffering from leukemia. Electronic Thesis or Dissertation Text fr PDF 1460876 text/html https://pepite-depot.univ-lille.fr/LIBRE/EDSPI/2018/50376-2018-Rocher.pdf https://theses.fr/2018LILUI004/abes Rocher Tatiana Rocher 1991-09-01 FR 231576870 https://theses.fr/2018LILUI004 2018LILUI004 https://doi.org/10.70675/9ffe4b25z7944z4479z8361z7ab8a95d3353 2018-02-12 Informatique et applications Université de Lille (2018-2021) 223446556 Doctorat Docteur es non oui Giraud Mathieu MADS_DIRECTEUR_DE_THESE_1 094640610 Salson Mikaël MADS_DIRECTEUR_DE_THESE_2 157564363 École doctorale Sciences pour l'ingénieur (Lille ; 1992-2021) MADS_ECOLE_DOCTORALE_1 147297028 Centre de Recherche en Informatique, Signal et Automatique de Lille MADS_PARTENAIRE_DE_RECHERCHE_1 18388695X ddc:000 Giraud Mathieu Salson Mikaël École doctorale Sciences pour l'Ingénieur (Lille) Centre de recherche en informatique, signal et automatique de Lille (CRIStAL) PDF 1460876