====== Alignements de Mots ====== ===== Introduction ===== ===== Algorithme Naïf ===== Pour perspective, partons de l'algorithme naïf et le calcul de son complexité. L'algorithme naïf cherche un mot **x** de longueur |x|=m dans un texte **y** de longueur |y|=n. Il étudie tous les cas possibles, en comparant **x** au contenu d'une fenêtre glissante sur **y** de longueur m. Procedure naive (x, m, y, n) pour j <- 0 à (n-m) faire reponse <- vrai i <- 0 tant que reponse = vrai et i < (m-1) faire si x[j+i] <> y[i] alors reponse = faux i <- i+1 fin tant que si reponse = vrai, afficher "alignement trouvé pour décalage " + j fin pour ==== Complexité dans le pire des cas ==== O(n m) ( O((n-m)*m) plus exactement) dans le cas où tous les tests doivent être réalisés parce que x et y sont des puissances de la même lettre. On exécute les deux boucles, internes et externes, pleinement. Pour |y| = 1, ça reste O(n); le pire des cas est pour m = n/2 : n²/2. ==== Complexité en moyenne ==== ^ Rappel ^ | Si q est une probabilité, %%|%%q%%|%% < 1, les séries \sum_{k=0}^{\infty} q^k | | et leurs dérivées sont convergentes et leurs sommes valent | | \sum_{k=0}^{\infty} q^k = \frac{1}{1-q} | | \sum_{k=0}^{\infty} \left(q^k\right) \prime = \left(\frac{1}{1-q} \right) \prime = \frac{1}{\left( 1 - q \right)2} | | La dérivée d'une série est égale à la dérivée de sa somme | * Hypothèse : distribution uniforme des occurrences des lettres. On constate que l'algorithme comparera la fenêtre au mot recherché **n - m + 1 ** fois. Combien de comparaisons de lettres de la fenêtre avec le texte, en moyenne? * Soit N ≥ 2 le cardinal de l'alphabet * p = (N-1)/N * q = 1/N * A_i = évènement d'obtenir une lettre différente à la i-ième comparaison. * Alors, * P\left(x=k\right) = P\left( \bar{A}_1 \cap \bar{A}_2 \cap \ldots \cap \bar{A}_{k-A} \cap A_k \right) * =P\left( \bar{A}_1 \right)\cdot P\left( \bar{A}_2 \right) \ldots P\left( \bar{A}_{k-1} \right) P\left( A_k \right) * = q^{k-1} p [loi gémétrique] * \displaystyle E\left(x\right) = \sum_{k=1}^{m} k p q^{k-1} \leq \sum_{k=1}^{\infty} kpq^{k-1} = \frac{N-1}{N}\sum_{k=1}^{\infty} k q^{k-1} = \frac{N-1}{N} \left(\frac{1}{1-q}\right)^{\prime} * = \frac{N-1}{N} \left(\frac{1}{\left(1-q\right)^2}\right) = \frac{N-1}{N} \left(\frac{1}{\left(1-\frac{1}{N}\right)^2}\right) * = \frac{N-1}{N} \left(\frac{1}{\left(\frac{N-1}{N}\right)^2}\right)= \frac{N-1}{N} \left(\frac{N}{N-1}\right)^2= \frac{N}{N-1} = \frac{1}{p} ===== Tracé ===== Des similitude entre deux mots x et y de longueurs respectives m et n peuvent être visulaisées graphiquement en définissant une table Tr de taille m x n, appelée le **tracé** entre x et y. Les valeurs de la table Tr sont définies pour toute position i sur x et j sur y par Tr[i,j] = vrai si x[i]=y[j], faux sinon. Pour visualiser le tracé, des detons (ou autre symbole) sur une grille sont utilisées pour signifier la valeur vrai. Les zones de similitude entre deux mots apparaissent alors comme des suites de jetons sur le diagonales de la grille. Il est possible de déduire d'un tracé un alignement global entre les deux mots en joignant des suites de jetons: * des jonctions diagonales correspondent à des substitution * des jonctions horizontales correspondent à des insertions * des jonctions verticales correspondent à des suppressions Les alignements globaux correspondent alors à des chemins commençant à proximité du coin supérieur gaugche et se terminant à proximité du coin inférieur droit. ==== Exercice ==== Donner le tracé entre X = ACGT et y = ATGCTACG. Déduire des propriétés entre x et y. ^ ^ A ^ T ^ G ^ C ^ T ^ A ^ C ^ G ^ ^ A | * | | | | | * | | | ^ C | | | | * | | | * | | ^ G | | | * | | | | | * | ^ T | | * | | | * | | | | * Il y a un préfixe propre de x qui est suffixe propre de y : x[0..2] = y[5..7] = A.C.G. Ca peut correspondre à in insertion de A.T.G.C.T (x[0..4]). * Il existe une suffixe propre de x qui est un facteur miroir de y : x[3]=y[1] , x[2]=y[2], x[1]=y[3]. ===== Alignement avec Brèches ===== ===== Alignement Local ===== ==== Similarité ==== ==== Calcul d'un alignement local optimal ==== ==== Calcul de plusieurs alignements locaux ==== ===== Méthodes Heuristiques Pour Les Séquences Biologiques ===== ===== Matrices de Similarité ===== ==== Matrices de similarité génétique (n=4) ==== ==== Matrices de similarité protéique (n=20) ==== ===== Variantes Algorithmiques ===== ==== Alignement d'un motif avec une séquence ==== ==== Alignement d'une séquence moyenne avec une séquence ==== ==== Alignement d'un profil avec une séquence ==== ==== Alignement d'un profil flexible avec une séquence ==== ===== Algorithmes d'Alignement Multiple ===== ==== Algorithmes d'alignement optimaux ==== ==== Méthodes heuristique d'alignement multiple ==== ===== Alignement de Structures Secondaires de l'ARN =====