Calculs intensifs pour l étude de lévolution Le calcul de larbre du vivant

S

Calculs intensifs pour

l étude de l’évolution Le calcul de l’arbre du vivant

Le génome

Le génome est l’ensemble du materiel génétique d’un individu ou d’une espece

Le génome est codé sous la forme de une ou plusieurs molécules d’ADN (par exemple les chromosomes)

Il est présent chez tous les organismes vivants: plantes, animaux, insectes, champignons, microbes, bactéries

Toutes les cellules d’un individu contienent un exemplaire du génome (chaque cellule humaine contient 2 mètres d'ADN environ)

Les gènes

Il s’agit de zones dans le génome qui contiennent l’information sur la construction d’élements fondamentaux du fonctionnement des cellules, des organes, etc.

Par exemple les gènes codent pour les protéines, des polypeptides impliqués a tous les niveaux de la vie cellulaire

Diversité des génomes

Génome humain : 3,2 milliards de lettres environ 25 000 gènes

Génome de la mouche: 120 millions de lettres environ 20 000 gènes

Génome du maïs: 5 milliards de lettres 55 000 gènes

Génome de la bactérie Escherichia coli 4 millions de lettres 4 000 gènes

Séquençage du génome

Il s’agit de connaître la « séquence » du génome c’est à dire la formule : AATGCATAGTGCCGATG…..

Certaines parties du génome sont des gènes qui codent des protéines

AATGCATAGTGCCGATGTAGTGCATAGTGC

Explosion du nombre de génomes séquencés

Cout du séquençage en chute libre (nouvelles technos)

Accélération du nombre de génomes séquencés

Génome de l’homme: Séquencage du génome humain 1989-2001: 12 ans

En 2010 : projet « 1000 Génomes » (1000 génomes humains)

Explosion du nombre de génomes séquencés

2 000 génomes disponibles aujourd’hui

Quelque projets parmi d’autres:

Génome 10K: 10 000 génomes de vertébrés

i5K: 5 000 génomes d’insectes dans les 5 ans

1KP: 1 000 génomes de plantes

L’évolution « rien en biologie n’a de sens, si ce n’est à la

lumière de l’évolution »Theodosius Dobzhansky (1900-1975) :

La diversité des formes de vie est le résultat d’un processus historique, fait de hasards et de contraintes : l’évolution

Comprendre l’évolution pour expliquer les formes de vie

Comprendre les formes de vie pour retracer l’évolution

La phylogénie

Etude de l’histoire des relation de parentés entre les êtres vivants Anatomie comparée

Comparaison de séquenceAATTACGATCGATTTACGCAATTGCGATCGATTTACGCAATTCCTATCGATTTACGCAATTCCTATCGATTTACGC

On peut observer des similarités entre les séquencesintérêt: tous les organismes ont des séquences d’ADN(alors qu’ils n’ont pas tous des pattes!)

On observe une similarité qui permet de supposer qui il existait un ancêtre commun a ces organes

La phylogénie

Gènes homologues: ce sont des gènes qui descendent du même gène ancestral

Deux séquences présentant une forte similarité de séquence ont de grande chance d’être des séquences homologues

Nombreuse méthodes mathématique permettant de calculer la similarité entre 2 séquences Séquences ADN : 4 lettres Séquences de protéines : 20 lettres

La phylogénie

Phylogénie d’un gène On estime la distance évolutive entre différents

gènes On la représente sous la forme d’un arbre

Phylogénie d’un gène présent dans le génome de différents organismes

Ces gènes sont des gènes « homologues »

Le gène de la souris est plus proche du gène du rat que de celui de la vache : la distance entre gène est proportionelle la longeur de branche

La phylogénie

Phylogénie des êtres vivants

La phylogénie

Phylogénie des êtres vivants On utilise la phylogénie d’un gène pour proposer une phylogénie des êtres vivants

La génomique comparative

Autrefois on se basait sur quelques gènes pour reconstruire l’ histoire évolutive des organismes

Mais tous les gènes n’ont pas la même histoire

Aujourd’hui on peut utiliser l’ensemble du génome pour comparer les organismes

La phylogénomique

Calcul de la phylogénie des especes en se basant sur l’ensemble de leur génome

Projet AncestromeEtude du fonctionnement et de l’organisation des génomes des êtres vivants actuels dans le but de construire des modèles permettant de

connaître le génomes de leurs ancêtres ainsi que les processus évolutifs qui les ont engendrés

Entre autres aspects: Base de données HOGENOM

Calculs de similarité de séquences Clustering

Programme PHYLDOG : Calcul simultané de l’arbre phylogénetique du vivant

et des arbres phylogenétique de chaque gène

HOGENOMBase de données de familles de gènes homologues pour tous

les génomes

On recherche les familles de gènes homologues chez tous les organismes vivants

Pour chaque famille on calcule un arbre phylogénétique: un « arbre de gène »


les génomes

clustering phylogénie

etc.

génomes protéines

génomes (tout l’ADN) gènes (ADN codant) protéines (traduction du gène)


les génomes

Environ 1 500 génomes (dont 140 eukaryotes : mamiferes, oiseaux, plantes etc.)

Soit 160 milliards de lettres au total

Environ 7 millions de gènes codants soit 3 milliards de lettres

Résultat: ces 7 milions de gènes sont classés en 300 000 familles


les génomes

génomes

Construction des familles de gènes homologues


les génomes

génomes protéines



les génomes

génomes protéines



les génomes

génomes protéines



les génomes

génomes

Recherche de similarités locales

entre les séquences (« BLAST »)

protéines



les génomes

génomes



protéines

Clustering transitif avec condition

(« SILIX»)



les génomes

génomes



protéines


(« SILIX»)


A

A

A

B

C

D


les génomes

génomes



protéines


(« SILIX»)


A

A

A

B

C

D

BA

CD

Famille


les génomes

génomes

Marche à suivre


les génomes

clustering phylogénie

etc.

génomes protéines

Marche à suivre

Calcul distribuéParallélisation par les données

banque BLAST

Plusieurs millions deséquences « requêtes »

1 fichier

texte

Plusieurs millions deséquences « cibles » Plusieurs milliards de

zones similaires entre les séquences


banque BLAST

Plusieurs millions deséquences « requêtes »

1 fichier

texte

Plusieurs millions deséquences « cibles »

banque BLAST

Quelques dizainesséquences « requêtes »Centaines de milliers de

fichiers

texte

Plusieurs milliards de zones similaires entre

les séquences


Chaque calcul est indépendant

On peut donc utiliser indifféremment et indépendamment un cluster de machines une grille de calcul le calcul dans le nuage une combinaison des précédents

Calculs BLAST incrémentiel sur toutes les séquences

connues

A chaque nouvelle version de la base, on classe les séquences comme « ancienne » ou « nouvelle »

On calcule la similiarité: des nouvelles séquences entre-elles ( BLAST new x new) des nouvelles séquences avec les anciennes ( BLAST new x old)

Finalement on ajoute BLAST new x new et BLAST new x old aux similarités de la release précédente (i. e. BLAST old x old)

Calculs BLAST incrémentiel sur toutes les séquences

connues

Release Nombre de séquences

BLASTS

1 (2009) 7 000 000 7 000 000 x 7 000 000

2 (2011) 13 000 000 6 000 000 x 6 000 0006 000 000 x 7 000 000

3 (2013) 19 000 000 6 000 000 x 6 000 0006 000 000 x 13 000 000


les génomes

Comparaison de tous les gènes entre eux pour déterminer leur similarité

Utilisation d’un logiciel (« BLAST ») qui recherche des zones de similarités locales entre les séquences ( approche heuristique)


les génomes

Exemple: un arbre phylogénetique de gène de HOGENOM

Eukaryotes

Calculs effectués

1ère Release (2009-2010) env. 8 000 000 séquences

BLAST 8,000,000 x 8,000,000 séquences [grille TIDRA]2ème Release (2011) env. 13 000 000 séquences

BLAST 5,000,000 nouvelles x 5,000,000 nouvelles [cluster] BLAST 5,000,000 nouvelles x 8,000,000 anciennes [grilles TIDRA/GRISBI]3ème Release (2013) env. 19 000 000 séquencesBLAST 6,000,000 nouvelles x 6,000,000 nouvelles [cluster] BLAST 6,000,000 nouvelles x 13,000,000 anciennes [cluster]

Technologie grille et services associés

sur TIDRA (Grille Rhône-Alpes)

7000 cœurs (cpu)

300 To de stockage

5 Sites LAPP (Annecy) LPSC (Grenoble) IPNL (Lyon) IBCP (Lyon) CC-IN2P3 ( Lyon)


TIDRA RAGRID (Grille Rhône-Alpes)

Middleware : Job management : gLite, LRMS Stockage : iRODS, SRM Utilisateur : JSAGA implementation SAGA

vo.rhone-alpes.idgrilles.fr

Mise en place sur TIDRA 1ère release (2009-2010)

1ère mouture de BGENR : séquences Uniprot (9 millions)

8 millions de séquences non redondantes à comparer.

Historique :Mise en place de l’outil avec 3 membres du CC - Y.Cardenas, P. Calvat, J.Y. Nief

1er contact avec la grille Novembre 2008Premiers tests de charge et développements blast intensifs

Février 2009 Arrivée de iRODS Gros soulagement!!!Juin 2009Début de la production + développementJuillet 2009Fin de la production Janvier 2010

Mémoire minimum des machines : 2 Go

La solidité d'une chaîne dépend du maillon le plus faible : on veut éviter un dépassement de mémoire sur les machines les moins puissantes

taille maximum de la banque BLAST : 2 x 106 séquences8 x 106 = 4 banques de 2 x 106 séquences à

traiter itérativement *

nombre maximum de séquences à traiter avec une banque 2 x 106 : 30

La “tâche unitaire” compatible avec une mémoire de 2 Go est donc :

4 x BLAST de 30 séquences vs 2 x 106 séquences

*La taille théorique de la banque BLAST est fixée (option -z)

Contraintes dues à la mémoire

Le calcul d’1 tâche unitaire est très court : env. 15 minutes

Bien inférieur au temps disponible dans un job : variable selon les machines

quelques heures - quelques jours

Chaque job doit exécuter le plus grand nombre possible de tâches unitaires

Optimisation du temps passé en calcul

Résumé

Données ( format FASTA) 1ère mouture de BGENR : séquences Uniprot (9 millions) : 8

millions non redondantes. Banque BLAST

8 millions de séquences Divisée en 4 bases de 2 millions de séquences pour éviter

de dépasser la mémoire maximum disponible sur les machines

Séquences à blaster 8 millions de séquences, soit: 250, 000 fichiers de 30 séquences au format FASTA

30 séquences : nombre maximum de séquences pour éviter un dépassement de mémoire sur les machines les moins puissantes

Chaque job doit exécuter le plus grand nombre possible de tâches quelque soit son temps de calcul maximum

1 - Liste de tâches à effectuer (250,000 fichiers de 30 séquences) 2 - Chaque job N tente de traiter les 100 tâches à partir de la tâche numéro N x 100 3 - Une fois tous les jobs terminés, génération d’une nouvelle liste de tâches à traiter4 - Retour au point 1

On a choisi un “pas” de 100 fichiers par job : c’est au dessus du nombre de tâches qu’il est possible de traiter avec les durées les plus longues.

Mais on peut l’adapter à la production : vers la fin, on prend un “pas” plus court

On utilise des jobs paramètriques, le paramètre est N

Stratégie adoptéePlusieurs tâches par job

Stratégie1

100

200

300

400

1

100

200

300

400

1

100

200

300

400

première production

1

100

200

300

400

deuxième production

exemple BGENR1 : 8 x 106 séquences 1 - Nombre de banques BLAST

4 2 - Nombre de séquences par fichiers

30 3 - Nombre max de fichiers par job 100 4 - Nombre de jobs par job paramétrique

40 5 - Délai entre la soumission des jobs paramétriques 20 mn

Paramètres à ajuster:

Launcher : source launcher 1 1000 40 20 generic_par_irods_lst_new.jdl

premier jobdernier jobnombre de jobs par job paramétriquedélai de soumission entre les jobs

Le launcher propose une liste de noeuds. Les jobs paramétriques seront

répartis sur les noeuds choisis.

Ici on a lancé 1000 jobs (de 1 à 1000) par paquets de 40 :25 jobs paramétriques, temps total soumission = 8h

Lancement des jobsscript jdl

Monitoring

Un job de monitoring est lancé qui envoie régulièrement des mails décrivant l’avancement des tâches

RésultatsRappel : 250,000 fichiers à traiter 250,000 fichiers

résultats

2,000,000,000 hits blast

concaténation en 200 fichiers de 5 Go (1 To)

moyenne de 50 fichiers par job

environ 5000 jobs (plusieurs séries) moyenne : 125 jobs x 40 paramétriques x 50 fichiers = 250

000 moyenne : jobs de 15 heures

Calcul en 1 semaine au lieu de 8 ans

Description du JDLN est le paramètre du job

paramétrique Déroulement d’un job numéro N :

récupération de différents outils via lcg-cp : outils iRODS outils pour l’estimation du temps de calcul outils pour la gestion des proxies

Renouvellement du proxy Lancement de l’application :

Copie des programmes BLAST en local via iRODS Copie des banques BLAST en local via iRODS Copie de la liste de fichiers à traiter Copie des 100 fichiers à traiter : fichiers numéros (N -

1)x 100 +1 à N x 100 Boucle: pour i variant de (N -1)x 100 +1 à N x 100

traite le fichier i, copie le résultat via iRODS tant que 95% du temps maximum n’est pas atteint,

passe au fichier suivant Post-traitement: envoi de mail, copie des logs via iRODS

Mise en place sur TIDRA 2ème release

(2011)

2ère mouture de BGENR : séquences Uniprot + Ensembl + Autres

(33 millions de séquences, 12 millions non redondantes)

5 millions de séquences non redondantes,soit 170,000 fichiers de 30 séquences

à comparer avec 7 millons de séquence.

Nouveaux développements :Outil DTM - Outil JJS - Acces iRODs


Prototype du DTM (« Distributed Task Manager ») Yonny Cardenas

gLite + iRODS système de base de données pour la gestion des

jobs (runing, ended, canceled,etc.).

destination des jobs : à la fois en local, BQS et Grille

gestion automatisée de la production (gestion des erreurs, etc.)

l’utilisateur fournit seulement une liste de tâches, DTM s’occupe des jobs et de la production

Pour l’instant fonction uniquement pour BQS, adaptation a la grille en cours


JJS Java Job Submission (Pascal Calvat) commande « jjs-* » pour simplifier l’utilisation de

la grille :• soumission • monitoring• gestion des proxy

gestion automatique de la répartition des jobs sur les noeuds de la grille, analyse de l’efficacité des différents noeuds

fonctionne via des jdl crées a partir d’un template avec une commande jjs

Notion de « production » c-à-d d’un ensemble de job


Migration totale de nos données sur iRODS: accès direct aux données :

icd,ils,ipwd,iput,iget,etc. programme de recherche des hits blast via iRODS

(utilisation d’une API C pour iRODS)

utilisation des meta-données et des micro-services ( à développer)


Approche similaire Release 1, mais irods intégré à la grille ( plus besoin de

récupérer les utilitaire irods ) gestion des proxies intégrée ( plus besoin de

déclarer les proxies dans le script)Utilisation des commandes jjs ( plus de jobs paramétriques)

Plus simple : 1 jdl + 1 script

Description du JDL avec JJSN est le paramètre du job paramétrique

Déroulement d’un job numéro N : récupération de différents outils via lcg-cp X:

outils iRODS X outils pour l’estimation du temps de calcul X outils pour la gestion des proxies X

Renouvellement du proxy X Lancement de l’application :

Copie des programmes BLAST en local via iRODS Copie des banques BLAST en local via iRODS Copie de la liste de fichiers à traiter Copie des 100 fichiers à traiter : fichiers numéros (N -

1)x 100 +1 à N x 100 Boucle: pour i variant de (N -1)x 100 +1 à N x 100

traite le fichier i, copie le résultat via iRODS tant que 95% du temps maximum n’est pas atteint,

passe au fichier suivantX Post-traitement: envoi de mail, copie des logs via iRODS

Mise en place sur TIDRA 2ème releaseRésultats

Production par « bloc » de 1000 jobs paramétriques, avec 20 fichiers par job

soit 20 0000 fichiers traités. 9 « blocs » de 1000 job à lancer pour traiter les 170 000 fichiers

Qualité: un proxy de 5 jours permet de perdre moins de jobs

Production jobs jobs récuperés jobs OK nb fichiers traités

Production 7 1000 734 411 10,535 Production 8 1000 881 676 17,174 Production 9 1000 982 786 19,835

Problèmes rencontrés

Beaucoup de choses à installer sur les machines

Hétérogénéité des machines

Information fournie par les machines au WMS pas toujours suffisante

En général


Si trop de jobs soumis à la fois saturation du WMS saturation des commandes «iget» de iRODS

Solution limiter le nombre de jobs qui attaquent en même

temps jouer sur le nombre de job paramétriques par job délai aléatoire au début de chaque job entre les jobs

Saturation


Estimation du temps de calcul d’un job pour un arrêt «propre» : système hétérogène, dépend des nœuds

Solution Release 1 : test de la présence d’un outil pour

estimer le temps de calcul Release 1 : récupération d’un outil si besoin Release 2 : pas encore de solution, à améliorer

Temps de calcul d’un job


RELEASE 1 :

2 types de problèmes

La soumission dure trop longtemps, on perd le proxy

utiliser un serveur de proxies

Le job dure trop longtemps, on perd le proxy car la grille ne gère pas le renouvellement automatique du proxy

le job doit renouveler lui-même le proxy au départ. utiliser un serveur de proxies

RELEASE 2 : plus de problèmes. Proxies de 5 jours, outil myProxy

Renouvellement des proxies

Conclusion TIDRA BGENR Release 1 et 2

travail pionnier dans l’utilisation en production de iRODS avec gLite 2 technologies/middleware integrées de manière

transparente gLite (EGEE) pour le calcul iRODS pour le stockage

Après ajustement iRODS semble bien supporter la charge ( à hauteur de 500 jobs en parallèle)

Intérêt d’une grille régionale

Pas trop de nœuds (pas l’embaras du choix, connaissance des capacités des nœuds)

En cas de problème sur un nœud, forte réactivité, facile de contacter un responsable

Perspectives TIDRA Fusion DTM et JJS

Mise en place sur GRISBIOutils disponibles

Tous les outils nécessaires à la bioinformatique sont disponible (tags)

Les bases de données biologiques sont disponible (tags)

Logiciel de statistique R installé (tags) Systême de fichiers XtreemFS :

répertoire partagé en réseau par tous les jobs de grille

lié au proxy, totalement transparent• grmount : montage temporaire du répertoire • grmount -u : démontage

Parallélisation par les « queries »

Meme approche que TIDRA

8 1068 106

banque BLASTdonnées fasta

QUERY SUBJECT

8 106

banque BLAST

QUERY SUBJECT


sur GRISBI

856 cœurs (cpu)

25 To de stockage

7 Sites IBCP (Lyon) LBBE (Lyon) ABiMS (Roscoff) GenOuest (Rennes) CBiB ( Bordeaux) GenoTool (Toulouse)

Outils bioinformatiques

Bases de données biologiques

XtreemFS

Stratégie « 1 job = 1 tâche »

(sans XtreemFS) On utilise les outils disponibles sur la grille

(blast)

On dépose sur la grille la base de données blast à traiter (LFC)

Fichier d’entrée en local, définis par le jdl (SandBox)

Fichier de sortie en local, définis par le jdl (SandBox)

Description du JDL GRISBI « 1 job = 1 tâche »

InputSandBox: le fichier à traiterOutputSandBox: le résultatN est le paramètre du job paramétrique, Déroulement d’un job numéro N :

Copie des banques BLAST en local (lcg-cp ) Traitement du fichier numéro N

170,000 fichiers à traiter : 170,000 jobs paramètriques • ici 1 job = 1 fichier• Essais sur une production de 1000 jobs parametriques• 200 a 400 jobs en run simultanés

Stratégie « 1 job = 1 tâche »

(sans XtreemFS)Ca marche, mais:

Très grand nombre de jobs

On utilise la SandBox pour les sorties : Taille des sorties importantes, risque de limitation!

Pas très efficace ( temps de calcul court, on récupère la base blast pour chaque tâche, etc.)

On souhaiterais utiliser une approche similaire à celle utilisée dans TIDRA

avec une liste de tâches comme argument du jdl:

Pas possible avec la SandBox

Stratégie « 1 job = n tâches »

(avec XtreemFS) On utilise les outils disponibles sur la grille (blast)

On dépose sur la grille la base de données blast à traiter (LFC)

On dépose sur la grille tous les fichier d’entrées (XtreemFS)

Chaque jobs traite plusieurs fichiers d’une liste (fournie par la SandBox)

On stocke sur la grille les fichiers de sortie via XtreemFS

170,000 fichiers à traiter ici 1 job = 30 tâches ( = 30 fichiers soit 90 séquences) Production : 6 soumissions par paquets de 1000 jobs

parametriques on atteint 850 jobs en run simultanés

Description du JDL GRISBI/XtreemFSInputSandBox: liste des fichiers à

traiterN est le paramètre du job paramétrique, m est le nb de fichiers à traiter par jobm fichiers à traiter : fichiers numéros (N -1)x m +1 à N x m Déroulement d’un job numéro N :

Copie des banques BLAST en local (lcg-cp )

Boucle: pour i variant de (N -1)x m +1 à N x m

Montage du répertoire grille Vérifie si le fichier i a été calculé:

si oui, saute à i +1 Copie du fichier i Démontage du répertoire grille Traite le fichier i avec blast, Montage du répertoire grille Copie du résultat Démontage du repertoire grille

Fin de boucle

170,000 fichiers à traiter • ici 1 job = 30 tâches

( 30 fichiers soit 90 séquences)

• Production : 6 soumissions par paquets de 1000 jobs parametriques

• on atteint 850 jobs en run simultanés

Entrées et sorties sur XtreemFS

Problèmes rencontrés GRISBI

Tags inexacts

Information fournie par les machines au WMS pas toujours suffisante

Saturation des accès XtreemFS

Problèmes résolus sans difficultés

Conclusion GRISBI

Travail pionnier dans l’utilisation en production de XtreemFS avec gLite

2 technologies/middleware integrées gLite (EGEE) pour le calcul XtreemFS pour le stockage

Après ajustement XtreemFS semble bien supporter la charge ( à hauteur de 500 jobs en parallèle)

Temps de calcul GRISBI et TIDRA

TIDRA 1ère production 22 248 jobs 115 751 heures ( 13 ans) sur 1 processeur Intel Xeon.

TIDRA 2 ème production 15 797 jobs (répartis sur une dizaine de soumissions) 63 433 heures ( 7 ans) sur 1 processeur Intel Xeon. pics de 650 jobs en parallèle

GRISBI avec et sans XtreemFS 47 713 job 8 810 heures ( 1 an) sur 1 processeur Intel Xeon pics de 830 jobs en parallèle

CONCLUSIONS TIDRA vs GRISBI Différences

TIDRA GRISBIGénéraliste BioinformatiqueRégionale NationalePas de softs/BDD installés Logiciels et BDD bioinfo et biostats disponiblesGestion des données avec iRODS Gestion des données XtreemFSCommandes jjs* Commandes gri*DTM+JJS (en devéloppement)Gestion des tâchesAdapté à des grandes productions Adapté a des calculs de bioinfo/biostats classiques

Points communs Pas trop de nœuds (pas l’embaras du choix, connaissance des capacités des

nœuds) En cas de problème sur un nœud, forte réactivité, facile de contacter un

responsable Commandes « grilles » simplifiées

Documents

Calculs intensifs pour l étude de lévolution Le calcul de larbre du vivant