Alignements de Mots

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

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.

• 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}

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.

Donner le tracé entre X = ACGT et y = ATGCTACG. Déduire des propriétés entre x et y.

• 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].