La recherche approchée de motifs : théorie et applications

1

La recherche approchée de motifs :théorie et applications

République Algérienne Démocratique et PopulaireMinistère de L'Enseignement Supérieur et de la Recherche Scientifique

Université des Sciences et de la Technologie Houari Boumediene

Présentée pour l’obtention du diplôme de DOCTORAT En : INFORMATIQUE

Par : Chegrane Ibrahim

Mme. Aicha Aissani-Mokhtari Prof USTHB/FEI Président Mme. Nacéra Bensaou MCA USTHB/FEI Directrice de thèse M. Thierry Lecroq Prof U. Rouen-Normandie ExaminateurM. Riadh BabaAli Prof USTHB/FEI ExaminateurM. Abdelmajid Boukra Prof USTHB/FEI ExaminateurM. Djamal Belazzougui M.R CERIST Invité

Soutenue publiquement, le 07 /12/ 2016 , devant le jury composé de :

Ibra_chegrane@hotmail.com , ibra.chegrane@gmail.com

2

Plan Background : la recherche de motifs

• La recherche approchée avec hachage• La recherche approchée avec Trie et Trie inversé

La recherche approchée

L’auto-complétion approchée

L’alignement multiple

3

La recherche de motifs

Chercher un motif, tout en permettant certain nombre d'erreurs

Exacte ibrahim

ibrahim

Approchée ibrahim

ibrahimbrahim

abraham

ibrahimovichblahim

Hors-ligne : indexationEn-ligne

4

La recherche approchée de motifs

5

Les fonctions de distance

D. Hamming

D. Levenshtein

D. Levenshtein- Damerau

Ibrahim

IbrahamSubstitution

Ibrahim

IbrahimoInsertion

Ibrahim

brahimSuppression

Ibrahim

birahimTransposition

6

Applications

7

Problématique de la recherche approchée

1. Dans quelle position l'erreur se trouve ?xbrahim, ixrahim, ibxahim, …., ibrahix,…..,pos insertion, …….

2. Quels sont les caractères qui mènent à des solutions possibles dans une position donnée.

3. Les types des erreurs à considérer ? (sub, insert, sup)

4. K>= 2 , combinaison entre les positions et les types.-xyrahim, xbyahim, xbryhim, xbrayim, ….

5. L’espace mémoire de SDD.

6. Combiner 1+2+3+4+5.

…. ibrxhim ……..

ab...z

7 + 8 +7 = 22 Cas

K=2 erreurs20+36+20+….= 228 Cas

Trouver des mots contenants des erreurs

8

Méthodes de la recherche approchée

Programmation dynamique

Méthodes de filtrage

Génération de voisinage

Indexation

HachageBit-parallélisme

Parallélisme

Méthodes hybrides

9

Ma thèse

Travauxexistants

ThéoriePratique

Algorithmes

Validés en pratique

Très performant

s

Compétitifs

Bibliothèques

Développeurs

Chercheurs

La recherche approchée pour k >=2 en utilisant les tables de hachage**

10

** Belazzougui, D. : Faster and space-optimal edit distance "1" dictionary. In : CombinatorialPattern Matching, 20th Annual Symposium, CPM 2009, Lille, France, June 22-24, 2009, Proceedings. (2009) 154 167.

1ère Contribution

La structure de données :Le dictionnaire exact

L’index[i] stocke lesmots de longueur i+2Si |mot|< .

11

𝒉 (𝒙 )=∑𝒊=𝟏

𝒎𝒙 𝒊× 𝒕𝒊𝒎𝒐𝒅𝑷

L’espace mémoire : Donc

Temps de Constr: L’ index[-2], stocke lesmots >= .

,

La structure de données :Dictionnaire des listes de substitution

• D={…,ABCDE,…, ABXDE,….}

– stocke .– stocke .– stocke stocke – stocke .– stocke .

• C, X sont stockés dans la même position.

D E A C X B

12

L’espace mémoire : Temps de Constr :

La vérification des occurrences

• D={…,ABCDE,…, ABXDE,….}

– ABCDE – ABXDE

D E A C X B

vérification

13Temps de Vérification :

Extension à deux erreurs ou plus

D E A C X B

. . . . . . . . . . . .

. . . . . . . . . . . .

𝑘=1≡𝑢1𝜙𝑢2

𝑘=2≡𝑢1𝜙𝑢2𝜙𝑢3

𝑘=𝑃≡𝑢1𝜙…𝜙𝑢𝑝+1

.

.

.

Génération Vérification

14

Pour K=2 erreurs L’espace mémoire : Temps de Constr: Temps de Vérif :

L'application de l’algorithme pour l'indexation d’un texte

15

16

La recherche approchée de motifs basée sur un

Trie et un Trie inversé (TRT_CI).

2ème Contribution

17

Trie

D={….ABCDEABDDEXYADAXYCDEXYDAAXYDDEXYZDZ….}

Recherche exacte

Mot requête : XYDDE

Recherche approchée k=1

Mot requête : XYqDE

A

B

C

D

E

D

D

E

X

Y

C

D

E

D

A

A

D

E

A

D

A

Z

D

Z

Solutions : 1) XYDDE 2) XYCDE

L’espace mémoire : Temps de Constr : Temps Rech exact : Temps Rech approchée :

18

L’idée de base de cette approche TRT_CI

• Soit mot requête

• Soit mot solution

𝑃1

𝑎𝑒1𝑒2𝑃2

𝑐1𝑎𝑐2{𝑎 ,𝑒1 ,𝑒2 }∩ {𝑐1 ,𝑎 ,𝑐2 }={𝑎}

𝑃1𝑎𝑃2

Trie Trie inversé

Temps de Vérif pire cas : T de Vérif cas moy : si si

19

La Méthode TRT_CI avec exemple

D={….ABCDEABDDEXYADAXYCDEXYDAAXYDDEXYZDZ….}

A

B

C

D

E

D

D

E

X

Y

C

D

E

D

A

A

D

E

A

D

A

Z

D

Z

Trie

={….EDCBAEDDBCADAYXEDCYXAADYXEDDYXZDZYX….}

A

A

D

Y

D

A

Y

E

D

B

A

D

B

C

Y

X

C

Y

X

Trie inversé

X X

Z

D

Z

Y

X

3)

Mot requête : XYqDE

1) Chercher « XY » dans le Trie 2) Chercher « ED » dans le Trie inversé

Solutions : XYCDE XYDDE

4) Continuer la recherche dans les branches

20

TRT_C pour k erreurs

–

– 𝑃2𝑎𝑛1𝑛2

𝑃 3

𝑏𝑟 1𝑟 2𝑃 ′=𝑃1𝑎 𝑃2𝑏𝑃3

GSTree inversé

𝑃2𝑐1𝑏𝑐2

𝑃1𝑎𝑒1𝑒2

𝑃3

GSTree

GSTree inverséGSTree𝑃=𝑃1𝜙𝑃2𝜙𝑃3

21

L'application de TRT_CI pour l'indexation de texte

• La recherche des occurrences des mots :– Ajouter un champ dans chaque feuille du Trie qui

pointe vers une liste de toutes les positions des mots dans le texte.

• La recherche des facteurs dans un texte :– Utiliser un arbre des suffixes.

22

L’auto-complétion approchée

AppacoLibApproximate auto-complete Library

3ème Contribution

23

Auto-complétion

24

Auto complétion approchée

Xaut

No Results

Xaut

AutocompleteAutocomplete jqueryAutomobileAutourAutolibAutisme

Tolérer un certain nombre d'erreurs dans le préfixe tapé.

Erreur

25

Top-k auto complétion

Rapporter les k suggestions les plus hautement classées.

Aut

………………………………………….…….

K éléments.

26

La structure de données

Root

BA

CD

C

A

DBC

B

CD

DE

50

50

40

50

50 8

10

11

13

ABCD #50ADBC #40AC #10ABDE #8BA #11CD #131) Trie compact avec

un système de classement

2) La file de priorité

3) Tableau de hachage

27

La méthode de recherche• Étape 1: Trouver les nœuds

– Nœud : une solution exacte– Nœuds : des solutions approchées (avec une recherche naïve)

• Étape 2: la liste du top-k complétion.

Temps Rech approchée (Algo naïf) :

28

Réduire le nombre de branches sortantes testées.

Choisir la bonne branche dans l'arbre.

29

Réduire le nombre de branches sortantes testées.

ABxCDZZZ

H(AB?CD)%n =3

x y ………..

AByXY

0 1 2 3 4 5 ......... n

Mot requête = ABzCD

H(AB?CD)%n=3 , tab[3]=x

AB

x

CD

D={…

…}

Long des préfixes limitée (exemple: 5)

Temps de Vérification , cas moyenne :

30

Méthode hybride : Liste de substitutions + méthode naïve

Trie

Liste de substitutions

Naïve

Alignement multiple d’ADN

DiaWay

4ème Contribution

31

Introduction

• Alignement : consiste à trouver des similitudes entre deux ou plusieurs séquences et déterminer leurs homologies possibles.

- G C T G A T A T A G C T | | | | | | | | | | G G G T G A T - T A G C T

32

- G C T G A T A T A G C T | | | | | | | | | | G G G T G A T - T A G C T | | | | | | - G C T - A T - - C G C - | | | | A G C G G A - A C A C C T

L’alignement multiple

33

L’approche DiaWayBasé sur l’algorithme DiAlign**

** Morgenstren, B., Dress, A., Werner, T. : Multiple DNA and protein sequence alignmentbased on segment-to-segment comparison. 93(October) (1996) 1209812103 34

DiaWay: l'extraction des diagonales

• La Matrice Dot plot:

• S1 : ATTCCGACT• S2 : AATTCGCGT

M [i] [M[i][j]= =

1: Si Match0: Sinon

A T T C C G A C T

A 1 0 0 0 0 0 1 0 0

A 1 0 0 0 0 0 1 0 0

T 0 1 1 0 0 0 0 0 1

T 0 1 1 0 0 0 0 0 1

C 0 0 0 1 1 0 0 1 0

G 0 0 0 0 0 1 0 0 0

C 0 0 0 1 1 0 0 1 0

G 0 0 0 0 0 1 0 0 0

T 0 1 1 0 0 0 0 0 1

d1 : TT AA d2 : ATTCCG ATTCGCd3 : CCGA GCGT

>Tri des diagonalesD={d2, d3, d1}

>>Indexation de D.

35

DiaWay: l'inconsistance

• Inconsistance simple: S1: s2:• Inconsistance complexe:S1:S2:S3:

chevauchement

NP-complet **

** Subramanian, A.R., Kaufmann, M., Morgenstern, B. : DIALIGN-TX : greedy andprogressive approaches for segment-based multiple sequence alignment. Algorithmsfor molecular biology : AMB 3 (January 2008)

36

DiaWay: la résolution de l’inconsistance

1) Inconsistance chemin

2) InconsistanceAvec cheminTrouvé dans (1)

3) Inconsistance simple

37

DiaWay : l'étape finale de l'alignement

1) Mettreles fragmentsensemble

2) insérer les gaps (-).

Un ensemble consistant de diagonales D'= {}Un ensemble trié D’’={d0, d1, d2, d4, d3, d6, d5}

38

Expérimentations

Résultats pratiques

39

40

Les Dictionnaires

Mobydick 37 milles motsTown 47 milles mots

Anglais 213 milles motsWikiTitle 1,8 millions mots

R.A. avec Hachage

Dictionnaire WikiTitle (Wi) pour une erreurDictionnaire Anglais (En) pour une erreur

Dictionnaire WikiTitle (Wi) pour 2 erreursDictionnaire Anglais (En) pour 2 erreurs

Le temps d'insertion dans l'index

41

42

TRT_CI

43

TRT_CI

Aleksander Cislak et Szymon Grabowski Avec la distance de Hamming.

TRT_CI : 3 fois plus rapide , et stable

Aleksander Cislak et Szymon Grabowski

TRT_CI

Distance Hamming = 1 Type d’erreur Edit Distance = 3 Types d’erreurs

Temps 0< t <1 Temps : 0< t <1

Changement de temps / la taille de Dic

Augmente Stable

La 2ème méthodeTRT_CI

La 1ère MéthodeRA hachage

44

TRT_CI

𝑇𝑅𝑇 𝐶𝐼≈167 𝑙𝑎 𝑟𝑒𝑐h𝑒𝑟𝑐 h𝑒𝑒𝑥𝑎𝑐𝑡𝑒

La recherche exacte est l’opération de référence qui donne le temps d'exécution optimal.

45

Auto-complétion : Coté serveur, C/C++

Requête + top-k (en millisecondes) sur l'anglais (En) et sur les titres Wiki (Wi).

Construction du Trie En : 177 ms , Wi : 980 ms.

46

Auto-complétion : Coté serveur, liste de substitutions

Les listes de substitutions (SL) augmentent la taille de l’index de 0,7 Mo pour Anglais (En), et de 5 Mo pour Wiki (Wi).

Temps de requête avec et sans l'utilisation des listes de substitutions.

47

Auto-complétion : Coté serveur, La méthode Hybride.

48

Auto-complétion : Coté Client, JavaScript

Navigateur Chrome.Construction du TrieEn : 2.7 secondsWi : 13 seconds.

Navigateur Internet Explorer.Construction du Trie En : 30 s. Wi : 150 s.

Les diagonales initiales

Le nombre des diagonales consistantes est inférieur à 1% de l'ensemble des diagonales initiales.

DiaWay

49

Les diagonales consistantes.

Tests avec 10 séquences biologiques

DiaWay

50

DiaWay

Tests avec 2 séquences biologiques de grande taille.

51

Conclusion • Chegrane, I., Belazzougui, D.

Simple, compact and robust approximate string dictionary. Journal of Discrete Algorithms 28(0) (2014) 49 60 StringMasters 2012 & 2013 Special Issue (Volume 1).

• Chegrane, I., Belazzougui, D., Raffinot, M. Jquery ui like approximate autocomplete. International Symposium on Web Algorithms. (2015).

• Chegrane, I, c., Athmane, s., Chahrazed, i., Aicha, b.Diagonal consistency problem resolution in dialign algorithm. Bioinformatics (2015) 225 231, Lisbon, Portugal.

• Athmane, S., Chegrane, I., Chahrazed, I. DNA multiple alignment problem with the new diaway algorithm.ISPS 2015 (2015).

• Beloucif, M , Chegrane, I .State of the art about Approximate Pattern Matching. META’12 Tunis 27-31.

• Chegrane, I. Hadj Ameur, M.S. , Bensaou, N.Fast approximate string matching in dictionary using Trie and reverse Trie. in progress.

52

1) Les publications

Conclusion

• https://github.com/chegrane/compact-approximate-string-dictionary– Langage C Nb ligne code : 5766

• https://github.com/chegrane/TrieRTrie– Langage C Nb ligne code : 4444

• https://github.com/AppacoLib/api.appacoLib– Langage C Nb ligne code : 7593– JavaScript Nb ligne code : 3884

• https://github.com/chegrane/DiaWay_2.0 – C/C++ (Qt) Nb ligne code : 5453

53

Total == 27 140

2) Les librairies

Perspectives

1. Des solutions efficaces en pratique pour .

2. Utiliser les caractéristiques de chaque langue afin de proposer des solutions spécifiques.

3. Utiliser le parallélisme.

4. Utiliser les techniques de intelligence artificiel.

54

Thesis defense

55

Jury

Questions

Ibra Ma thèse

Les erreurs