- Le blog participatif de bioinformatique francophone depuis 2012 -

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.

par Chris Cac­tus (CC-by-NC-SA 2.0)

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 !

(CC-by-SA 3.0)

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.

(CC-by-SA 3.0)


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



Pour continuer la lecture :


Commentaires

3 réponses à “Une question d'équilibre”

  1. Avatar de Claire Rioualen
    Claire Rioualen

    Mer­ci pour cet article per­ti­nent. La conclu­sion me plaît par­ti­cu­liè­re­ment, aus­si je me per­mets une pointe de pub pour le jeu de Go… Une rapide ini­tia­tion est pos­sible ici : jeu​de​go​.org

  2. C'est un bon exemple pra­tique où une ana­lyse de type "pire cas" n'est pas réa­liste. Heu­reu­se­ment, la théo­rie de la com­plexi­té couvre aus­si les ana­lyses de type "cas moyen" (ave­rage case), qui pour­rait mettre en évi­dence les avan­tages de l'algo naif.

    http://​en​.wiki​pe​dia​.org/​w​i​k​i​/​B​e​s​t​,​_​w​o​r​s​t​_​a​n​d​_​a​v​e​r​a​g​e​_​c​ase

    1. Mer­ci pour ton com­men­taire et pour le lien Rayan.
      Quand est-ce que tu viens t'essayer à la rédac­tion d'un billet pour le blog ?
      😉

Laisser un commentaire