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 ?

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.

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.

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 4³⁰ entiers… même si cha­cun d'eux était enco­dé par un seul octet, ça fait tout de même 10⁹ 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.

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.

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 :

• R. Chi­khi, G. Rizk. Space-effi­cient and exact de Brui­jn graph repre­sen­ta­tion based on a Bloom fil­ter, WABI 2012
• G. Rizk, D. Lave­nier, R. Chi­khi. DSK : k-mer coun­ting with very low memo­ry usage, Bio­in­for­ma­tics, 2013.

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 là.

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. 🙂

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.