M´emoire de fin d’´etude

Indexation parall`
ele des donn´
ees
g´
enomiques
NGUYEN Van Hoa
Responsable : Dominique LAVENIER
Equipe d’accueil : Symbiose, IRISA
18 novembre 2005


Remerciement
Je tiens `a remercier tout particuli`erement
Monsier Dominique Lavenier, mon responsable de stage, de m’avoir accueilli, soutenu et aid´e
tout au long de ces six mois,
Rumen Andonov pour ses judicieux conseils.
Un grand merci ´egalement `a toute l’´equipe Symbiose pour son accueil.


R´
esum´
e
Les banques de donn´ees g´enomiques sont de plus en plus volumineuses depuis quelques ann´ees. Elles sont devenues la ressource d’information principale de la biologie mol´eculaire
pour d´eterminer une histoire ´evolutive des organismes, ou pour d´eterminer des donn´ees fonctionnelles. Face `a leur croissance exponentielle, les outils actuels de recherche de similarit´es
devient lourd dans quelques ann´ees lorsqu’on d´esire effectuer une recherche syst´ematique.
Nous proposons la recherche par indexation parall`ele pour acc´el´erer les performances. Nous
pr´esentons ce mod`ele de recherche sur un cluster de machines : les noeuds travaillent ind´ependamment sur une partie des banques et le r´esultat final est la fusion de l’ensemble.
Mots-cl´
es : g´enomiques, indexation parall`ele, recherche de similarit´es, cluster de PC

Abstract
The genomic databases have been increasingly more and more for a few years. They became
the resource of principal information of molecular biology to determine an evolutionary
history of the organism, or to determine functional data. In face of their exponential growth,
the current tools for similar searching becomes heavy in a few years when we want to do the
systematic researches. We propose a model of research by parallel indexing to accelerate the
performances. We present this model of research on a cluster of machines : the nodes work
independently on part of the banks and the final result is the set fusion
Keywords : genomic, parallel indexing, search for similarities, PC cluster


Table des mati`
eres
1 Introduction
1.1 Contexte du stage . . . . . . . . . . . . . . . . .
1.2 Contexte biologique . . . . . . . . . . . . . . . .
1.2.1 Banques de donn´ees de s´equences d’ADN
1.2.2 La recherche de similarit´es . . . . . . . .
1.3 Heuristique de recherche d’alignement . . . . . .
1.4 Recherche par indexation parall`ele . . . . . . . .
1.5 Objectifs du stage . . . . . . . . . . . . . . . . .

.
.
.
.
.
.
.


.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.

.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.

.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.

.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.


1
1
2
2
3
4
4
5

2 Indexation pour la recherche de similarit´
es
2.1 Principe de l’indexation . . . . . . . . . . . . . . . . .
2.1.1 Exemple de recherche via l’indexation . . . . . .
2.1.2 Indexation des banques g´enomiques . . . . . . .
2.2 Les travaux ant´erieurs . . . . . . . . . . . . . . . . . .
2.2.1 Les structures de donn´ees . . . . . . . . . . . .
2.2.2 La recherche . . . . . . . . . . . . . . . . . . . .
2.3 M´ethodes d’indexation pour la recherche de similarit´es
2.3.1 Format de la table d’index . . . . . . . . . . . .
2.3.2 M´ethode de r´ef´erence . . . . . . . . . . . . . . .
2.3.3 Suppression des zones de faible complexit´e . . .
2.3.4 Discussion . . . . . . . . . . . . . . . . . . . . .
2.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . .

.
.
.
.
.

.
.
.
.
.
.
.

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

.
.
.
.
.
.
.
.
.

.
.
.

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

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


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

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

.
.
.
.

.
.
.
.
.
.
.
.

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

.
.
.
.
.
.
.
.

.
.
.
.

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

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


6
6
7
7
8
8
9
10
10
11
12
13
14

3 Indexation parall`
ele pour la recherche de similarit´
es
3.1 Principe . . . . . . . . . . . . . . . . . . . . . . . . . .
3.1.1 La tˆache de filtrage . . . . . . . . . . . . . . . .
3.1.2 La recherche . . . . . . . . . . . . . . . . . . . .
3.2 Mod´elisation du temps d’ex´ecution . . . . . . . . . . .
3.3 Plateformes ´etudi´ees . . . . . . . . . . . . . . . . . . .
3.3.1 Cluster de PC . . . . . . . . . . . . . . . . . . .
3.3.2 RDisk . . . . . . . . . . . . . . . . . . . . . . .
3.3.3 ReMiX . . . . . . . . . . . . . . . . . . . . . . .
3.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . .

.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

15
15

16
16
17
17
17
18
19
20

.
.
.
.
.
.

21
21
21
22
23
25
26

4 Ordonnancement
4.1 Principe d’ordonnancement . . . . . . . . . . . . . .
4.1.1 R´epartir les donn´ees g´enomiques . . . . . . .
4.1.2 Dupliquer une partie des donn´ees localement .
4.1.3 Algorithme d’ordonnancement . . . . . . . . .
4.2 Application `a l’ordonnancement des tˆaches de filtrage

4.3 Application `a l’ordonnancement des s´equences . . . .
i

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.


.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.

.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.


`
TABLE DES MATIERES

4.4 Simulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

ii
27
27

5 Impl´
ementation et r´
esultats
5.1 Plateforme et biblioth`eque
5.2 Impl´ementation . . . . . .
5.3 Param`etres d’indexation et
5.3.1 Les param`etres . .
5.3.2 Les r´esultats . . . .
5.4 Conlusion . . . . . . . . .

28
28
28
29
29
30
35

6 Conclusion et perspectives

. . . . . .
. . . . . .
r´esultats

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

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.

.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.


.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.

.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.

.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.


.
.
.
.
.
.

37


Table des figures
1.1

Croissance de Genbank . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3

2.1
2.2

Les arbres des suffixes pour le text ”tctagc” . . . . . . . . . . . . . . . . . . . . . . . . . .
Les tableaux de suffixes pour le text “tctagc” . . . . . . . . . . . . . . . . . . . . . . . . . .

8
9

3.1
3.2
3.3

3.4

Diagramme de traitement d’une requˆete par
Configuration de cluster de PC . . . . . . .
Configuration de RDisk . . . . . . . . . . . .
Configuration de ReMiX . . . . . . . . . . .

4.1
4.2
4.3

R´epartition de 16 clusters cons´ecutifs et non-cons´ecutifs sur 4 processeurs . . . . . . .
R´epartition et duplication 16 clusters cons´ecutifs a
` 4 processeurs . . . . . . . . . . . . .
Duplication d’une partie des donn´ees en local niveau 2 (r´epartition cons´ecutives et

22
22

non-cons´ecutives) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Temps d’ordonnancement des tˆ
aches de filtrage pour 48 processeurs, W=9 (calcul´e en

23

4.4

micro seconds) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Temps d’ordonnancement des tˆ
aches de filtrage pour 48 processeurs, W=9 (calcul´e en


24

4.5

micro seconds) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Temps d’ex´ecution des N*tˆ
aches de filtrage pour chaque plateforme avec diff´erent ni-

25

4.6

l’index . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . .

15
18
19
20

veau de duplication des cluster (la longueur de requˆete = 2077, la taille de la banque
FASTA est de 9 Go, le nombres de noeuds pour le cluster de PC est de 32 ; et RDisk
de 48 ; et ReMiX de 8) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Temps de construction de la banque sur chaque plateforme correspondant niveau de

26


4.7
4.8

duplication des s´equences (M = 10.000) . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Temps d’ex´ecution des requˆetes avec diff´erents niveaux de duplication des clusters . .

26
27

5.1
5.2
5.3

Mod`ele de l’impl´ementation pour un cluster PC a
` K noeuds . . . . . . . . . . . . . . . .
Deux ´etapes principales de traitement d’une requˆete pour un cluster de PC . . . . . .
Temps d’ex´ecution de l’´etape de filtrage par rapport a
` un nombre de noeuds diff´erents

29
29

(pas de duplication des donn´ees) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Temps d’ex´ecution de l’´etape de filtrage par rapport au niveaux de concurrence des

30

5.4
5.5
5.6

5.7

clusters (K=32) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Temps d’extraction de la banque par rapport a
` un nombre de noeuds diff´erents . . . .
Temps de traitement des requˆetes par rapport a
` un nombre de noeuds diff´erents . . . .
Comment le temps de traitement des requˆetes se passe pour 16 noeuds (calcul´e en

31
31
32

seconds) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

34

iii


Chapitre 1
Introduction
Le d´eveloppement des techniques de la biologie moderne a conduit au s´equencage en
masse des g´enomes. Les biologistes mol´eculaires veulent extraire et ´etudier l’information tr`es
rapidement. Ils effectuent quotidiennement des recherches de similarit´es pour d´eterminer une
histoire ´evolutive des organismes, ou pour d´eterminer des donn´ees fonctionnelles. Plusieurs
approches, exhaustives ou `a base d’index existent pour faciliter la recherche. N´eanmoins,
la n´ecessit´e d’acc´el´erer les recherches se d´eveloppe tous les jours. D`es qu’un nouveau g`ene
est s´equenc´e, l’´etape suivante est l’exploration des banques nucl´eotides pour extraire des
similarit´es entre un g`ene connu et un g`ene nouveau.


1.1

Contexte du stage

J’ai effectu´e mon stage dans l’´equipe Symbiose1 , `a l’Institut de Recherche en Informatique
et Syst`emes Al´eatoires (IRISA). La probl´ematique g´en´erale de cette ´equipe correspond au
champ de la bio-informatique, c’est `a dire `a la mod´elisation des donn´ees g´enomiques pour
assister le biologiste mol´eculaire dans la formulation et la d´ecouverte de nouvelles connaissances. L’´equipe s’articule autour de 3 grands axes : l’analyse linguistique des s´equences,
l’analyse et l’identification de syst`emes dynamiques et l’architecture et le parall´elisme. Dans
le dernier axe, il y a deux projets ils s’appellent RDisk (un cluster de disques reconfigurables)
et ReMiX (un cluster de m´emoires reconfigurables). L’objectif des deux projets est la parall´elisation des traitements coˆ
uteux en g´enomique pour en acc´el´erer fortement l’ex´ecution. La
mise en oeuvre vise les super-calculateurs, les grilles de calcul et les architectures sp´ecialis´ees.
1

http ://www.irisa.fr/symbiose

1


1.2 Contexte biologique

1.2

2

Contexte biologique

La biologie mol´eculaire ´etudie l’ADN, l’ARN, les prot´eines et leurs interactions. Ces trois

´el´ements ont en commun d’ˆetre des chaˆınes de petites mol´ecules. L’ADN contient l’information g´en´etique compl`ete permettant de d´efinir la structure, la fonction, le d´eveloppement et
la reproduction d’un organisme. Les g`enes qui sont des portions d’ADN sont le support de
cette information g´en´etique et les prot´eines sont les produits de ces g`enes. Les g`enes sont
constitu´es d’un enchaˆınement de 4 types de nucl´eotides : Ad´enine (A), Cytosine (C), Guanine (G), et Thymine (T). On peut consid´erer l’ADN comme un tr`es grand texte avec un
vocabulaire de 4 lettres : A,C,G,T. Les prot´eines sont, par contre, les macromol´ecules de l’activit´e et de la structure. Elles assurent le fonctionnement des processus cellulaires et servent
de mat´eriau de construction pour la cellule. L’unit´e de base des prot´eines est l’acide amin´ee.
On en trouve 20 diff´erents ayant des caract´eristiques physico-chimiques vari´ees. Le rˆole de
l’ARN est interm´ediaire dans le sens o`
u sa fonction principale est de transcrire l’information
se trouvant dans l’ADN en prot´eine [8].

1.2.1

Banques de donn´
ees de s´
equences d’ADN

En 1965, la premi`ere s´equence de 100 bases a ´et´e publi´ee [5]. D`es la fin des ann´ees 70,
grˆace `a une nouvelle technique de s´equencage, les s´equences ont ´et´e produites cent fois plus
rapidement. En r´epondant `a l’int´erˆet croissant port´e `a l’analyse de ces informations, la communaut´e biologique a d´ecid´e en 1978 d’´etablir une base de donn´ees rassemblant l’ensemble de
ces ressources afin de collecter, organiser et distribuer les informations et les annotations sur
les s´equences. A partir de cette d´ecision, toutes les s´equences produites sont collect´ees dans
les banques de donn´ees g´enomiques dont les trois banques principales sont : the Euroean
´
Molecular Biology (EMBL) en Europe, Genbank aux Etats-Unis
et the DNA Data Bank of
Japan (DDBJ) au Japon. Les banques de donn´ees sont mises `a jour `a partir d’une collaboration internationale. Ainsi, depuis sa cr´eation en 1982, la taille de Genbank n’a cess´e de
croˆıtre `a une vitesse toujours plus rapide chaque ann´ee. On estime que la taille de Genbank
double tous les 15 ou 16 mois [8] depuis sa cr´eation (fig 1.1)2 .
Les banques de donn´ees peuvent ˆetre organis´ees en plusieurs structures : texte, XML, donn´ees relationnelles etc. Nous prenons un exemple : le format FASTA. Dans cette structure,

2

http ://www.ncbi.nlm.nih.gov/Genbank


1.2 Contexte biologique

3

Fig. 1.1 – Croissance de Genbank
les s´equences d’ADN ou d’acides amin´es sont des donn´ees non structur´ees. Elles sont stock´ees sous la forme de grands fichiers textuels qui peuvent ˆetre soit des fichiers personnels
(pr´esents dans un espace personnel) ou soit des fichiers publics (s´equences des banques). Une
s´equence au format FASTA a deux parties : la ligne de d´efinition et la s´equence d’ADN.
>Ligne de d´efinition
La s´equence d’ADN
>..................

– la ligne de d´efinition doit commencer par le caract`ere ”>”. Cela permet de mettre
plusieurs s´equences dans un mˆeme fichier. Apr`es le caract`ere ”>” on trouve un identificateur unique (ID) et une petite description. La description est libre et ne contient pas
de caract`ere terminal de ligne ;
– la s´equence d’ADN est pr´ec´ed´ee imm´ediatement de la ligne de d´efinition. La s´equence
est donn´ee sous forme de lignes de 80 caract`eres au maximum.

1.2.2

La recherche de similarit´
es

Lorsque l’on recherche la fonction d’un g`ene ou d’une prot´eine inconnue, on essaye de
trouver des similarit´es entre sa s´equence d’acides amin´es ou de ses bases d’ADN et celles

de mol´ecules connues et ´etudi´ees. La similarit´e est une mesure de ressemblance entre deux
s´equences prot´eiques ou nucl´eiques. Elle est bas´ee sur la pourcentage d’identit´e entre les deux
s´equences compar´ees. La recherche de similarit´e consiste `a rep´erer des r´egions similaires entre
une s´equence, appel´ee s´equence requˆete, et une s´equence cible. Pour ce faire, on proc`ede par


1.3 Heuristique de recherche d’alignement

4

alignement de s´equences. Les types d’alignement sont :
– alignement local : cet alignement est utilis´e pour d´etecter les r´egions locales de hautes
similarit´es entre deux s´equences ayant des longueurs diff´erentes ;
– alignement global : le but de cet alignement est de mesurer la ressemblance globale
entre deux s´equences. Ceci est effectu´e en alignant la totalit´e des deux s´equences ;
– gaps et insertion : en alignant, on peut ´egalement introduire des d´ecalages, c’est `a
dire une absence de lettre sur l’une ou sur l’autre des s´equences que l’on notera ”-”
et qui correspond biologiquement aux insertions/delections. Plus pr´ecis´ement, c’est un
´ev´enement de mutation qui ´elimine une partie d’un g`ene, ou en ins`ere une nouvelle.

1.3

Heuristique de recherche d’alignement

La recherche des s´equences similaires correspond `a la recherche par le contenu dans de
grands ensembles de donn´ees. On doit parcourir toutes les donn´ees de l’ensemble consid´er´es.
Il existe plusieurs solutions pour trouver des alignements. Les premiers algorithmes, comme
celui de Smith-Waternam en 1981, utilisent des techniques de programmation dynamique, et
sont d’une complexit´e quadratique [28]. BLAST bas´e sur une heuristique est apparu en 1990
[1]. BLAST permet d’ex´ecuter dans un temps raisonnable la comparaison de deux s´equences

de quelques centaines `a quelques milliers de nucl´eotides. BLAST est devenu la r´ef´erence
en exploration de base de donn´ees g´enomiques. Cependant, BLAST devient lourd lorsqu’on
d´esire effectuer une recherche syst´ematique dans des banques dont la taille est de l’ordre
109 `a 1010 r´esidus. Il y a deux probl`emes : la capacit´e calculatoire et le temps d’acc`es aux
donn´ees. Pour acc´el´erer les performances, il existe deux fa¸cons :
– l’impl´ementation parall`ele de BLAST sur un cluster de stations : TurboBLAST [22],
mpiBLAST [7] et parallelBLAST [23].
– l’ajout d’acc´el´erateurs mat´eriels : unit´es de traitement sp´ecialis´ees (en technologie ASIC
ou reconfigurable [RDisk]) r´eparties sur des cartes d’extension.

1.4

Recherche par indexation parall`
ele

Nous pouvons am´eliorer les performances de recherche de similarit´es en indexant les donn´ees g´enomiques. L’index nous permet de pointer directement sur des donn´ees pertinentes.
L’id´ee est de chercher seulement dans une petite partie des banques. On construit une table


1.5 Objectifs du stage

5

d’index qui contient, pour chaque mot de taille W, les indices des occurrences de ce mot. Ce
pr´e-traitement du texte facilite la recherche d’un mot de taille W quelconque en permettant
par une simple lecture de la table de cibler exactement toutes les s´equences contenant ce
mot dans le texte original. Cependant, la table d’index est n´ecessairement bien plus grande
que le texte dont elle est issue.

1.5


Objectifs du stage

L’objectif de mon stage ´etait d’´etudier la parall´elisation de la recherche par indexation.
Plus pr´ecis´ement il s’agissait :
– de construire un mod`ele de recherche de similarit´es par indexation ;
– de proposer un algorithme d’ordonnancement (`a d´eterminer) qui distribue les tˆaches de
mani`ere `a optimiser le temps d’ex´ecution ;
– d’´etudier le taux de duplication d’une partie des donn´ees ;
– de valider le mod`ele le mod`ele par impl´ementation sur cluster PC.
Dans la suite du rapport nous verrons dans la section 2 plus en d´etails la recherche de
similarit´es par indexation. Puis, dans la section 3 nous pr´esenterons un mod`ele de la recherche
de similarit´es par indexation parall`ele. Dans la partie suivante nous pr´esenterons l’algorithme
d’ordonnancement des tˆaches. Enfin dans la section 5, nous validerons le mod`ele par une
impl´ementation sur un cluster de 32 noeuds.


Chapitre 2
Indexation pour la recherche de
similarit´
es
L’indexation est une technique qui acc´el`ere la recherche de donn´ees. Elle a ´et´e appliqu´ee
avec beaucoup de succ`es dans plusieurs secteurs de l’informatique. Pour l’instant, plusieurs
m´ecanismes d’indexation ont ´et´e d´evelopp´es, chacun adapt´e `a un type de donn´ees et `a un
type de recherche. L’indexation des textes est tr`es bien avanc´ee. Mais pour quelques types
de donn´ees, en particulier des donn´ees des s´equences biologiques, il n’y a pas de crit`eres
pr´ecis pour faire de l’indexation. La difficult´e dans ce secteur c’est que l’on ne cherche pas
des s´equences ou des sous-s´equences biologiques exactes, mais on emploie des techniques de
recherche d’appariement non exactes.


2.1

Principe de l’indexation

Lorsque que l’on veut faire de la recherche de similarit´es dans un texte, il y a deux
approches possible. La premi`ere consiste `a pr´e-traiter la requˆete. Cette approche a donn´e
lieu `a plusieurs travaux [11] mais cette fa¸con de faire g´en`ere beaucoup trop de mots, ce qui la
rend peu performante. La seconde approche consiste `a pr´e-traiter le texte lui-mˆeme. Cela est
d’autant plus fonctionnel que le texte est long et que plusieurs recherches seront effectu´ees.
Une structure de donn´ees, la table d’index, est alors construite pour acc´el´erer la recherche
d’un motif dans ce texte. Il y a deux ´etapes distinctes dans l’indexation :
– construction de l’index : cr´eer une structure de donn´ees `a partir du texte sur lequel on
veut faire des recherches. Celle-ci n’a pas besoin d’ˆetre reconstruite `a chaque requˆete
sauf s’il y a modification du texte ;
6


2.1 Principe de l’indexation

7

– traitement des requˆetes : c’est la phase de recherche proprement dite ; elle se fait grˆace
`a la table d’index et ne n´ecessite pas de relecture du texte original.

2.1.1

Exemple de recherche via l’indexation

Prenons l’exemple d’une recherche lexicographique dans une biblioth`eque. Nous avons
devant nous quinze livres. Ils ne sont pas tri´es et il n’y a pas d’information sur leur contenu.

Nous souhaitons trouver tous les livres qui contiennent le mot “plateforme”. Par ailleurs, on
sait que dans certains livres le mot est ´ecrit diff´eremment (par exemple “plate-forme”) et qu’il
peut y avoir des fautes de frappe. Pour effectuer cette recherche, nous avons trois solutions :
– soit lire tous les livres un par un et relever au fur et `a mesure les livres qui contiennent
les mots commen¸cant par “plate”. Ensuite, on v´erifie s’il s’agit bien d’une forme du mot
“plateforme”;
– soit g´en´erer toutes les variantes possibles (mais acceptables) du mot et les rechercher
une par une dans les livres ;
– soit construire un tableau qui associe aux cinq premi`eres lettres de tous les mots de la
biblioth`eque, le num´ero du livre dans lequel on le trouve.
Pour la premi`ere solution, il est n´ecessaire de lire tous les livres pour chacune des requˆetes.
C’est l’approche utilis´ee dans BLAST. La seconde risque de g´en´erer beaucoup de mots diff´erents, ce qui implique autant de recherches et de relectures de la biblioth`eque que de mots
g´en´er´es. Il y a d’autant plus de mots g´en´er´es que le mot recherch´e est long. C’est la m´ethode
des approches par pr´etraitement de la requˆete. La troisi`eme solution est celle de l’indexation.
On ne lit l’ensemble des livres qu’une seule fois quand on construit l’index. Ensuite quelque
soit le mot recherch´e, on saura imm´ediatement `a quel endroit le trouver. On a une table
d’index compos´ee d’une colonne cl´es (ou entr´ees) et d’une colonne donnant les occurrences
de celles-ci.

2.1.2

Indexation des banques g´
enomiques

L’utilisation de l’indexation pour la recherche de similarit´es dans les banques de donn´ees
g´enomiques est, ´evidemment, quelque peu diff´erente. On ne distingue pas les mots de la
mˆeme mani`ere. Il n’y a pas, comme dans un texte en langage naturel, d’espaces entre les
mots. Un mot peut ˆetre n’importe quelle sous-suite de nucl´eotides de la banque. Ainsi pour
l’indexer, on utilise tous les mots d’une longueur donn´ee W comme sur la figure suivant. On



2.2 Les travaux ant´
erieurs

8

consid`ere tous les mots, y compris ceux qui se chevauchent.
W
✛
✲
TGTTGTTTATTGTTGCCTGCATGTATACCTGCTCACT
mot1 TGTTGTTTA
mot2 GTTGTTTAT
TGTTTATTG
mot3

Les requˆetes sont trait´ees selon le mˆeme d´ecoupage des mots. Chaque mot de longueur W
de la requˆete est recherch´e dans la table d’index.

2.2

Les travaux ant´
erieurs

2.2.1

Les structures de donn´
ees

– Les arbres des suffixes [13] : c’est une structure de donn´ees refl´etant les caract´eristiques

internes des s´equences. Dans les arbres des suffixes chaque noeud interne reliant des fils
est une unit´e du texte index´e et les feuilles sont les indices des positions o`
u commence le
mot lu en partant de la racine de l’arbre jusqu’au p`ere de la feuille (voir figure 2.1). Cette
structure nous permet de chercher toutes les sous-s´equences. Pour r´eduire l’espace, on
utilise un algorithme de compression.

Fig. 2.1 – Les arbres des suffixes pour le text ”tctagc”
– Les tableaux de suffixes [17] : ce sont des tableaux contenant tous les indices aux
suffixes des textes tri´es dans l’ordre (alphab´etique) lexicographique. Chaque suffixe est


2.2 Les travaux ant´
erieurs

9

une chaˆıne commen¸cant `a une certaine position dans le texte et finissant `a la fin du
texte. En fait, c’est une version sous forme de tableau des arbres des suffixes qui permet
de prendre moins de place en m´emoire (fig 2.2).

Fig. 2.2 – Les tableaux de suffixes pour le text “tctagc”
– q-grams (indexing scheme) [21], [19] : toutes les sous chaˆınes de taille q (les q-grams)
sont rang´ees dans l’index avec l’ensemble de leurs positions dans le texte. Cette approche
nous permet de chercher des sous-s´equences de longueur q.

2.2.2

La recherche


Gonzalo Navarro a abord´e dans [11] trois m´ethodes de recherche :
– la g´en´eration de voisinages (neighborhood generation) : g´en´eration de toutes les chaˆınes
issues de la requˆete qui sont `a une distance d’edition inf´erieure `a un seuil k ; puis
recherche de chacune d’elle dans l’index ;
– le partitionnement en recherche d’appariement exact (partitioning into exact searching) : s´election les sous-chaˆınes ; puis recherche de chacune de ces sous-chaˆınes dans
l’index et enfin comparaison des zones de texte alentours ;
– le partitionnement interm´ediaire (intermediate partitioning) : extraction des sous-chaˆınes ;
puis pour chacun recherche des voisinages proches dans l’index.
La premi`ere m´ethode prend plus de temps si la chaˆıne requˆete est longe car elle g´en`ere plus
de voisinages ´etendus. Rigoutsos et Califan ont utilis´e la deuxi`eme m´ethode pour faire la
recherche (avec graps et non-appariement) d’indexation dans les bases de donn´ees g´enomiques
[29]. Les index, ou les tables de consultation sont fortement redondants et bas´es sur un mod`ele
probabiliste. Pour chaque intervalle de longueur W, la structure de recherche FLASH stocke,
dans une table de hachage, toutes les sous-s´equences possibles contigues et non-contigues de
longueur m qui commencent par la premi`ere base dans l’intervalle m < W. Par cons´equent,
la taille d’index est tr`es grande ; les auteurs parlent d’un index de 2.8 Go pour une base de


2.3 M´
ethodes d’indexation pour la recherche de similarit´
es

10

donn´ees de 10 millions de paires de bases [9].
Par ailleurs, Fondrat et Dessen ont propos´e la m´ethode RAMdb pour trouver un pattern
court dans les bases de donn´ees g´enomiques [30]. Chaque s´equence g´enomique est index´ee
par un intervalle de recouvrement constitutif en structure de table de hachage. Pour chaque
intervalle, une liste associ´ee au nombre des s´equences et des offsets est stock´ee, permettant
de localiser rapidement n’importe quel motif. CAFE utilise la puissance de l’algorithme de

compression, il obtient une table d’index de taille raisonnable par rapport `a la base de donn´ees
index´ee (de 2 a 3 fois plus grande). Stefan Burkhardt a utilis´e les tableaux des suffixes avec
la m´ethode de partitionnement et de recherche d’appariement approximatif. Cette technique
est bas´ee sur les q-grams [17].

2.3

M´
ethodes d’indexation pour la recherche de similarit´
es

2.3.1

Format de la table d’index

La table d’index que nous avons choisi d’utiliser contient, en plus du num´ero des s´equences
comprenant l’occurrence du mot r´ef´erenc´e dans la banque, les V lettres pr´ec´edant ce mot et
les V lettres suivantes. On appellera ces deux mots voisinage gauche VG et voisinage droit
VD.
voisinage gauche
✛

mot r´ef´erenc´e

✲ ✛

voisinage droit

✲ ✛


✲

TGTTGTTGTTTTTATTGTTGCCTGCATGTATACCTGCTCACTGAACAC

Cette information suppl´ementaire dans la table d’index va permettre, au moment de la phase
de traitement d’une requˆete de ne s´electionner que les meilleurs r´esultats. C’est `a dire, ceux
dont les voisinage gauche et le voisinage droit sont les plus similaires aux voisinages de la requˆete sans avoir besoin de consulter la banque de donn´ees. La s´election s’effectue grˆace `a une
fonction de score qui ´evalue la similarit´e des voisinages, lui attribue un score et ne renvoie que
les candidats dont le score d´epasse un certain seuil. La taille de la table d’index est ´egale `a 4W .


2.3 M´
ethodes d’indexation pour la recherche de similarit´
es

cl´e

occurence
VG0.0

VD0.0

NbSeq0.0

VG0.1

VD0.1

NbSeq0.1


VG0.2

VD0.2

NbSeq0.2

VG1.0

VD1.0

NbSeq1.0

VG1.1

VD1.1

NbSeq1.1

mot2

VG2.0

VD2.0

NbSeq2.0

...

...


...

...

VGN.0

VDN.0

NbSeqN.0

VGN.1

VDN.1

NbSeqN.1

mot0

mot1

motN

11

Tableau 1 : Structure g´en´erale de table d’index

2.3.2

M´
ethode de r´

ef´
erence

La construction de l’index (banque index´ee) est obtenue `a partir de la banque au format
FASTA, appel´e F. Soit S une s´equence de F, mi un mot de longueur W commen¸cant `a l’indice
i dans S et V la longueur des voisinages gauche et droit. Les mots mi sont pris non-contigus,
c’est `a dire nous ne prenons qu’un mot tous les J caract`eres. Pour toute s´equence S de F,
pour tout mot mi de S avec i tel que V ≤ i ≤ |S| − (V + W ), `a l’entr´ee correspondante `a mi
de l’index on ajoute :
– le num´ero de s´equence S dans F ;
– le mot VG de longueur V lu `a l’indice i-V ;
– le mot VD de longueur V lu `a l’indice i+V ;
Par exemple, la banque F contient les deux s´equences suivant. La longueur du mot est W=2,
et la longueur des voisinages V=3 et le saut J=2 :


2.3 M´
ethodes d’indexation pour la recherche de similarit´
es

12

Seq No 1 : TGCCTGCATGTATACCTGCTCA
Seq No 2 : CTGAACACATGCAGTGCCTAAGAA
mot cl´e
AA
AC
AT

CA

...
GT
TG

occurence
CTG

CAC

2

CCT

GAA

2

TAT

CTG

1

TGT

ACC

1

TGC


GTA

1

GAA

CAT

2

ACA

TGC

2

ATG

GTG

2

...

...

...

CAT


ATA

1

GCA

GCC

2

ACA

CAG

2

Tableau 2 : Contenu de la table d’index

Pour la phase de traitement d’une requˆete, chaque mot de longueur W, en incluant les
mots se chevauchant, est recherch´e dans la table d’index. S’il existe au moins une occurrence
de ce mot, on compare une `a une les lettres du voisinage et on calcule un score en fonction
du nombre de bases identiques. Si ce score est ´egal ou sup´erieur `a un seuil fix´e au pr´ealable,
le num´ero de la s´equence dont est issu ce mot est ajout´e `a la liste des s´equences r´esultats.
Cette m´ethode n’indexe qu’un mot sur J, ce qui r´eduit consid´erablement la taille de l’index.
Ceci est un crit`ere important ´etant donn´e la taille de l’index par rapport `a la taille de la
base de donn´ees. De plus, l’information sur le contexte de l’occurrence (voisinage gauche et
droit) augmente la taille de la table en m´emoire ; il est donc n´ecessaire en compensation de
ce surplus d’information de r´eduire le nombre de mots index´es. Cependant, cet avantage a
pour contrepartie de rendre la recherche moins sensible.


2.3.3

Suppression des zones de faible complexit´
e

La m´ethode pr´ec´edente utilise aucun crit`ere pour choisir les mots r´ef´erents. Pour augmenter la sensibilit´e nous pouvons choisir les mots r´ef´erents en se basant un crit`ere de complexit´e
qui nous aide `a prendre uniquement les mots int´eressants. Nous pouvons ´eviter les zones de
faible complexit´e ; par exemple : AAAAAAACAAAAAAAAATAAAAAA. La construction
de l’index est bas´ee sur la complexit´e. Soit S une s´equence de F, la construction de l’index


2.3 M´
ethodes d’indexation pour la recherche de similarit´
es

13

est alors la suivant :
– calcul de la complexit´e des positions de s´equences ;
Xj = (nA + 1) ∗ (nC + 1) ∗ (nG + 1) ∗ (nT + 1) o`
u nA, nC, nG et nT sont les sommes
des bases correspondant `a A, C, G et T dans la fenˆetre |j-x, j+x| ; avec x < j < |S| − (x).
– on ne prend que le mot mi si la complexit´e de tous W caract`eres de mi est sup´erieur `a
un certain seuil avec i tel que V ≤ i ≤ |S| − (V + W ).
A l’entr´ee correspondante `a mi : on ajoute :
– l’ordre de s´equence S dans F ;
– le mot VG de longueur V lu `a l’indice i-V ;
– le mot VD de longueur V lu `a l’indice i+V ;
Par exemple, nous prenons la s´equence suivante avec une longueur du mot W=2, une longueur

des voisinages V=3, une taille de fenˆetre |i-2, i+2| et un seuil de 11
0

5

10

AGTAAAATTATAAAAATTTTAA
AGTAA
complexit´e : 16
GTAAA
16
TAAAA
10
AAAAT
10
AAATT
12
AATTA
12
ATTAT
12
TTATA
12
AGTAAAATTATAAAAATTTTAA (linge a)
TA ATTAT
ATT
(ligne b)

Dans cet exemple, la ligne b montre les caract`eres de la s´equence originale (la ligne a) qui

ont pass´e un seuil de complexit´e (de 11). Nous prenons les mots dans la ligne b pour les
ajouter dans la table d’index.
Pour la phase de traitement d’une requˆete, on proc`ede de la mˆeme mani`ere en prenant garde
d’appliquer le mˆeme crit`ere que celui de la phase d’indexation. Cela nous garantit que s’il
existe une zone de match significative entre la s´equence requˆete et la cible. On s´electionnera
les mˆemes graˆınes pour l’une comme pour l’autre. De cette fa¸con, on s’assure qu’`a cette zone
correspond au moins une entr´ee de la table d’index.

2.3.4

Discussion

Pour la derni`ere m´ethode, les mots index´es et les mots recherch´es n’´etant pas s´electionn´es
au hasard. Cette m´ethode a une sensibilit´e plus forte que la m´ethode de r´ef´erence. Elle


2.4 Conclusion

14

permet, non seulement de n’´eviter que des zones de faible complexit´e de la banque, mais en
plus, elle acc´el`ere ´enorm´ement la phase de traitement des requˆetes. En effet, l’´economie de
mots index´es lors de l’´etape d’indexation se retrouve au niveau nombre de mots recherch´es
dans l’index.

2.4

Conclusion

Nous consid´erons des banques de s´equences g´enomiques de 100 Gbp. Les s´equences sont

tron¸conn´ees en petits morceaux (mot r´ef´erenc´e) qui sont regroup´es par mot identique de
taille W. Nous appelons un cluster un tel groupe. La taille des clusters est tr`es variable. Il
y a C = 4W clusters dans la banque index´ee. Finalement, nous avons deux banques : une
banque index´e et une banque au format FASTA


Chapitre 3
Indexation parall`
ele pour la recherche
de similarit´
es
3.1

Principe

Les banques de donn´ees g´enomiques sont de plus en plus volumineuses. L’indexation nous
permet de pointer seulement sur des donn´ees appropri´ees pendant le processus de recherche.
C’est `a dire que nous extrayons seulement les s´equences ayant un potentiel de similarit´e
avec une requˆete avant de commencer la recherche de similarit´es. La figure 3.1 r´esume le
traitement global.

Fig. 3.1 – Diagramme de traitement d’une requˆete par l’index

15


3.1 Principe

3.1.1


16

La tˆ
ache de filtrage

La s´equence requˆete est une s´equence d’ADN. On veut savoir s’il y exit des s´equences
similaires `a la s´equence requˆete. On d´ecouple la s´equence requˆete en N mots requˆete. La
longueur des mots est W. Pour chaque mot requˆete, on acc`ede directement au mot r´ef´erence
correspondant dans la banque index´ee. Ensuite, on compare les voisinages du mot requˆete
avec ceux des mots occurrences dans le cluster pour ´evaluer la similarit´e. On consid`ere les
comparaisons des voisinages pour un mot requˆete comme une tˆache de filtrage. Voici un
exemple : on a un mot requˆete CA avec ses voisinages `a gauche et `a droite dans la s´equence
requˆete ci-dessous. Consid´erons la table d’index de l’exemple puis en 2.3.2
Requˆete : ATTCCTCACATTAGGGTCATTAC
Tˆache = comparer avec le cluster CA
Pour le mot requˆete CA, la tˆache s’effectuer de la mani`ere suivante : on acc`ede directement
au cluster CA dans la banque index´ee. Ensuite, on compare le voisinage `a gauche (CCT) et `a
droite (CAT) du mot requˆete CA avec trois paires occurrences de voisinages ({GAA,CAT},
{ACA,TGC}, {ATG,GTG}) pour ´evaluer la similarit´e. Nous ne s´electionnons les candidats
que si leurs scores de similarit´e d´epassent un certain seuil.

3.1.2

La recherche

Nous avons deux banques de donn´ees : la banque de s´equences au format FASTA et la
banque index´ee. La s´equence requˆete est d´ecoup´ee en N mots requˆetes, chaque mot requˆete
est consid´er´e comme une tˆache de filtrage. En se basant sur notre approche, il y a quatre
´etapes pour ex´ecuter une requˆete :
– premi`erement, pour une tˆache i, on acc`ede imm´ediatement au cluster correspondant au

mot requˆete i, et on compare les deux voisinages avec ceux du cluster ; le r´esultat de la
tˆache i est un ensemble de num´eros de s´equences.
– deuxi`emement, c’est l’´etape de fusion des r´esultats des N tˆaches pour trouver l’ensemble
des num´eros de s´equences. En effet, pour les r´esultats il y a des num´eros de s´equences
en double, en triple, etc.
– troisi`emement, `a partir de cet ensemble de num´eros de s´equences, on construit une
banque FASTA en extrayant directement les s´equences `a partir de la banque FASTA.


3.2 Mod´
elisation du temps d’ex´
ecution

17

– finalement, c’est l’´etape de recherche des similarit´es en utilisant BLAST avec deux
entr´ee : la requˆete et la banque qui vient d’ˆetre construite.

3.2

Mod´
elisation du temps d’ex´
ecution

Le temps d’ex´ecution d’une tˆache de filtrage et le temps d’extraction d’une s´equence sont
calcul´es par les deux formules suivant :
1
TF iltrage = Tacces + Scls ∗ ( T1 + Texec
)
f


TExtraction = Tacces + Sseq ∗ T1

f

O`
u : Tacces : temps d’acc`es aux donn´ees ;
Scls : taille de cluster ;
Sseq : taille de s´equence ;
Tf : vitesse de transfert des donn´ees (Mo/s) ;
Texec : puissance de comparaison (Mo/s) ;
Pour acc´el´erer le processus de recherche, la recherche de similarit´es est parall´elis´ee sur un
cluster de machines o`
u les banques g´enomiques (index´ee et format FASTA) sont r´eparties
localement sur chacun des noeuds. Plus pr´ecis´ement, les N tˆaches de comparaison et la
construction de la banque au format FASTA s’effectuent en parall`ele. Supposons qu’il y a
K noeuds dans un cluster de machines. Les N tˆaches requˆete s’effectuent en parall`ele sur K
noeuds. En moyen, un noeud fera

N
K

tˆaches de filtrage et extraira

total de traitement d’une requˆete est :
N
Trequete = K
∗ TF iltrage

M

K

s´equences. Le temps

+M
K ∗ TExtraction

Le temps d’ex´ecution d’une requˆete est calcul´e en se basant sur les param`etres d’un cluster de
machines. Dans le contexte de l’´equipe Symbiose nous proposons trois plateformes : cluster
de PC, RDisk et ReMiX.

3.3
3.3.1

Plateformes ´
etudi´
ees
Cluster de PC

Le nombre de noeuds dans cette plateforme est de 32. Chaque noeud est un PC comprenant
une m´emoire local et un disque dur. La communication et la synchronisation entre les noeuds
sont g´er´ees `a l’aide d’une biblioth`eque de communication MPI ou RMI. Les deux banques de


3.3 Plateformes ´
etudi´
ees

18


donn´ees sont r´eparties localement sur chacun des noeuds. La s´equence requˆete est d´ecoup´ee
en un ensemble de mots requˆetes qui sont distribu´es aux noeuds. Les mots requˆetes sont
ex´ecut´es s´equentiellement et ind´ependemment sur les 32 noeuds. Les r´esultats des mots
requˆetes sont envoy´es `a un noeud d´edi´e qui les fusionne pour avoir un ensemble de num´eros
de s´equences `a aligner. A partir de cet ensemble, une banque au format FASTA est construite.
Dans cette plateforme on n’a pas besoin de communication inter-noeuds sauf pour envoyer
les mots requˆetes et pour fusionner les r´esultats. Voici les param`etres du cluster de PC :
Tacces = 7 msec
Tf = 20 Mo/sec
Texec = 10 Mo/sec

Fig. 3.2 – Configuration de cluster de PC

3.3.2

RDisk

RDisk est un cluster de disques reconfigurables. Dans cette plateforme, il y a un ordinateur,
appel´e l’hˆote, connect´e `a 48 cartes RDisk par un port Ethernet [4]. Chaque carte RDisk
comprend un disque dur et un filtre FPGA (Field-Programmable Gate Array), un type de
puce de logique qui peut ˆetre programm´e. La fonction d’une carte RDisk est ´equivalent `a un
noeud de la plateforme pr´ec´edente. Les banques de donn´ees g´enomiques sont r´eparties sur
les 48 cartes RDisk. L’id´ee est que l’´etape heuristique de l’algorithme de comparaison des
voisinages peut ˆetre remplac´ee par une ´etape de filtrage directement en sortie des disques
dur. Dans cette plateforme, l’hˆote d´ecoupe la s´equence requˆete en un ensembles de mots
requˆetes et les envoie `a chaque carte RDisk. Le filtre FPGA a pour fonction de comparer
les paires de voisinages. Les num´eros des s´equences sont alors envoy´es `a l’hˆote. L’hˆote doit
effectuer la fusion et renvoyer aux cartes la demande d’extraction des s´equences. Voici les
param`etres de cette plateforme :
Tacces = 7 msec



3.3 Plateformes ´
etudi´
ees

19
Tf = 15 Mo/sec
Texec = 0 Mo/sec

HD

Filter on FPGA

Node 1
Ethernet
Switch

Node 2

Host Computer (PC)

Node 48

Fig. 3.3 – Configuration de RDisk
Pour cette plateforme, les clusters lues sur le bus IDE sont transf´er´es sur le filtre FPGA.
L’ex´ecution d´emarre d`es qu’un noeud re¸coit l’adresse et la taille des clusters `a lire. Grˆace `a
ceci, nous ne prenons pas de temps pour l’´etape de comparaison des voisinages.

3.3.3


ReMiX

ReMiX est un cluster de m´emoires reconfigurables. Dans cette plateforme, on a un cluster
de quatre machines. Chaque machine est connect´ee `a deux cartes RMEM (Reconfigurable
Memory)1 . La carte RMEM comprend un filtre FPGA et une grande m´emoire FLASH. Dans
la plateforme RDisk, les banques ( index´e, FASTA ) sont r´eparties localement sur les disques
durs, mais pour ReMiX, elles sont r´eparties localement dans la m´emoire FLASH. De la mˆeme
mani`ere, un serveur d´ecoupe une s´equence requˆete en un ensemble de mots requˆetes. Les mots
requˆetes sont envoy´es `a des serveurs qui travaillent en parall`ele de mani`ere ind´ependante.
Les r´esultats partiels sont collect´es sur un serveur d´edi´e pour un traitement global. La taille
m´emoire d’une carte RMEM est 64 Goctet. Au total, il y a 512 Goctet sur les 8 cartes. Voici
les param`etres de cette plateforme :
Tacces = 40 micro seconds
Tf = 600 Mo/sec
Texec = 0 Mo/sec
Pour ReMiX, les clusters lues sur la m´emoire FLASH sont transf´er´es sur le filtre FPGA. Ils
sont trait´es par la mˆeme mani`ere sur la plateforme RDisk.