THE COMMON SUBSTRING ALIGNMENT PROBLEM

Xavier COGNARD . Licence Info 2001/2002
Professeur: M. Crochemore

Introduction

Le probleme se pose ainsi: étant donné une chaine de caractéres source S contenant un thème récurant Y et une autre chaine cible T, on veut calculer la distance entre S et T sans calculer encore et encore (c.a.d autant de fois qu'apparait Y dans S) la distance entre T et Y.

Un petit exemple:

S = CBA DCBD DCBD C
Y = DCBD
T = DCBADBDC

Afin de réaliser cet exploit :) il faut tout réaliser une travail en deux étapes; tout d'abord une précompilation que l'on va nommer "etape d'encodage" puis un calcul temps réél que l'on nomme "étape d'alignement". Ainsi pour une partie de S non redondante on calcule la distance normalement, mais avec la partie redondante de S on réutilise la précompilation ("étape d'encodage") effectué et on l'ajuste en fonction de sa position dans S ("etape d'alignement"). Cette technique a pour resultat de faire tomber la complexité en cas de rencontre du thème.

Nous allons donc aborder deux implémentations de ce processus dans, respectivement, une premiére partie et une seconde partie, ainsi que, dans une troisiéme partie, les difficultés auquelles j'ai été confronté durant ce projet.

1. Une premiére implémentation

1.1 Etape d'encodage

Cette étape sert à réaliser l'encodage de la distance entre G et T dans un format adéquat c.a.d utilisable par l'étape d'alignement. Pour cela on construit une matrice DIST qui stocke les poids des plus courts chemins de la premiére lettre de T jusque la derniére de G, des deux premiéres lettres de T jusque la derniére de G, etc...
Afin de trouver ces fameux poids des plus courts chemins (distances), on utilise dans ce projet l'algorithme "Edit Distance"[1]. On a donc, pour un une chaine cible T de longueur N, une matrice de taille N*N ressemblant à:

matrice Dist                   
         

4 3 2 1 1 1 2 3 4   Edit[T₁^j=0...9,Y]
  4 3 2 2 2 3 4 5   Edit[T₂^j=0...9,Y]
    4 3 3 3 4 3 4   Edit[T₃^j=0...9,Y]
      4 4 3 3 2 3   Edit[T₄^j=0...9,Y]
        4 3 2 1 2   Edit[T₅^j=0...9,Y]
          4 3 2 3   Edit[T₆^j=0...9,Y]
            4 3 2   Edit[T₇^j=0...9,Y]
              4 3   Edit[T₈^j=0...9,Y]
                4   Edit[T₉^j=0...9,Y]

Cette matrice ainsi construite va nous permettre de calculer, à l'aide de l'etape qui suit, la distance entre G et T à chaque apparation de l'occurance G dans S.

La complexité de cette étape dépend pour beaucoup de la complexité de l'algorithme utilisé pour calculer les distances de la matrice. En utilisant l'algorithme "Edit Distance" cette phase d'encodage se déroule en O(N²)

1.2 Etape d'alignement

Cette étape s'occupe de gerer le calcul de la distance Out entre G et T, quelques soit le niveau d'avancement de S, à partir de la matrice DIST precedement calculer et du tableau d'entrée In qui prend en compte les calculs de distances precedants.
La sortie Out se calcule de la maniére suivante:

Out [ j ] = min { In [ r ] + DIST [ r , j ] } avec r = 0 ... j
En fait ce calcule applique le tableau d'entrée In à la matrice DIST afin d'obtenir une nouvelle matrice OUT dont on prend le minima de chaque colonne pour trouver le tableau de sortie Out.
Pour continuer l'exemple ci-dessus on exprime In (c.a.d le calcul de la distance entre CBA et T) de la maniére suivante:

In[0]	In[1]	In[2]	In[3]	In[4]	In[5]	In[6]	In[7]	In[8]
3	3	3	2	1	2	3	4	5

Ce qui nous donne une matrice OUT de la forme:

matrice OUT

7 6 5 4 4 4 5 6 7
  7 6 5 5 5 6 7 8
    7 6 6 6 7 6 7
      6 6 5 5 4 5
        5 4 3 2 3
          6 5 4 5
            7 6 5
              8 7
                9

avec OUT [ i , j ] = In [ i ] + DIST [ i , j ] pour j = 0 ... n et i = 0 ... j

et enfin un tableau de sortie Out:

Out[0]	Out[1]	Out[2]	Out[3]	Out[4]	Out[5]	Out[6]	Out[7]	Out[8]
7	6	5	4	4	4	3	2	3

Ce tableau de sortie Out peut maintenant servir d'entrée au prochain calcul de distance entre la prochaine partie de S et T.

Abordons maintenant une propriété importante des matrices DIST et OUT. Ces matrices sont dites de Monge car elles respectent au moins des propriétés suivantes:
1. M [ i , j ] - M [ i , j - 1 ] <= M [ i - 1, j ] - M [ i -1 , j - 1 ]
2. M [ i , j ] - M [ i , j - 1 ] >= M [ i - 1, j ] - M [ i -1 , j - 1 ]

Cela a pour effet de rendre les matrices DIST et OUT totalement monotone. On peut ainsi appliquer l'algorithme de Aggarwal surnommé SMAWK, qui permet de trouver la valeur minimale de chaque colonne d'une matrice N*N en un temps de O(N), à la matrice OUT dans le but de trouver Out le tableau de sortie.
N'ayant pu me procurer une version claire de SMAWK mon algorithme naif effectue le méme travail mais en O(N²).

2. Une seconde implementation

2.1 Etape d'encodage

Toujours dans la méme optique que precedemment, on cherche à, lors de la rencontre du thème Y, pesser du tableau d'entrée In au tableau de sortie Out en un minimum de calcul. Une autre propriété de DIST (et donc de OUT) est que l'ecart entre deux valeurs consecutives appartenant à ces matrices est borné par un indice µ (provenant du choix de l'algorithme pour calculer les distances). On calcule donc, dans cette deuxiéme méthode, la méme matrice DIST que dans la premiére méthode mais on construit en plus la matrice DELTA comme suit:

DELTA [ i , j ] = DIST [ i , j ] - DIST [ i, j - 1] pour j = 1 .... N et i = 0 ... j - 1

On obtient ainsi la matrice DELTA suivante:

matrice DELTA

- -1  -1  -1  0  0  1  1  1
   -  -1  -1  0  0  1  1  1
       -  -1  0  0  1 -1  1
           -  0 -1  0 -1  1
              - -1 -1 -1  1
                 - -1 -1  1
                    - -1 -1
                       - -1
                          -

On peut donc, à l'aide de cette matrice DELTA, faire une representation de taille O(N) de DIST en relevant les "paliers" où la valeur DELTA change.
On défini le tableau Borderline, chargé de représenté DIST, comme un tableau dans les valeurs correspondent aux index des lignes d'un palier (c.a.d la ligne où la valeur fait un saut d'une hauteur de 1). Comme l'ecart type (qui provient du calcul de la distance par l'algorithme "Edit Distance") de notre DELTA est de 2 (valeur entre -1 et 1) alors en cas de "bond" de 2 on place l'index j de la ligne à la fois dans Borderline[1][j] mais aussi dans Borderline[2][j].

En prenant la matrice DELTA ci-dessus on obtient la tableau Borderline suivant:


 -  -  -  -  -  2  2  1  5  Borderline[1,j]
 -  -  -  -  -  -  3  1  5  Borderline[2,j]

De part ces elements, on remarque que, soit deux lignes L1 et L2 avec L1 <= Borderline [ µ , j ] < L2 ,alors

OUT [ L2 , j ] - OUT [ L2 , j - 1 ] < OUT [ L1 , j ] - OUT [ L1 , j - 1 ]
(c'est une propriété qui va servir dans l'etape suivante d'alignement)

2.2 Etape d'alignement

Nous allons maintenant aborder la mise en place d'un algorithme qui, à l'aide des tableaux Borderline et In, calcule le tableau de sortie Out.

Le but est de garder, à chaque étape de l'algorithme, les lignes j succeptibles de contenir la valeur de sortie Out[j]. Pour cela on implemente une liste de candidat qui contient les lignes N en mentionnant si elles sont encore "valable" ou non.
Definissons tout d'abord quelques outils:

_ gap[L] caractérise la différence entre OUT[L] et OUT[candidat suivant L dans la liste]
_ OffSet[L] caractérise la différence entre OUT[premier element dans la liste] et OUT[dernier element dans la liste]
_ Delete[Y] caractérise le poid d'une suppression de Y tout entier. Delete [ Y ] = DIST [ j , j ]

L'algorithme peut se décrire ainsi:

POUR j = 0 ... N FAIRE
{
  1. Ajouter la ligne j à la liste de candidat
  2. Mettre à jour la liste
  3. Calculer la sortie Out[j]
}

1.
On place j comme "valable" dans la liste de candidat

2.
Pour mettre à jour la liste de candidat il faut "invalidé" les candidat valide de la liste et qui n'ont plus lieu de l'être.
Une ligne L1 est considéré comme invalide quand il existe une ligne L2 tel que L2 > L1 et que OUT [ L2 , j] <= OUT [ L1 , j ].
Cela arrive quand:
_ il existe 2 lignes candidates L1 et L2 tel que L1 <= Borderline[µ,j] < L2 et que gap[L1]=0 . Dans ce cas L1 est considéré comme invalide et est supprimé de la liste de candidat
_ lors de l'integration de j dans la liste de candidat, si un candidat posséde un OUT[candidat] etant supérieur ou egal à OUT[j] alors ce candidat est de la méme facon supprimé de la liste des candidats.

3.
Arrivé à ce moment de l'execution, le candidat qui posséde l'index de plus haute valeur est j (étant donné que l'on vient de l'y placer) et OUT [ j , j ] = In[j] + Delete[Y]. Ainsi, comme le premier element de la liste est l'index de la ligne qui contient la valeur minimale de la colonne j de OUT alors:
Out [ j ] = In[j] + Delete[Y] - OffSet[j]

Pour continuer notre exemple voici les differents etats de la liste de candidat, lors du calcul de la distance entre Y et T, avec le tableau d'entrée precedement utilisé ( 3 3 3 2 1 2 3 4 5 ):


      j = 0  1  2  3  4  5  6  7  8

          0  0  0  0  0  4  4  4  4
             1  1  1  4  5  5  5  6
                2  3        6  6  7
                               7  8

On en déduit:

OffSet[j]  0  1  2  2  1  2  4  6  6

D'où:

    Out[j]  7  6  5  4  4  4  3  2  3

Cette etape d'alignement se fait, comme l'etape d'alignement de la premiére methode, en O(N) puisque l'algorithme va de 0 à N. En réalité la compléxité de cette étape est légérement supérieur à ça compte tenu de la gestion de la liste de candidat. [2] propose d'utiliser "The Set Union Implementation" de [4] afin de gerer celle-ci et d'eviter une hausse de la complexité.

3. Remarques generales

Pour changer les parametres d'entrées du programme il faut juste placer les chaines S, Y et T au début du main.
Le programme se compile en faisant g++ prog.c
L'executable se lance avec en parametre le numéro de la méthode à utiliser: 1 pour la premiere methode et 2 pour la deuxiéme.
Tout ces calculs de distance entre des mots trouvent leurs applications dans diverses domaines tel que la sécurité reseau (trouver des chaines de caractéres similaires à des virus dans des trames réseaux) ou le calcul de reconnaissance de génes particuliers dans le génome humain.
Cette étude s'est appuyé en majeur partie sur l'article [2] que je vous recommande de consulter en détail si vous avez à traiter ce sujet car il contient des aspects plus techniques que ce qui se trouve ci-dessus.
Testons maintenant les performances de mon application et des 2 méthodes par la méme occasion.
Test du calcul de distance entre la précedente chaine cible T et une chaine source S contenant 1000000 de thème:

_premiére methode
```
[ravier@localhost ProjTut]$ time -p a.out 1

Compute of Out:
with T = DCBADBDC
with S = CBADCBDC
with Y = DCBD
using the first algorithm...

4000003 4000002 4000001 4000000 4000000 3999999 3999998 3999997 3999996
real 17.56
user 4.73
sys 0.93
```
_deuxiéme méthode
```
[ravier@localhost ProjTut]$ time -p a.out 2

Compute of Out:
with T = DCBADBDC
with S = CBADCBDC
with Y = DCBD
using the second algorithm...

4000003 4000002 4000001 4000000 4000000 3999999 3999998 3999997 3999996
real 3.14
user 3.02
sys 0.09
```
On remarque une nette différences de rapidité entre la premiére et la deuxiéme méthode, somme toute à nuancer puisque normalement le calcul d'alignement de la premiére methode se fait en O(N) grâce à SMAWK alors que là nous sommes en O(N²).

Conclusion

Voilà, nous avons donc aborder le probleme du calcul de la distance entre deux mots dont un posséde une partie redondante.
Une ouverture pourrait se faire en posant une question de complexité au niveau du gain fait par l'utilisation de ces deux méthodes d'un coté et la perte faite par la recheche de différents motifs redondants dans une chaine source S. Cela revient à se demander, sur un point de vue de complexité, où s'arrete le bon compromis recherche motif / gain de méthode.
Meme si le code peut paraitre court c'est dans la subtilité algorithmique que résidait la difficulté de ce projet que j'espere avoir traiter, en partie, comme il se devait.

References

[1]   Incremental String Comparison Gad M. Landau, Eugene W. Myers and Jeanette P. Schmidt

[2]   On The Common Substring Alignment Problem Gad M. Landau & Michal Ziv-Ukelson

[3]   Sequence Comparison Christian Charras & Thierry Lecroq
      http://www-igm.univ-mlv.fr/~lecroq/seqcomp/

[4]   A Linear Time Algorithm For a Special Case of Disjoint Set Union Gabow & R. E. Tarjan