Algorithmes de recherche de motifs dans les séquences d'ADN / Renaud Vérin ; sous la direction de Maxime Crochemore

Date :

Editeur / Publisher : [S.l.] : [s.n.] , 1998

Type : Livre / Book

Type : Thèse / Thesis

Langue / Language : français / French

Catalogue Worldcat

Bioinformatique

ADN -- Informatique

Crochemore, Maxime (1947-....) (Directeur de thèse / thesis advisor)

Université de Marne-la-Vallée (Organisme de soutenance / degree-grantor)

Résumé / Abstract : CETTE THESE, SITUEE DANS LE CADRE DE LA BIO-INFORMATIQUE, PRESENTE DES METHODES PERMETTANT DE DETECTER DES REGIONS DANS LES SEQUENCES D'ADN AYANT UNE FAIBLE ENTROPIE. ON APPELLE CES REGIONS DES ZONES DE DOSDNA. ON DEFINIT ICI L'ENTROPIE COMME LE NOMBRE DE FACTEURS DISTINCTS PRESENTS DANS UNE REGION. ELLE EST MESUREE EN TEMPS LINEAIRE. POUR CELA, LES SEQUENCES D'ADN SONT VUES COMME DES TEXTES SUR L'ALPHABET DES NUCLEOTIDES [SOMME DE L'ENSEMBLE] = A,C,G,T ET ON CREE UN INDEX DE TOUS LES FACTEURS PRESENTS DANS LE TEXTE. D'UN POINT DE VUE INFORMATIQUE, LES ARBRES ET LES AUTOMATES DE SUFFIXES SONT LES STRUCTURES DE DONNEES LES MIEUX ADAPTEES POUR GENERER CES INDEX. ILS ONT UNE TAILLE LINEAIRE PAR RAPPORT A LA TAILLE DU TEXTE ET LE TEMPS D'ACCES A UN FACTEUR W DU TEXTE EST DE O (LONGUEUR (W)). ON S'INTERESSE ICI AUX AUTOMATES COMPACTS DE SUFFIXES (ACS). LE GAIN D'ESPACE MEMOIRE DU A LA COMPRESSION PERMET DE CONSTRUIRE, EN MOYENNE, DES INDEX DE SEQUENCES DEUX FOIS PLUS GRANDES QU'AVEC DES AUTOMATES DE SUFFIXES, TOUT EN LES GARDANT EN MEMOIRE VIVE. NOUS AVONS DEVELOPPE LE PREMIER ALGORITHME LINEAIRE DE CONSTRUCTION DIRECTE DES ACS. D'UN POINT DE VUE BIOLOGIQUE, GRACE A CES STRUCTURES DE DONNEES, NOUS AVONS ADAPTE DES METHODES EXISTANTES, LA CREATION DE PAYSAGES DE SEQUENCES ET L'ANALYSE STATISTIQUE DES VALEURS DE X#2 DE PORTIONS DE SEQUENCES, AFIN QU'ILS PUISSENT TRAITER EFFICACEMENT LES LONGUES SEQUENCES. NOUS AVONS DEVELOPPE UNE NOUVELLE METHODE, BASE SUR LA MESURE D'ENTROPIE DE PORTIONS DE SEQUENCES. CETTE METHODE PERMET DE DETECTER DES ZONES CONTENANT DE LONGUES REPETITIONS OU UN GRAND NOMBRE DE PETITES REPETITIONS. NOUS AVONS COMPARE LES REGIONS REMARQUABLES EN UTILISANT UN INDICE DE PROXIMITE, BASE SUR L'INDICE DE JACCARD. CETTE METHODE MET EN EVIDENCE DES REGIONS AYANT DES SIMILARITES QUI N'AURAIENT PAS ETE TROUVEES AVEC DES METHODES STANDARDS D'ALIGNEMENT. ON APPLIQUE CETTE METHODE SUR DES CHROMOSOMES DE LA LEVURE SACCHAROMYCES CEREVISIAE