Une question d'équilibre

De nom­breux articles de bio­in­for­ma­tique com­mencent par une phrase du genre : "Les mul­tiples pro­jets de séquen­çage et les pro­grès tech­no­lo­giques réa­li­sés ces der­nières années per­mettent aujourd'hui de pro­duire une énorme masse de don­nées bio­lo­giques." Cette phrase sert en géné­ral à intro­duire l'utilisation d'algorithme plus rapide, le trai­te­ment en paral­lèle des don­nées, ou leur uti­li­sa­tion mas­sive afin d'extraire de la connais­sance.

Mais au-delà de ces trois thèmes, le trai­te­ment ou l'utilisation de grande quan­ti­té de don­nées impose de réflé­chir un petit peu plus pré­ci­sé­ment à l'équilibre entre temps de cal­cul et temps de lecture/​écriture, voire même à remettre en cause la com­plexi­té théo­rique d'un algo­rithme. C'est ce qui m'est arri­vé récem­ment et j'aimerai par­ta­ger avec vous cette expé­rience et mes réflexions à ce sujet.

Le problème à résoudre

Mon pro­blème était assez simple, je devais lire envi­ron 80000 fichiers PDB (Pro­tein Data Bank), c'est-à-dire 80 000 struc­tures de pro­téines, afin de détec­ter si elles pos­sé­daient ou non un motif 3D d'acides ami­nés que j'avais don­né en entrée. Vous me direz… 80 000 fichiers, ce n'est pas for­cé­ment énorme, sur­tout que le plus gros fichier fait 70 Mo. Mais cela suf­fit pour cet exemple.

L'algorithme le plus rapide en théorie n'est pas forcément le meilleur

Pour recher­cher un motif d'acides ami­nés dans une struc­ture, j'ai d'abord uti­li­sé un algo­rithme très naïf :

• on prend un acide ami­né du motif et un acide ami­né de la struc­ture ;
• on regarde si ils sont com­pa­tibles ;
• si c'est le cas, on prend deux autres acides ami­nés (un dans la struc­ture, un dans le motif);
• on véri­fie la com­pa­ti­bi­li­té entre eux et avec les pré­cé­dents au niveau 3D (dis­tances inter-ato­miques simi­laires);
• on conti­nue ain­si jusqu'à trou­ver un ensemble d'acides ami­nés de la struc­ture, qui soit com­plè­te­ment com­pa­tible avec les acides ami­nés du motif.

Expri­mé en com­bi­na­toire, cet algo­rithme consiste à tes­ter tous les arran­ge­ments, sans répé­ti­tion, de m objets par­mi n, avec n le nombre d'acides ami­nés dans la struc­ture et m le nombre d'acides ami­nés dans le motif. Autre­ment dit, on choi­sit m acides ami­nés par­mi les n de la struc­ture et on regarde si ils sont com­pa­tibles avec les acides ami­nés du motif. Cela signi­fie qu'il faut, dans le pire des cas, tes­ter les n!/(n — m)! solu­tions et pour cha­cune véri­fier que toutes les dis­tances inter-ato­miques sont com­pa­tibles, c'est-à-dire m*(m‑1)/2 com­pa­rai­sons. Ce qui est énorme !

Ce pro­blème peut faci­le­ment se modé­li­ser sous la forme d'un graphe (je vous passe la modé­li­sa­tion), ce qui per­met de le rame­ner à une recherche de toutes les cliques d'une taille don­née dans le graphe (je vous laisse suivre le lien pour les expli­ca­tions sur les cliques). Or, nous savons que la recherche de cliques est un pro­blème NP-com­plet dif­fi­cile à résoudre. Néan­moins, c'est un pro­blème bien étu­dié, avec des algo­rithmes bien connus comme celui de Bron-Ker­bosch que j'ai choi­si d'utiliser (le choix de cet algo­rithme est sujet à dis­cus­sion).

J'avais alors deux algo­rithmes et des jeux de don­nées que j'ai tes­tés sur des petits exemples où je savais que la struc­ture conte­nait le motif recher­ché. Mon algo­rithme de Bron-Ker­bosch était plus rapide, ce qui confir­mait la théo­rie. Je tes­tai ensuite les deux algos sur mes 80 000 fichiers et là : sur­prise ! C'est l'algorithme naïf qui allait le plus vite !… Que s'était-il pas­sé ?

Plu­sieurs effets entrent en compte :

• dans l'algorithme naïf, si un couple d'acides ami­nés n'est pas com­pa­tible, il est éli­mi­né. Ain­si, si aucun acide ami­né n'est com­pa­tible au départ, la recherche s'est effec­tuée en O(n) : on a com­pa­ré tous les acides ami­nés de la struc­ture avec le pre­mier du motif ;
• j'avais éva­lué la com­plexi­té de mon algo­rithme dans le pire des cas. Or, dans notre cas, le pire arrive très rare­ment, voire jamais. En effet, en fonc­tion du motif recher­ché, il risque de n'apparaître que très peu sou­vent au sein de la PDB et sur­tout très peu sou­vent au sein d'une même struc­ture. Ce qui était le cas de mon jeu de test : le motif que je recher­chais n'était pré­sent que dans une ou deux cen­taines de pro­téines, ce qui est peu com­pa­ré à 80 000 ;
• dans l'algorithme de Bron-Ker­bosch, toutes les paires d'acides ami­nés sont éva­luées au moins une fois quelque soit la struc­ture, ce qui entraîne un coût mini­mal de cal­cul.

Ain­si, pour les struc­tures conte­nant mon motif, l'algorithme de Bron-Ker­bosch était plus effi­cace, mais cela repré­sen­tait moins de 1% des fichiers. Dans la large majo­ri­té des cas, l'algorithme naïf était bien plus effi­cace car il éli­mi­nait rapi­de­ment les struc­tures où il n'y avait pas de motif simi­laire.

Les temps de lecture/​écriture ne sont pas négligeables

J'ai éga­le­ment vou­lu voir quel était l'effet de la taille du motif sur le temps de cal­cul. En théo­rie, cher­cher un motif de 3 acides ami­nés devrait aller plus vite que cher­cher un motif de 10 acides ami­nés. Il n'en est rien pour deux rai­sons :

• les temps de lec­ture des fichiers impliquent un temps mini­mal à l'exécution du pro­gramme (1h30 pour mes 80 000 struc­tures) et que ce temps de lec­ture est là où on passe le plus de temps dans la majo­ri­té des cas ;
• un motif de 10 acides ami­nés com­plè­te­ment com­pa­tible est beau­coup plus rare qu'un motif de 3 acides ami­nés. Il y a donc moins de solu­tions et donc moins de fichiers de sor­tie à écrire (dans mon cas, un fichier PDB est écrit par solu­tion). Si il y a moins de fichiers à écrire, on va sim­ple­ment plus vite.

Conclusion

Dans cet article, j'espère vous avoir mon­tré que lorsqu'on cher­cher à trai­ter une grande quan­ti­té de fichiers, il ne faut pas seule­ment cher­cher à trai­ter chaque fichier le plus effi­ca­ce­ment pos­sible mais sur­tout réus­sir à tous les trai­ter rapi­de­ment. Ain­si, dans mon exemple, je m'étais atta­ché à trai­ter effi­ca­ce­ment chaque fichier grâce à l'algorithme de Bron-Ker­bosch. Or, même si, en théo­rie, l'algorithme naïf était moins per­for­mant sur chaque fichier, fina­le­ment il trai­tait plus rapi­de­ment la tota­li­té des fichiers.

Cela me rap­pelle une grande leçon du jeu de Go : "Cher­cher à résoudre les com­bats locaux, sans perdre de vue la glo­ba­li­té du pla­teau."