- Indexation parall` ele des donn´ ees g´ enomiques. - Les banques de donn´ees g´enomiques sont de plus en plus volumineuses depuis quelques an- n´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 fonc- tionnelles. - 1.2.1 Banques de donn´ees de s´equences d’ADN. - 2 Indexation pour la recherche de similarit´ es 6 2.1 Principe de l’indexation. - 2.2.1 Les structures de donn´ees. - 2.3.1 Format de la table d’index. - 4.1.1 R´epartir les donn´ees g´enomiques. - 4.1.2 Dupliquer une partie des donn´ees localement. - 4.3 Duplication d’une partie des donn´ees en local niveau 2 (r´epartition cons´ecutives et non-cons´ecutives. - 4.7 Temps de construction de la banque sur chaque plateforme correspondant niveau de duplication des s´equences (M = 10.000. - 5.3 Temps d’ex´ecution de l’´etape de filtrage par rapport ` a un nombre de noeuds diff´erents (pas de duplication des donn´ees. - 5.4 Temps d’ex´ecution de l’´etape de filtrage par rapport au niveaux de concurrence des clusters (K=32. - 5.5 Temps d’extraction de la banque par rapport ` a un nombre de noeuds diff´erents. - Ils effectuent quotidiennement des recherches de similarit´es pour d´eterminer une histoire ´evolutive des organismes, ou pour d´eterminer des donn´ees fonctionnelles. - 1.2.1 Banques de donn´ ees de s´ equences d’ADN. - Les banques de donn´ees sont mises `a jour `a partir d’une collabo- ration internationale. - Les banques de donn´ees peuvent ˆetre organis´ees en plusieurs structures : texte, XML, don- n´ees relationnelles etc. - les s´equences d’ADN ou d’acides amin´es sont des donn´ees non structur´ees. - 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.. - BLAST est devenu la r´ef´erence en exploration de base de donn´ees g´enomiques. - Il y a deux probl`emes : la capacit´e calculatoire et le temps d’acc`es aux donn´ees. - L’index nous permet de pointer directement sur des donn´ees pertinentes.. - – d’´etudier le taux de duplication d’une partie des donn´ees. - Puis, dans la section 3 nous pr´esenterons un mod`ele de la recherche de similarit´es par indexation parall`ele. - L’indexation est une technique qui acc´el`ere la recherche de donn´ees. - 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. - 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. - 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. - – construction de l’index : cr´eer une structure de donn´ees `a partir du texte sur lequel on veut faire des recherches. - 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. - Chaque mot de longueur W de la requˆete est recherch´e dans la table d’index.. - 2.2.1 Les structures de donn´ ees. - c’est une structure de donn´ees refl´etant les caract´eristiques internes des s´equences. - 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]. - 2.3 M´ ethodes d’indexation pour la recherche de similarit´ es 10 donn´ees de 10 millions de paires de bases [9].. - 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). - C’est `a dire, ceux dont les voisinage gauche et le voisinage droit sont les plus similaires aux voisinages de la re- quˆete sans avoir besoin de consulter la banque de donn´ees. - La taille de la table d’index est ´egale `a 4 W. - La construction de l’index (banque index´ee) est obtenue `a partir de la banque au format FASTA, appel´e F. - de l’index on ajoute. - Tableau 2 : Contenu de la table d’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. - 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.. - Nous avons deux banques de donn´ees : la banque de s´equences au format FASTA et la banque index´ee. - O` u : T acces : temps d’acc`es aux donn´ees . - T f : vitesse de transfert des donn´ees (Mo/s. - 3.3 Plateformes ´ etudi´ ees 18 donn´ees sont r´eparties localement sur chacun des noeuds. - Les banques de donn´ees g´enomiques sont r´eparties sur les 48 cartes RDisk. - Pour r´esoudre ce probl`eme, nous proposons de dupliquer une partie des donn´ees en local sur chaque noeud. - 1 La taille de la banque Fasta est 9 Giga octets. - `a seulement quelques processeurs pour respecter la r´epartition des donn´ees. - Plus pr´ecis´e- ment, les donn´ees g´enomiques (les clusters de la banque index´ee et les s´equences FASTA) sont r´eparties une fois pour toute. - C’est la raison pour laquelle les tˆaches sont affect´ee aux processeurs en respectant la r´epartition des donn´ees.. - 4.1.1 R´ epartir les donn´ ees g´ enomiques. - Les donn´ees g´enomique sont r´eparties suivant leur structure. - 4.1.2 Dupliquer une partie des donn´ ees localement. - Le temps d’ex´ecution d’une tˆache d´epend de la taille du cluster. - On peux obtenir cet objectif si l’on duplique une partie des donn´ees en local. - En effet, la duplication d’une partie des donn´ees nous donne un plusieurs choix pour affecter une tˆache `a un processeur. - 4.3 – Duplication d’une partie des donn´ees en local niveau 2 (r´epartition cons´ecutives et non-cons´ecutives). - K-1} les processeurs, et R le niveau de duplication des donn´ees. - Pour chaque t^ ache Tj de la requ^ ete{j=1, 2. - K chercher un cluster correspondant ` a la t^ ache Tj dans 1 la ` ere partie des donn´ ees de noeud i. - Si l’on ne duplique pas une partie des donn´ees en local, chaque tache n’est affect´ee qu’`a un processeurs. - Et si l’on duplique une partie des donn´ees en local R fois on peut affecte une tˆaches `a un des R processeurs. - L’avantage de dupliquer une partie des donn´ees est d’´equilibrer la charge des processeurs.. - De nos jours, le temps d’acc`es aux donn´ees est encore coˆ uteux {pro- tocole IDE : 7 msec . - C’est pourquoi l’´etape de construction de la banque au format FASTA s’effectue en parall`ele. - En r´eduisant le temps de construction de la banque, nous faisons aussi la duplication d’une partie des s´equences en local. - Voici la formule qui calcule le temps de l’´etape construction de la banque (o` u m k : nombre de s´equences extraites `a un noeud k). - La figure 4.7 montre que le temps de construction de la banque au format FASTA ne baisse pas beaucoup si l’on augmente le niveau de duplication.. - 4.7 – Temps de construction de la banque sur chaque plateforme correspondant niveau de duplication des s´equences (M = 10.000). - La figure 4.8 montre que le temps gagn´e grˆace `a la duplication des donn´ees `a niveau 2 est le plus important. - La baisse du temps d’extraction de la banque au format FASTA n’est pas importante si l’on duplique des donn´ees. - C’est la raison pour laquelle nous d´ecidons de dupliquer les donn´ees seulement pour l’´etape de filtrage. - Chaque processus a ses propres donn´ees. - – l’acc´el´eration de l’´etape de filtrage (N tˆaches). - La figure 5.3 montre les performances de l’´etape de filtrage. - Par ailleurs, l’acc´el´eration de cette ´etape d´epend aussi du temps d’acc`es aux donn´ees. - Le temps moyen d’acc`es aux donn´ees est de 4.7 msec.. - En effet, si nous augmentons le nombre de noeuds, la tailles de donn´ees sera plus faible.. - Cette figure montre aussi que le temps de traitement de cette ´etape d´epend de la longueur des s´equences requˆetes.. - temps de l’etape de filtrage (seconds). - 5.3 – Temps d’ex´ecution de l’´etape de filtrage par rapport ` a un nombre de noeuds diff´erents (pas de duplication des donn´ees). - Pour r´eduire le temps de traitement de l’´etape de filtrage nous faisons la duplication d’une. - 5.4 – Temps d’ex´ecution de l’´etape de filtrage par rapport au niveaux de concurrence des clusters (K=32). - Les performances de l’´etape d’extraction de la banque au format FASTA est linaire (voir figure 5.5). - C’est la raison pour laquelle le temps d’extraction d’une s´equence ne d´epend que du temps d’acc`es aux donn´ees. - Le temps de construction de la banque ne d´epend pas la longueur des s´equences.. - temps d’extraction de la banque (seconds). - 5.5 – Temps d’extraction de la banque par rapport ` a un nombre de noeuds diff´erents. - Par ailleurs, la taille des donn´ees concernant l’ordonnancement des tˆaches et des s´equences n’est pas tr`es grande. - Par contre, la taille des donn´ees pour construire la banque FASTA est tr`es importante. - Apr`es avoir ´etudi´e le comportement de la recherche de similarit´es par l’indexation parall`ele, on d´eduit que. - Nous avons ´etudi´e le taux de duplication d’une partie des donn´ees en local. - Nous pouvons r´eduire le temps de cette ´etape en effectuant en parall`ele pour tous les noeuds sur une base de donn´ees obtenue par l’extraction des s´equences