- Le blog participatif de bioinformatique francophone depuis 2012 -

Assembler un génome sur un Raspberry Pi

Assem­bler un génome est une tâche fas­ti­dieuse et sur­tout très coû­teuse. Pour un génome de 100 Mbp (Mil­lion de paires de bases), Vel­vet ou SOAP­de­no­vo uti­lisent 20 à 30 Go de mémoire, voire plus. Je vou­drais par­ta­ger avec vous une idée com­plè­te­ment far­fe­lue qui nous est venue et qui nous a fait gagner (Guillaume Rizk et moi-même) le prix du meilleur pos­ter lors de JOBIM 2013 : et si on fai­sait de l'assemblage de génome sur un Rasp­ber­ry Pi ?

Raspberry Pi (CC-BY-SA 3.0)
Rasp­ber­ry Pi (CC-BY-SA 3.0)

Remet­tons-nous d'abord dans le contexte…

L'assemblage de génome

Je ne vais pas décrire ici tout ce qui concerne l'assemblage de génome, cela méri­te­ra un article entier… même plu­sieurs. Je vais sim­ple­ment vous pré­sen­ter les idées géné­rales et sur­tout le cas qui nous concerne : l'assemblage de novo.

L'assemblage de génome consiste à recons­ti­tuer un génome à par­tir d'un ensemble de reads, des séquences d'ADN "lues". Ces reads peuvent pro­ve­nir de divers types de séquen­ceurs. Nous en avons pré­sen­té quelques uns dans l'article : Le séquen­çage, une his­toire de géné­ra­tion. En fonc­tion des tech­no­lo­gies, les reads peuvent être plus ou moins longs et pro­duits plus ou moins rapi­de­ment.

Commins, Toft & Fares (CC BY-SA 2.5)
Com­mins, Toft & Fares (CC BY-SA 2.5)

Dans notre cas, nous avons des reads petits (~100 bp) mais en grande quan­ti­té et nous n'avons pas de génome de réfé­rence. La pro­cé­dure lar­ge­ment uti­li­sée dans ce cas là se com­pose, en gros, de trois étapes :

  1. Le comp­tage des k‑mers
  2. L'assemblage des contigs
  3. La créa­tion de scaf­folds

Pour faire simple, les reads sont décou­pés en mor­ceaux che­vau­chants de k carac­tères : les k‑mers. Les k‑mers sont comp­tés afin de sup­pri­mer ceux qui ne sont pas suf­fi­sam­ment repré­sen­tés et qui sont consi­dé­rés comme des erreurs de séquen­çage.

À par­tir des k‑mers che­vau­chants, nous pou­vons ensuite recons­ti­tuer des séquences d'ADN conti­guës, les contigs. Cette étape est géné­ra­le­ment réa­li­sée en uti­li­sant un graphe de De Brui­jn. Enfin, puisqu'il reste des trous entre les contigs, dans une der­nière étape, ils seront ras­sem­blés en scaf­folds (écha­fau­dages) dans les­quels la taille des trous pour­ra être esti­mée.

Graphe de De Bruijn et Filtre de Bloom (CC BY-NC-ND 3.0)
Graphe de De Brui­jn de l'union d'un ensemble de k‑mers réels (noeuds verts) et de
k‑mers faux posi­tifs (noeuds rouges et noirs poin­tillés) (CC BY-NC-ND 3.0)

Les deux pre­mières tâches sont celles qui nous inté­ressent par­ti­cu­liè­re­ment car elles sont les plus dif­fi­ciles. En effet, elles demandent de sto­cker tous les k‑mers  en mémoire. Or, si nous vou­lons comp­ter des 30-mers, il nous faut une table qui contienne au pire 430 entiers… même si cha­cun d'eux était enco­dé par un seul octet, ça fait tout de même 109 Go… ça monte vite non ? On n'arrive jamais à cette extré­mi­té mais cela reste très gour­mand.

 MINIA, un assembleur minimaliste

Afin de réduire la quan­ti­té de mémoire vive uti­li­sée pour l'assemblage, Rayan Chi­khi, Guillaume Rizk et Domi­nique Lave­nier, ont eu l'idée d'utiliser une struc­ture de don­nées infor­ma­tique par­ti­cu­liè­re­ment com­pacte, le filtre de Bloom, que Nico vous a déjà pré­sen­té ici. Je ne reviens donc pas sur la défi­ni­tion.

Filtre de Bloom (CC BY-NC-ND 3.0)
Filtre de Bloom (CC BY-NC-ND 3.0)

Le graphe de De Brui­jn est enco­dé via un filtre de Bloom qui nous dit si un k‑mer y est pré­sent ou non. Mais pour ne pas nous trom­per, il faut que le filtre soit par­fait, or nous savons qu'il ne l'est pas. Ce pro­blème est réso­lu en gar­dant, dans une autre table, les k‑mers non-pré­sents mais qui sont voi­sins d'un k‑mer pré­sent dans le graphe (cercles rouges). Ain­si, nous sommes sûrs de ne jamais nous trom­per.

Cela résout le pro­blème de la taille du graphe de De Brui­jn mais pas celui du comp­tage des k‑mer. Pour ce pro­blème, la réflexion a été la sui­vante : "puisque nous n'avons pas assez de mémoire vive, pour­quoi ne pas uti­li­ser le disque dur ?" Ain­si, une pro­cé­dure par décou­page de l'espace des k‑mers a été uti­li­sée comme illus­trée dans l'image ci-des­sous. Chaque read est lu et décou­pé en k‑mers. Puis une fonc­tion de hachage est appli­quée à chaque k‑mer afin de savoir à quelle par­ti­tion il appar­tient. Chaque par­ti­tion est écrite sur le disque dur. Une fois que tout est lu, chaque par­ti­tion est char­gée en mémoire, triée, comp­tée puis réécrite sur le disque. Évi­dem­ment, la taille des par­ti­tions est cal­cu­lée de façon à opti­mi­ser l'utilisation de la mémoire vive.

DSK (CC BY-NC-ND 3.0)
DSK (CC BY-NC-ND 3.0)

Ces deux idées ont été implé­men­tées dans le logi­ciel MINIA et sont plus lar­ge­ment décrites dans les réfé­rences sui­vantes :

Mettons tout ça sur un Raspberry Pi

Là ! Y a défi ! Même si MINIA est peu gour­mand en res­sources, ça reste dif­fi­cile de faire tour­ner un assem­bleur avec seule­ment 512 Mo de RAM. Car notre Rasp­ber­ry Pi est vrai­ment un tout petit sys­tème infor­ma­tique : un pro­ces­seur ARM à 700MHz, 512 Mo de RAM, une carte SD de 4 Go pour le GNU/​Linux et une clé USB de 32 Go pour les don­nées. C'est pas énorme !

D'ailleurs, lors des pre­miers essais sur E. coli, cela ne fonc­tion­nait pas. Les buf­fers d'écriture sur fichiers étaient trop grand (2 Mo par fichier x 100 fichiers ouverts = 200 Mo). Après cor­rec­tion, nous avons réus­si à assem­bler le génome de E. coli puis celui de C. ele­gans. Ça devient inté­res­sant lorsqu'on com­pare à Vel­vet et SOAP­de­no­vo qui uti­lisent res­pec­ti­ve­ment 30.6 et 29.6 Go de RAM pour assem­bler C. ele­gans, là où MINIA en uti­lise moins de 300 Mo.

Par contre, c'est vrai que le Rasp­ber­ry Pi est lent, il lui a fal­lu 18h pour réa­li­ser l'assemblage. Ceci dit, sur un ordi­na­teur de bureau, Vel­vet a mis 13h… MINIA, sur une machine lar­ge­ment moins per­for­mante, s'en tire plu­tôt pas mal. Bref, tous ces résul­tats sont don­nés sur notre pos­ter dis­po­nible ici ou .

Picontigotron (CC-BY-NC-ND 3.0)
Picon­ti­go­tron (CC-BY-NC-ND 3.0)

Enfin, pour JOBIM, nous avions besoin de faire la démons­tra­tion en direct. Guillaume Rizk et moi-même avons donc sor­ti le fer à sou­der, deux trois LED, une mini impri­mante ther­mique, un écran LCD 2x16 carac­tères, des câbles, etc… Et nous avons créé le Picon­ti­go­tron : un assem­bleur de génome dans une boite à chaus­sures ! La classe totale. 🙂

L'intérieur du Picontigotron (CC-BY-NC-ND 3.0)
L'intérieur du Picon­ti­go­tron (CC-BY-NC-ND 3.0)

Conclusion

Le but de ce billet, au-delà du plai­sir de vous racon­ter ma petite his­toire, n'est pas de vous dire que MINIA est le meilleur assem­bleur de tous les temps, loin de là. D'ailleurs, il ne fait que les deux pre­mières étapes de l'assemblage, il ne sait pas construire les scaf­folds. Ce n'est pas non plus de vous inci­ter à ache­ter des Rasp­ber­ry Pi…

Non, ce que j'espère vous faire pas­ser, c'est que désor­mais, il va fal­loir être malin. Ali­gner les ordis dans des clus­ters n'est pas for­cé­ment LA solu­tion. Avec des struc­tures de don­nées bien pen­sées et adap­tées aux pro­blèmes, avec des algo­rithmes qui uti­lisent fine­ment les res­sources des ordi­na­teurs, nous pou­vons réa­li­ser des tâches extrê­me­ment com­plexes sur un ordi­na­teur de bureau. Nous avons bien réus­si sur un Rasp­ber­ry Pi.

La bio­in­for­ma­tique est en cela une source mer­veilleuse de pro­blèmes pour les infor­ma­ti­ciens. J'adore bos­ser dans ce domaine, j'espère que vous aus­si. 😉

Je remer­cie Nol­wenn, Max et Syl­vain pour leur relec­ture.



Pour continuer la lecture :


Commentaires

6 réponses à “Assembler un génome sur un Raspberry Pi”

  1. […] genome assem­bly with #Rasp­ber­ry­Pi (in French) http://t.co/BHxOJTPDNe ( via @bilouweb /​ @BioinfoFr)  […]

  2. […] Assem­bler un génome est une tâche fas­ti­dieuse et sur­tout très coû­teuse. Pour un génome de 100 Mbp (Mil­lion de paires de bases), Vel­vet ou SOAP­de­no­vo uti­lisent 20 à 30 Go de mémoire, voire plus.  […]

  3. […] très beaux pro­jets sont désor­mais pos­sibles. Le Picon­ti­go­tron de Guillaume Col­let, par exemple, est incroyable et à la croi­sée de la recherche, de la péda­go­gie, et du bri­co­dage. […]

  4. nous allons tous attendre le Picon­ti­go­tron 2 !

    à base de Rpi2 et qui devrait se rap­pro­cher des grands… avec tou­jours la même pro­blé­ma­tique de la mémoire embar­qué !

    car si la Rpi2 à 1Go, elle à aus­si 4cores, si le soft devaient être mul­ti­threa­dé cela ne lais­se­rai que 256Mo/​thread… ouchhh
    après limi­té l'execution sur 2cores est fai­sable… trop facile, diront cer­tains ! 😉

    1. Avatar de Jérôme lamarque
      Jérôme lamarque

      Et on en parle du Rasp­ber­ry Pi 4 Modèle B à 8Go de RAM et 4 cœurs ?

      Broad­com BCM2711, Quad-core Cor­tex-A72 64bit SoC@ 1,5GHz, ARM v8

  5. Article interessant:D

Laisser un commentaire