Analyse statistique des séquences biologiques
modélisation markovienne, alignements et motifs
Grégory Nuel
Bernard Prum
Hermes Science
Lavoisier
Introduction21
Première partie. Modélisation de séquences37
Chapitre 1. Chaînes de Markov39
1.1. Un exemple39
1.2. Modèles d'indépendance41
1.2.1. Modèle shuffle44
1.3. Rappels sur les chaînes de Markov44
1.3.1. Introduction44
1.3.2. Loi de Xi, loi stationnaire47
1.3.3. Chaînes de Markov d'ordre supérieur à un50
1.3.4. Générateur infinitésimal51
1.4. Application aux séquences biologiques52
1.4.1. Estimation du modèle, loi à portée d52
1.4.2. Loi stationnaire54
1.5. Choix d'un modèle55
1.6. Les chaînes de Markov phasées58
1.7. Diverses chaînes de Markov parcimonieuses59
1.7.1. Les VLMC61
1.7.2. Les PMM62
1.7.3. Les MTD64
1.8. Les chaînes de Markov dérivantes65
1.8.1. Dérive linéaire66
1.8.2. Dérive générale68
1.9. Notes bibliographiques68
Chapitre 2. Chaînes de Markov cachées69
2.1. Motivation69
2.2. Les modèles HMM70
2.2.1. Modèle M1M170
2.2.2. Modèle M1Mm71
2.2.3. Longueur des plages, ergodicité71
2.3. Inférence72
2.3.1. La vraisemblance72
2.3.2. L'algorithme EM73
2.3.2.1. La phase M :74
2.3.2.2. La phase E :75
2.3.2.3. L'algorithme récursif EM77
2.3.2.4. EM et gel final77
2.3.3. Qualité des estimations79
2.3.3.1. Rappels79
2.3.3.2. Vraisemblance conditionnelle80
2.3.3.3. Loi des estimateurs81
2.3.3.4. Conclusion82
2.3.4. L'algorithme SEM82
2.3.5. L'algorithme de Viterbi83
2.4. Les SHMM85
2.5. Exemples d'applications86
2.5.1. Modélisation des gènes86
2.5.2. Profils HMM88
2.5.2.1. Les RBS89
2.5.2.2. Les sites donneurs et accepteurs89
2.6. Chaînes de Markov cachées et score local90
2.6.1. Algorithme de Viterbi93
2.6.2. Algorithme EM93
2.6.3. Variance de l'estimateur95
2.6.3.1. Information de Fisher95
2.6.3.2. Variances96
2.6.3.3. Variance pour les scores97
2.6.3.4. Simulations97
2.6.4. Score local avec m segments99
2.6.4.1. Vraisemblance99
2.6.4.2. Algorithme de Viterbi100
2.6.4.3. Algorithme EM100
2.6.4.4. Information de Fisher101
2.7. Logiciels et notes bibliographiques101
2.7.1. Quelques logiciels101
2.7.2. Notes bibliographiques101
Deuxième partie. Motifs103
Chapitre 3. Compter les motifs105
3.1. Définitions105
3.1.1. Alphabet105
3.1.2. Séquence106
3.1.3. Mot106
3.1.3.1. Palindromes106
3.1.4. Motif107
3.1.5. Que compter ?107
3.1.5.1. Pour un mot107
3.1.5.2. Pour un motif108
3.2. Automates109
3.2.1. Langages109
3.2.2. Automates Finis Déterministes110
3.2.3. Comptages112
3.3. Algorithmes114
3.3.1. Construction d'automates114
3.3.1.1. Automate non déterministe115
3.3.1.2. Déterminisation118
3.3.1.3. Minimisation120
3.3.1.4. Heuristique120
3.3.2. Arbres de suffixes124
3.3.3. Arbres de préfixes129
3.4. Notes bibliographiques132
Chapitre 4. Statistiques de motifs135
4.1. Cyrano de Bergerac135
4.2. Statistique de motifs139
4.3. Pattern Markov Chain140
4.3.1. Modèle M0141
4.3.2. Un cas simple142
4.3.3. Modèle Mm144
4.4. Calculs exacts150
4.4.1. Finite Markov Chain Imbedding151
4.4.2. Algorithmes154
4.4.2.1. Développements asymptotiques156
4.4.3. Temps d'attente157
4.4.3.1. Etudier la répartition des motifs158
4.4.3.2. Simuler la répartition des motifs160
4.4.3.3. Considérations numériques161
4.4.4. Moments163
4.4.4.1. Espérance163
4.4.4.2. Variance165
4.4.5. Lois jointes171
4.4.6. Plusieurs séquences173
4.4.7. Modèle hétérogène175
4.5. Approximations gaussiennes176
4.5.1. Cas Markov176
4.5.2. Lois jointes177
4.5.3. Loi de (Nm, Nm+1)177
4.5.4. Approche fondée sur les martingales183
4.5.5. Modèle shuffle184
4.5.5.1. Espérance185
4.5.5.2. Variance187
4.5.5.3. Approximation gaussienne188
4.6. Approximations binomiales188
4.6.1. Prise en compte de l'estimation des paramètres193
4.7. Approximations de Poisson composées198
4.7.1. Mots recouvrants198
4.7.1.1. Structure d'un mot périodique198
4.7.1.2. Occurrences par paquets199
4.7.1.3. Calcul de thêta200
4.7.1.4. Loi de Poisson géométrique200
4.7.1.5. Exemple du traitement par AFD201
4.7.1.6. Cas de motifs201
4.7.2. Matrice d'autorecouvrement202
4.7.3. Résultat principal204
4.7.4. Cas Poisson205
4.7.5. Cas Poisson géométrique205
4.7.6. Cas général211
4.8. Grandes déviations213
4.8.1. Introduction213
4.8.2. Niveau 1215
4.8.2.1. Calculs numériques217
4.8.3. Niveau 2218
4.8.3.1. Mise en oeuvre pratique220
4.9. Comparaison des méthodes220
4.9.1. Complexités221
4.9.2. Comparaison Markov versus shuffle225
4.9.3. Grandes déviations précises225
4.9.4. Cas extrêmes226
4.9.5. Cas réels229
4.9.6. Conclusions232
4.10. Notes bibliographiques234
Chapitre 5. Motifs biologiques237
5.1. Chi237
5.2. Régulation244
5.3. PROSITE246
5.4. Scan statistics247
5.5. Notes bibliographiques251
5.5.1. Chi251
5.5.2. Régulation252
5.5.3. Prosite252
5.5.4. Scan statistics252
Troisième partie. Alignements de séquences253
Chapitre 6. Score local d'une séquence255
6.1. Définition255
6.1.1. Segment de score maximal255
6.1.2. Algorithme linéaire256
6.1.3. Segments sous-optimaux258
6.2. Significativité exacte259
6.2.1. Cas simple260
6.2.2. Extension aux scores rationnels264
6.2.3. Extension au cas markovien265
6.3. Approximations asymptotiques265
6.3.1. Runs de 1, loi de Gumbel265
6.3.1.1. Exemple simple265
6.3.1.2. Application au cas Bernoulli267
6.3.2. Loi asymptotique du score d'une séquence267
6.3.3. Validité des approximations270
6.4. Notes bibliographiques271
Chapitre 7. Alignement de deux séquences273
7.1. Introduction273
7.1.1. L'évolution ponctuelle273
7.1.2. Matrices d'évolution275
7.1.2.1. Evolution des séquences nucléotidiques275
7.1.2.2. Modèle de Jukes et Cantor277
7.1.2.3. Modèle de Kimura277
7.1.2.4. Autres modèles278
7.1.2.5. Evolution des séquences protéiques278
7.1.2.6. Evolutions non ponctuelles279
7.2. L'alignement de deux séquences d'ADN280
7.2.1. Nombre d'alignements possibles283
7.3. Score global : Needleman et Wunsch285
7.3.1. L'algorithme de programmation dynamique285
7.3.2. Recherche de l'alignement : le trace-back287
7.3.3. Complexité, algorithme SL290
7.3.3.1. Algorithme SL (Space Linear)290
7.4. Score local : Smith et Waterman291
7.4.1. Alignement global de séquences tronquées291
7.4.2. Programmation dynamique et trace-back292
7.5. Scores de gap affines294
7.6. Significativité295
7.7. Heuristiques, Blast295
7.8. Alignement et HMM297
7.9. Notes bibliographiques300
Chapitre 8. Alignements multiples303
8.1. Une heuristique d'alignement multiple305
8.1.1. L'arbre guide : Clustal306
8.2. Ouverture vers la phylogénie307
8.2.1. Phylogénie et distances307
8.2.2. Phylogénie et parcimonie308
8.2.2.1. Calcul du coût d'un arbre308
8.2.2.2. Recherche de l'arbre le plus parcimonieux309
8.2.3. Phylogénie et vraisemblance310
8.2.3.1. L'algorithme PhyML312
8.3. Notes bibliographiques313
Chapitre 9. Matrices de similarité315
9.1. Les matrices Pam316
9.2. Discussion critique318
9.3. Les matrices Blosum319
9.4. Autres matrices321
9.4.1. Sensibilité au choix de (...)321
9.5. Notes bibliographiques322
Annexes323
A. L'algorithme EM325
A.1. La phase M326
A.2. La phase E326
A.3. L'algorithme récursif327
A.4. Variances des estimateurs327
A.5. Notes bibliographiques329
B. Arbres, distances et algorithme NJ331
B.1. Distances d'arbre, distances phylogénétiques331
B.2. L'algorithme NJ333
B.3. Notes bibliographiques335
C. Valeurs propres et vecteurs propres337
C.1. Analyse spectrale337
C.1.1. Matrices positives337
C.1.2. Matrices stochastiques339
C.1.3. Méthode de la puissance nième340
C.2. Algorithme Q R341
C.3. Algorithme d'Arnoldi345
C.4. Notes bibliographiques347
Bibliographie349
Index359