Chapitre 11 • Prédiction de structures 3D
152
s’agira soit d’échantillonner des conformations en recherche conformationnelle soit
d’optimiser un modèle obtenu par construction.
Dans ce cas, la dynamique moléculaire s’apparente au problème de l’algorithme
du voyageur de commerce qui est un problème NP-complet pour lequel il est facile
de trouver facilement une solution acceptable dans un temps raisonnable (20 s) pour
80 villes (4,5.10
116
trajets).
11.8 MODÉLISATION DE STRUCTURES 3D
La prédiction de structure 3D est un domaine de recherche très actif et constitue un des
objectifs de la bioinformatique structurale. Il existe quatre grandes classes de méthodes :
• Identification de repliement par enfilage (ou threading)
• Modélisation par homologie
• Alphabets structuraux
• Méthode ab initio
Le voyageur de commerce doit revenir à son point de départ après avoir visité un
nombre fini de villes en parcourant le minimum de distance sans parcourir deux
fois le même trajet. Pour N villes le nombre de possibilités est N = (N - 1) ! / 2.
Un problème NP-complet est solvable dans le pire cas par un algorithme dans un
temps d’exécution exponentiel en la taille de l’entrée.
Figure 11.16 – Deux solutions acceptables de 7 919 km (gauche) et
7 981 km (droite) obtenues par recuit simulé pour 80 villes de France.
152
s’agira soit d’échantillonner des conformations en recherche conformationnelle soit
d’optimiser un modèle obtenu par construction.
Dans ce cas, la dynamique moléculaire s’apparente au problème de l’algorithme
du voyageur de commerce qui est un problème NP-complet pour lequel il est facile
de trouver facilement une solution acceptable dans un temps raisonnable (20 s) pour
80 villes (4,5.10
116
trajets).
11.8 MODÉLISATION DE STRUCTURES 3D
La prédiction de structure 3D est un domaine de recherche très actif et constitue un des
objectifs de la bioinformatique structurale. Il existe quatre grandes classes de méthodes :
• Identification de repliement par enfilage (ou threading)
• Modélisation par homologie
• Alphabets structuraux
• Méthode ab initio
Le voyageur de commerce doit revenir à son point de départ après avoir visité un
nombre fini de villes en parcourant le minimum de distance sans parcourir deux
fois le même trajet. Pour N villes le nombre de possibilités est N = (N - 1) ! / 2.
Un problème NP-complet est solvable dans le pire cas par un algorithme dans un
temps d’exécution exponentiel en la taille de l’entrée.
Figure 11.16 – Deux solutions acceptables de 7 919 km (gauche) et
7 981 km (droite) obtenues par recuit simulé pour 80 villes de France.