[figure]

Pourquoi ?

Algorithmes sur les chaînes classiques (BM, KMP...)

Complexité temporelle O(|m| + |t|) par rapport à O(|t| + |m|) (complexité spatiale Θ(|t|)).

Recherche de la plus longue sous-chaîne commune en temps linéaire (cf. conjecture de Knuth ≈70).

Algorithmique du texte (notamment “biologique”).

Objectif :

– avoir une représentation linéaire en |t| de l’ensemble des facteurs de t,

– la construire en O(|t|),

– permettre la recherche d’un facteur f en un temps O(|f|).

[figure]

Prélude : l’ADS

On appelle arbre digital des suffixes d’un mot s l’arbre (déterministe) dont les arcs ont pour label des lettres de l’alphabet et dont l’ensemble des mots formés par les labels concaténés de chaque branche représente l’ensemble des suffixes de s.

Exemple : arbre digital des suffixes de ACAC$.

[figure: 1; 2; 3; 4; 5; •; •; •; •; •; •; •; •; $; C; C; $; C; C; A; $; A; $; $; A]

[figure]

Commentaires

2|s| ≤ |ADS(s)| ≤ \frac{|s|(|s| + 1)}{2}

Définitions :

– locus d’un mot,

– suf_{i} : ie suffixe de s,

– head_{i} : plus long préfixe de suf_{i} également préfixe d’un suf_{j}, j < i.

– tail_{i} : tel que suf_{i} = head_{i} · tail_{i}.

Remarque : marqueur de fin $.

[figure]

Algorithme

Complexité spatiale (en nombre de nœuds crées) et temporelle (en parcours de nœuds) quadratique.

[figure]

L’arbre des suffixes

L’arbre des suffixes d’une chaîne s est un arbre AS(s) dont les arêtes sont étiquetées par chacun des suffixes de s. Cet arbre indexe toutes les sous-chaînes de s, donne leur position et toutes leurs occurences dans s. (c’est la version compressée de l’ADS) Cet structure de données présente les caractéristiques suivantes :

– les arcs de AS(s) sont les facteurs de s,

– les chemins de la racine à un nœud interne sont les suffixes de s,

– chaque nœud interne a au moins deux fils,

– les arcs issus d’un nœud interne sont étiquetés par des facteurs commençant par des lettres différentes.

En codant les labels par un couple d’entiers (position de début et longueur du facteur), on a :

|s| + 1 ≤ |AS(s)| ≤ 2|s| − 1

[figure]

Un exemple

s = CAGATAGAG$

[figure: 1; 5; 12; 2; 8; 10; 3; 14; 6; 15; 7; 11; 9; 4; 13; 0; CAGATAGAG$; TAGAG$; $; G; G; $; A; $; G$; G$; A; TAGAG$; TAGAG$; TAGAG$; A]

Construisons-le pas à pas ...

[figure]

Comment : version naïve

Complexité spatiale linéaire. avec label = couple d’entiers)

Construction :

– compression de l’arbre digital des suffixes : NON !

– itération de la fonction slowfind et coupe_arc.

Complexité temporelle :

– Le rajout d’une branche ne comporte qu’un seul nœud, qu’un seul label et se fait donc en temps constant.

– mais le parcours des suffixes depuis la racine

reste quadratique. tape i O(|head_{i}|) NON !

[figure]

Comment : version sioux Algorithme de McCreight

Notion de lien suffixe.

On cherche à trouver le locus du suffixe suivant en temps constant (en moyenne sur l’ensemble de la construction).

Propriété : si head_{i−1} peut s’écrire sous la forme aδ (a ∈ Σ, δ ∈ Σ^{∗}) alors δ est un préfixe de head_{i}.

Le lien suffixe d’un nœud interne p de l’AS, locus de aδ, relie p à q, le locus de δ.

La fonction fastfind

Remarque : il existe d’autres algorithmes dont celui d’Ukkonen qui est dynamique mais plus gourmand en place mémoire.

[figure]

L’algorithme -1-

[figure]

L’algorithme -2-

[figure]

L’algorithme -3-

[figure]

Complexité

Complexité spatiale :

|AS(s)| ≤ 2n − 1 = O(n)

Complexité temporelle :

• Complexité de la fonction slowfind. À l’étape i, lecture de |γ_{1}| + 1 caractères de s. Or :

|γ_{1}| + 1 ≤ |head_{i}| − |head_{i−1}| + 2

d’où, en sommant, une complexité en O(n).

• Complexité de la fonction fastfind. À l’étape i, lecture de |β| caractères de s. Or :

|β| ≤ |pere(head_{i})| − |pere(head_{i−1})| + 2 d’où, en sommant, une complexité en O(n).

Remarque : fastfind est-elle indispensable ?

[figure]

Quelques applications

⋆ Recherche de toutes les occurrences d’un mot

w en O(|w| + k), ⋆ Plus longue sous-chaîne commune d’un

ensemble E de mots en O(|E|) et ses applications :

– textuelles,

– recherche dans une BD (US army !),

– contamination de l’ADN,

– alignement, ⋆ Répétition maximale dans un texte, ⋆ Linearisation des chaînes circulaires ⋆ Palindrome maximal, ⋆ Recherche avec erreurs, ⋆ Compression, ⋆ Pattern matching bidimensionnel, ⋆ Algorithmique géométrique, ⋆ ...

[figure]

Bibliographie

- R. Vérin. Algorithmes de recherches de motifs dans les séquences d’ADN. Thèse de Doctorat de l’UMLV, 1998.

- M. Crochemore et W. Rytter. Text Algorithms. Oxford University Press, 1994.

- D. Gusfield. Algorithms on strings, Trees and Sequences. Computer Science and Computational Biology. Cambridge University Press, 1997.

- M. S. Waterman. Introduction to Computational Biology. Maps, Sequences and Genomes. Chapman & Hall, 1995.

- T. Lecroq. Exact String Matching Algorithms. Laboratoire d’Informatique de Rouen.

et SANS RAPPORT AUCUN :

- J. A. Bergstra, I. Bethke, P. Rodenburg. A propositional logic with 4 values : true, false, divergent and meaningless. WWW fermivista.

[figure]

Compléments

Le source Caml. Les fichiers ps. Le Web

  http://www.cs.mcgill.ca/
       ~aghitza/suffix/SuffixTreeGrow.html

[figure]

Conclusion

Structure très riche. Implémentation des applications. Remerciements à

– B. Petazzoni,

– Université de Marne la vallée.