these

Informations

• Publié par: Vufuk
• Nombre de lectures: 60
• Langue: Français

Extrait

UNIVERSITE DU QUEBEC A MONTREAL
ALGORITHMES VECTORIELS ET BIOINFORMATIQUE
THESE
PRESENTEE
COMME EXIGENCE PARTIELLE
DU DOCTORAT EN MATHEMATIQUES
PAR
SYLVIE HAMEL
AVRIL 2002REMERCIEMENTS
Je voudrais commencer par dire un gros MERCI a ma directrice Anne Bergeron
pour sa disponibilite, son enthousiasme, son humour, sa patience et bien entendu pour
ses belles idees mathematiques toujours tres interessantes et joliement presentees. Merci
pour tout le temps que tu as passe a lire et relire et corriger ma these et a m’envoyer
ces longs e-mails de Paris pour me donner tes opinions sur les nombreuses versions de
certains des chapitres de cette these. Merci a l’imprimante de Marne-la-Vallee pour
avoir permis a Anne d’imprimer ma these de si nombreuses fois :-)
Merci a mes parents, Gisele et Henri-Paul, a mon frere Steve et a ma soeur Josee
pour m’avoir toujours appuyee dans mes etudes et pour ^etre toujours l a pour moi. Merci
de m’aimer comme je suis, avec mes petites excentricites et ma t^ete de cochon.
Merci Fran cois pour ton amour, ta grande patience envers mes angoisses de n de
doctorat. Merci d’^etre l a, a c^ote de moi. Merci a toi Cedrik, mon petit homme, pour ta
bonne humeur constante et toutes les belles histoires que tu me racontes. Gardez tous
les deux cette capacite de me faire sourire, peu importe mon humeur. Je vous aime.
CRSNG, FCAR, ISM, Andre, Manon....TABLE DES MATIERES
REMERCIEMENTS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii
LISTE DES FIGURES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vi
RESUME . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ix
INTRODUCTION . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
CHAPITRE I
RECHERCHE DES OCCURRENCES APPROXIMATIVES D’UN MOT DANS
UN TEXTE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2 Alignement global de deux mots . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2.1 Qu’est-ce qu’un alignement? . . . . . . . . . . . . . . . . . . . . . . 6
1.2.2 Cout^ d’edition d’un alignement . . . . . . . . . . . . . . . . . . . . . 8
1.2.3 Distance d’edition ou de Levenshtein . . . . . . . . . . . . . . . . . . 9
1.2.4 Distance d’edition generalisee . . . . . . . . . . . . . . . . . . . . . . 11
1.3 Calcul de la distance d’edition entre deux mots . . . . . . . . . . . . . . . . 14
1.3.1 Le probleme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.3.2 La relation de recurrence . . . . . . . . . . . . . . . . . . . . . . . . 16
1.3.3 Calculer D(m;n) a l’aide d’une table . . . . . . . . . . . . . . . . . 18
1.3.4 Obtenir les alignements optimaux . . . . . . . . . . . . . . . . . . . 19
1.4 Calcul des occurrences approximatives d’un mot dans un texte . . . . . . . 22
1.4.1 Le probleme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
1.4.2 La relation de recurrence . . . . . . . . . . . . . . . . . . . . . . . . 23
1.4.3 Les positions des occurrences approximatives . . . . . . . . . . . . . 24
1.4.4 Obtenir les occurrences approximatives . . . . . . . . . . . . . . . . 24
CHAPITRE II
DIFFERENTES APPROCHES AU PROBLEME DE LA RECHERCHE AP-
PROXIMATIVE D’UN MOT DANS UN TEXTE . . . . . . . . . . . . . . . . . 27
2.1 Ne calculer qu’une partie de la table des distances . . . . . . . . . . . . . . 27iv
2.2 Pretraitement du mot P a l’aide d’un automate ni deterministe . . . . . . 29
2.3 Prt de P et calcul de diagonales . . . . . . . . . . . . . . . . . . 31
2.3.1 Calcul de diagonales . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
2.3.2 Premier algorithme de Landau-Vishkin . . . . . . . . . . . . . . . . 36
2.3.3 Algorithme de Galil-Park . . . . . . . . . . . . . . . . . . . . . . . . 40
2.3.4 Deuxieme algorithme de Landau-Vishkin . . . . . . . . . . . . . . . 41
2.3.5 Algorithme de Ukkonen-Wood . . . . . . . . . . . . . . . . . . . . . 44
2.4 La methode des 4 Russes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
2.4.1 Algorithme de Masek-Paterson pour l’alignement global . . . . . . . 49
2.4.2 de Wu, Manber et Myers pour la recherche approximative 52
2.5 Une approche a la Boyer-Moore . . . . . . . . . . . . . . . . . . . . . . . . . 60
CHAPITRE III
APPROCHES VECTORIELLES AU PROBLEME DE LA RECHERCHE AP-
PROXIMATIVE D’UN MOT DANS UN TEXTE . . . . . . . . . . . . . . . . . 64
3.1 Operations vectorielles, notations et algorithmes vectoriels . . . . . . . . . . 64
3.2 Algorithme de Wu et Manber . . . . . . . . . . . . . . . . . . . . . . . . . . 67
3.2.1 Recherche exacte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
3.2.2 Recherche approximative . . . . . . . . . . . . . . . . . . . . . . . . 70
3.3 Algorithme de Baeza-Yates et Gonnet . . . . . . . . . . . . . . . . . . . . . 72
3.4 de Myers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
CHAPITRE IV
AUTOMATES RESOLUBLES ET ALGORITHMES VECTORIELS . . . . . . 82
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
4.2 Automates de Moore et algorithmes vectoriels . . . . . . . . . . . . . . . . . 83
4.2.1 Un exemple simple . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
4.2.2 Une memoire des evenements passes . . . . . . . . . . . . . . . . . . 85
4.2.3 Automates resolubles) algorithmes vectoriels . . . . . . . . . . . . 87
4.3 Algorithme vectoriel pour la recherche approximative d’un mot dans un texte 95
4.3.1 Rappel du probleme . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
4.3.2 Calculer les distances avec un automate . . . . . . . . . . . . . . . . 97v
4.3.3 Notre algorithme vectoriel . . . . . . . . . . . . . . . . . . . . . . . . 100
4.3.4 Mesure de complexite . . . . . . . . . . . . . . . . . . . . . . . . . . 106
CHAPITRE V
DECOMPOSITION EN CASCADE D’AUTOMATES . . . . . . . . . . . . . . 108
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
5.2 Construction de cascades d’automates . . . . . . . . . . . . . . . . . . . . . 109
5.2.1 De nition de la decomposition en cascade . . . . . . . . . . . . . . . 109
5.2.2 Problemes relies a la decomposition . . . . . . . . . . . . . . . . . . 114
5.3 Algorithmes vectoriels associes aux automates aperiodiques . . . . . . . . . 116
5.3.1 De nitions et exemples . . . . . . . . . . . . . . . . . . . . . . . . . 116
5.3.2 Les decompositions en cascade sont des algorithmes vectoriels . . . . 117
5.3.3 Lien avec la logique temporelle et complexite . . . . . . . . . . . . . 122
5.4 Le cas des automates resolubles . . . . . . . . . . . . . . . . . . . . . . . . . 125
5.4.1 Decomposition en cascades d’un automate resoluble . . . . . . . . . 126
5.4.2 Un algorithme bit-vectoriel lineaire . . . . . . . . . . . . . . . . . . . 132
5.4.3 Analyse de complexite . . . . . . . . . . . . . . . . . . . . . . . . . . 136
CONCLUSION . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137
Bibliographie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139LISTE DES FIGURES
1.1 Di erents alignements de deux sequences . . . . . . . . . . . . . . . . . 8
1.2 Passage d’une sequence x a une sequence y avec un transcrit d’edition . 10
1.3 Une fonction de substitution . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.4 Initialisation de la table des distances D entre deux mots . . . . . . . . 18
1.5 Table des distances entre les sequences AAGCTAAG et AGGAGGA. . 19
1.6 Exemple de chemins correspondants a des alignements optimaux . . . . 20
1.7 Chemins optimaux avec une distance d’edition generalisee . . . . . . . . 21
1.8 Exemple de table des distances pour le probleme de la recherche des
occurrences approximatives d’un mot dans un texte . . . . . . . . . . . . 24
1.9 Chemins correspondants a des occurrences approximatives du mot P =
AAC dans le texte T = ACGTAACGAGG . . . . . . . . . . . . . . . . 26
2.1 Un exemple de calcul partiel de la table des distances . . . . . . . . . . 28
2.2 Un autre exemple, moins interessant, de calcul partiel de la table D . . 29
2.3 Un automate M . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31P
2.4 Une diagonale dans la table des distances . . . . . . . . . . . . . . . . . 32
2.5 Exemples de calcul de C(e;d) . . . . . . . . . . . . . . . . . . . . . . . . 33
2.6 Une table de valeurs C(e;d) . . . . . . . . . . . . . . . . . . . . . . . . . 34vii
2.7 Une C-diagonale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
2.8 Une L-diagonale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
2.9 Un arbre des su xes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
2.10 Un automate su xe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
3.1 Di erences horizontales et verticales d’une cellule . . . . . . . . . . . . . 78
4.1 Un automate de Moore . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
4.2 Automate d’addition binaire . . . . . . . . . . . . . . . . . . . . . . . . 86
5.1 Un etat global du produit en cascade . . . . . . . . . . . . . . . . . . . . 110
5.2 Le nouvel etat global apres la transition a . . . . . . . . . . . . . . . . . 110
5.3 Un compteur borne . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
5.4 Une dec