Opinion :
Une question d'équilibre

De nombreux articles de bioinformatique commencent par une phrase du genre : "Les multiples projets de séquençage et les progrès technologiques réalisés ces dernières années permettent aujourd'hui de produire une énorme masse de données biologiques." Cette phrase sert en général à introduire l'utilisation d'algorithme plus rapide, le traitement en parallèle des données, ou leur utilisation massive afin d'extraire de la connaissance.

par Chris Cactus (CC-by-NC-SA 2.0)

Mais au-delà de ces trois thèmes, le traitement ou l'utilisation de grande quantité de données impose de réfléchir un petit peu plus précisément à l'équilibre entre temps de calcul et temps de lecture/écriture, voire même à remettre en cause la complexité théorique d'un algorithme. C'est ce qui m'est arrivé récemment et j'aimerai partager avec vous cette expérience et mes réflexions à ce sujet.

Le problème à résoudre

Mon problème était assez simple, je devais lire environ 80000 fichiers PDB (Protein Data Bank), c'est-à-dire 80 000 structures de protéines, afin de détecter si elles possédaient ou non un motif 3D d'acides aminés que j'avais donné en entrée. Vous me direz... 80 000 fichiers, ce n'est pas forcément énorme, surtout que le plus gros fichier fait 70 Mo. Mais cela suffit pour cet exemple.

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

Pour rechercher un motif d'acides aminés dans une structure, j'ai d'abord utilisé un algorithme très naïf :

  • on prend un acide aminé du motif et un acide aminé de la structure;
  • on regarde si ils sont compatibles;
  • si c'est le cas, on prend deux autres acides aminés (un dans la structure, un dans le motif);
  • on vérifie la compatibilité entre eux et avec les précédents au niveau 3D (distances inter-atomiques similaires);
  • on continue ainsi jusqu'à trouver un ensemble d'acides aminés de la structure, qui soit complètement compatible avec les acides aminés du motif.

Exprimé en combinatoire, cet algorithme consiste à tester tous les arrangements, sans répétition, de m objets parmi n, avec n le nombre d'acides aminés dans la structure et m le nombre d'acides aminés dans le motif. Autrement dit, on choisit m acides aminés parmi les n de la structure et on regarde si ils sont compatibles avec les acides aminés du motif. Cela signifie qu'il faut, dans le pire des cas, tester les n!/(n - m)! solutions et pour chacune vérifier que toutes les distances inter-atomiques sont compatibles, c'est-à-dire m*(m-1)/2 comparaisons. Ce qui est énorme !

(CC-by-SA 3.0)

Ce problème peut facilement se modéliser sous la forme d'un graphe (je vous passe la modélisation), ce qui permet de le ramener à une recherche de toutes les cliques d'une taille donnée dans le graphe (je vous laisse suivre le lien pour les explications sur les cliques). Or, nous savons que la recherche de cliques est un problème NP-complet difficile à résoudre. Néanmoins, c'est un problème bien étudié, avec des algorithmes bien connus comme celui de Bron-Kerbosch que j'ai choisi d'utiliser (le choix de cet algorithme est sujet à discussion).

J'avais alors deux algorithmes et des jeux de données que j'ai testés sur des petits exemples où je savais que la structure contenait le motif recherché. Mon algorithme de Bron-Kerbosch était plus rapide, ce qui confirmait la théorie. Je testai ensuite les deux algos sur mes 80 000 fichiers et là : surprise ! C'est l'algorithme naïf qui allait le plus vite !... Que s'était-il passé ?

Plusieurs effets entrent en compte :

  • dans l'algorithme naïf, si un couple d'acides aminés n'est pas compatible, il est éliminé. Ainsi, si aucun acide aminé n'est compatible au départ, la recherche s'est effectuée en O(n) : on a comparé tous les acides aminés de la structure avec le premier du motif;
  • j'avais évalué la complexité de mon algorithme dans le pire des cas. Or, dans notre cas, le pire arrive très rarement, voire jamais. En effet, en fonction du motif recherché, il risque de n'apparaître que très peu souvent au sein de la PDB et surtout très peu souvent au sein d'une même structure. Ce qui était le cas de mon jeu de test : le motif que je recherchais n'était présent que dans une ou deux centaines de protéines, ce qui est peu comparé à 80 000;
  • dans l'algorithme de Bron-Kerbosch, toutes les paires d'acides aminés sont évaluées au moins une fois quelque soit la structure, ce qui entraîne un coût minimal de calcul.

Ainsi, pour les structures contenant mon motif, l'algorithme de Bron-Kerbosch était plus efficace, mais cela représentait moins de 1% des fichiers. Dans la large majorité des cas, l'algorithme naïf était bien plus efficace car il éliminait rapidement les structures où il n'y avait pas de motif similaire.

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

J'ai également voulu voir quel était l'effet de la taille du motif sur le temps de calcul. En théorie, chercher un motif de 3 acides aminés devrait aller plus vite que chercher un motif de 10 acides aminés. Il n'en est rien pour deux raisons :

  • les temps de lecture des fichiers impliquent un temps minimal à l'exécution du programme (1h30 pour mes 80 000 structures) et que ce temps de lecture est là où on passe le plus de temps dans la majorité des cas;
  • un motif de 10 acides aminés complètement compatible est beaucoup plus rare qu'un motif de 3 acides aminés. Il y a donc moins de solutions et donc moins de fichiers de sortie à écrire (dans mon cas, un fichier PDB est écrit par solution). Si il y a moins de fichiers à écrire, on va simplement plus vite.

Conclusion

Dans cet article, j'espère vous avoir montré que lorsqu'on chercher à traiter une grande quantité de fichiers, il ne faut pas seulement chercher à traiter chaque fichier le plus efficacement possible mais surtout réussir à tous les traiter rapidement. Ainsi, dans mon exemple, je m'étais attaché à traiter efficacement chaque fichier grâce à l'algorithme de Bron-Kerbosch. Or, même si, en théorie, l'algorithme naïf était moins performant sur chaque fichier, finalement il traitait plus rapidement la totalité des fichiers.

(CC-by-SA 3.0)


Cela me rappelle une grande leçon du jeu de Go : "Chercher à résoudre les combats locaux, sans perdre de vue la globalité du plateau."

  • À propos de
  • Je suis actuellement en post-doc dans l'équipe DYLISS de L'IRISA à Rennes. Je travaille sur la reconstruction automatique de réseaux métaboliques. Plus particulièrement, je m'intéresse aux aspects fouille de connaissance, combinatoire, base de données en graphe. Mais dans un passé pas si lointain, je me suis aussi intéressé aux séquences de protéines, à leur alignement et à la prédiction de leur structures.

3 commentaires sur “Une question d'équilibre

  1. Merci pour cet article pertinent. La conclusion me plaît particulièrement, aussi je me permets une pointe de pub pour le jeu de Go... Une rapide initiation est possible ici : jeudego.org

  2. C\'est un bon exemple pratique où une analyse de type \"pire cas\" n\'est pas réaliste. Heureusement, la théorie de la complexité couvre aussi les analyses de type \"cas moyen\" (average case), qui pourrait mettre en évidence les avantages de l\'algo naif.

    http://en.wikipedia.org/wiki/Best,_worst_and_average_case

    • Merci pour ton commentaire et pour le lien Rayan.
      Quand est-ce que tu viens t\'essayer à la rédaction d\'un billet pour le blog ?
      😉

Laisser un commentaire