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 : n2/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
  • Ai = é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

 
m1ilc/bioinfo_2.txt · Dernière modification: 2010/05/23 16:14 par suitable
 
Sauf mention contraire, le contenu de ce wiki est placé sous la licence suivante :CC Attribution-Noncommercial-Share Alike 3.0 Unported
Recent changes RSS feed Donate Powered by PHP Valid XHTML 1.0 Valid CSS Driven by DokuWiki