Algorithmes annexes liés au séquençage

Il existe de nombreux problèmes annexes à celui de la mise en correspondance de deux chaînes. Nous aborderons le problème de similitude locale, ainsi que la détermination de la sous-chaînes de y ayant k différences avec x.

similitudes locales :

Nous nous intéressons ici a trouver un alignement optimal local entre une partie de x et une partie de y. La notion de distance n'est plus suffisante nous allons utiliser la formule de récurrence suivante:

{T(i-1,j-1)+sub(xi,yj),
T(i,j)=max   T(i-1,j)+sub(xi,-),
 T(i,j-1)+sub(-,yj)}

où les substitutions ont maintenant un coût négatif, de plus chaque case conserve une valeur positive.

Exemple:

x=ATCGTG ,y=ATGTCTGAC  ,sub(a,a)=1, sub(a,b)=-m, gap=-m.
 
 
A T G T C T G A C
0 0 0 0 0 0 0 0 0 0
A 0 1 0 0 0 0 0 0 1 0
T 0 0 2 0 1 0 1 0 0 0
C 0 0 0 0 0 2 0 0 0 1
C 0 0 0 0 0 1 0 0 0 1
T 0 0 1 0 1 0 2 0 0 0
G 0 0 0 2 0 0 0 3 0 0

Pour trouver un alignement local optimal il suffit maintenant de trouver la plus grande valeur dans la table T et d'effectuer le tracer arrière du chemin  à partir de la case contenant cette valeur.

CTG est la plus grande aire de similitude entre ATCCTG et ATGTCTGAC .

Sous-chaînes de y ayant k différences avec x :
Nous allons maintenant chercher toutes les sous-chaînes de y qui sont à une distance plus petite ou égale à une valeur k donner de x .
pour cela on initialise la première ligne du tableau avec 0.
(se qui signifie que l'insertion d'une lettre de y en début de x a un coût nul ).
les réponses sont donner par la dernière ligne de T qui ont une valeur plus petite ou égal à k.

exemple avec k=1 x=ATCT, y=ATGTCGTATGTGC
A T G T C G T A T G T G C
0 0 0 0 0 0 0 0 0 0 0 0 0 0
A 1 0 1 1 1 1 1 1 0 1 1 1 1 1
T 2 1 0 1 1 2 2 1 1 0 1 1 2 2
C 3 2 1 1 2 1 2 2 2 1 1 1 2 3
T 4 3 2 2 1 2 2 2 3 2 2 1 2 3

 

différence (x,m,y,n,k)  
pour j<-0 à n faire
 
  T(0,j)<-0  
 
pour i<-0 à n faire
 
 
T(i,0)<-i+1
 
 
pour j<-1 à m faire
si xi=yj alors p<-0
    sinon p<-1
    T(i,j)<-min{T(i-1,j-1)+p ,
    T(i,j-1)+1 ,
    T(i-1,j)+1 }
    si T(n,j)<=k sinon renvoie(j)

 

solutions:

A
T
G
T
C
G
T
A
T
G
T
G
C
|
|
:
|
A
T
C
T

A
T
G
T
C
G
T
A
T
G
T
G
C
|
|
:
|
A
T
C
T

 

on pourra tester ces algorithmes avec les modules.