STAGE DE MASTER RECHERCHE - LAAS-CNRShomepages.laas.fr/nic/AMoRo/publi/RapportStageBrice.pdfUne fois ces bases établies, le problème consiste à explorer un espace dans lequel les

MASTER EEAS - Système Automatiques, Informatiques et Décisionnels

******

ECOLE DOCTORALE SYSTÈMES

TOULOUSE

Année universitaire 2004 - 2005

******

STAGE DE MASTERRECHERCHE

PLANIFICATION DE MOUVEMENT POUR LAMODÉLISATION MOLÉCULAIRE

LAAS - CNRSToulouse

SALVA Brice

Groupe : RIAResponsable stage : Juan CORTES

MASTER EEAS - Système Automatiques, Informatiques et Décisionnels

******

ECOLE DOCTORALE SYSTÈMES

TOULOUSE

Année universitaire 2004 - 2005

******

STAGE DE MASTERRECHERCHE

PLANIFICATION DE MOUVEMENT POUR LAMODÉLISATION MOLÉCULAIRE

LAAS - CNRSToulouse

SALVA Brice

Groupe : RIAResponsable stage : Juan CORTES

Remerciements

Tout d’abord, je souhaite remercier mon maître de stage, Juan Cortés, chercheur permanentdu LAAS-CNRS dans le groupe Robotique et Intelligence Artificielle. Merci en particulier pourl’enthousiasme qu’il a su me communiquer, l’aide précieuse qu’il m’a apportée et la confiance qu’ilm’a accordée en me livrant une partie de la réalisation de ce projet.

Merci également à Thierry Siméon pour avoir suivi l’évolution de mon travail depuis mon arrivéeau LAAS.

Je tiens aussi à citer Christophe Chassot, non pour les escapades en course à pied qu’il m’a faitendurer, mais plutôt pour m’avoir mis en contact avec Juan Cortés il y a deux ans et m’avoir ainsipermis de découvrir ce domaine de recherche captivant qu’est la planification de mouvement.

Je tiens également à mentionner les stagiaires qui, comme moi, réalisaient un projet de find’études au LAAS et avec qui j’ai eu le plaisir de passer de très agréables moments, en particulier :Mathias Fontmarty pour son humour et sa bonne humeur permanente, Jesse Himmelstein pourses conseils toujours agrémentés d’un soupçon d’accent américain, Jonathan Blanchard pour sonsens pratique et son incroyable habileté en matière de pliages papier, Noureddine Gamani pour sagentillesse et sa générosité, Olivier Dusacq pour ses anecdotes de vieux loup de mer, mais encoreFrancesco Mennini, Mathieu Poirier et Sébatien Tredan.

Je remercie enfin l’ensemble du personnel du LAAS pour sa convivialité et son sens du service.

Table des matièresIntroduction 1

1 MéthodesMécanismes et planification de mouvement 3

1.1 Modélisation mécanique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31.1.1 Représentation d’un mécanisme articulé . . . . . . . . . . . . . . . . . . . . 31.1.2 Contraintes de fermeture . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

1.2 La planification de mouvement . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61.2.1 Notion d’espace de configuration . . . . . . . . . . . . . . . . . . . . . . . . 61.2.2 Formulation du problème . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61.2.3 Les méthodes d’exploration probabilistes . . . . . . . . . . . . . . . . . . . . 8

2 ApplicationLe mouvement moléculaire 11

2.1 Les interactions moléculaires en biologie . . . . . . . . . . . . . . . . . . . . . . . 112.1.1 Les entités moléculaires : protéines et ligands . . . . . . . . . . . . . . . . . 112.1.2 Intérêt de l’étude des interactions . . . . . . . . . . . . . . . . . . . . . . . . 13

2.2 Prédiction des mouvements moléculaires : problématique . . . . . . . . . . . . . . 142.2.1 Influence de la flexibilité des molécules . . . . . . . . . . . . . . . . . . . . . 142.2.2 Principes et limites de approches énergétiques . . . . . . . . . . . . . . . . . 14

2.3 Une approche géométrique de la modélisation moléculaire . . . . . . . . . . . . . 142.3.1 Contraintes propres à la modélisation moléculaire . . . . . . . . . . . . . . . 142.3.2 Modèle géométrique des molécules . . . . . . . . . . . . . . . . . . . . . . . 15

2.4 Algorithmes géométriques dédiés à la modélisation moléculaire . . . . . . . . . . 162.4.1 Exploration de l’espace de conformation . . . . . . . . . . . . . . . . . . . . 162.4.2 Echantillonnage des conformations en présence de boucles . . . . . . . . . . 172.4.3 Détection de collision . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

3 LogicielLes premiers pas de BioMove3D 19

3.1 BioMove3D : un réel besoin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193.1.1 Cohabitation de différents formats de données dans Move3D . . . . . . . . . 193.1.2 Nouvelles structures de données dans BioMove3D : motivations . . . . . . . 20

3.2 Vers une représentation cohérente des molécules . . . . . . . . . . . . . . . . . . . 203.2.1 Une molécule selon le format de la Protein Data Bank . . . . . . . . . . . . 203.2.2 Structuration de l’information biochimique . . . . . . . . . . . . . . . . . . 223.2.3 Structuration mécanique des chaînes moléculaires . . . . . . . . . . . . . . . 24

3.3 Elaboration des informations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 283.3.1 Première intégration dans Move 3D : le traducteur . . . . . . . . . . . . . . 283.3.2 Nouvelles fonctions d’interface . . . . . . . . . . . . . . . . . . . . . . . . . 29

3.4 Le module énergétique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 343.4.1 Intérêt d’une approche énergétique . . . . . . . . . . . . . . . . . . . . . . . 343.4.2 Mise en oeuvre du module énergétique au sein de BioMove3D . . . . . . . . 34

iv Table des matières

4 PerspectivesAméliorations algorithmiques 37

4.1 L’échantillonnage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 374.2 Boucles multiples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 374.3 Exploration combinée boucles/ligands . . . . . . . . . . . . . . . . . . . . . . . . 38

Conclusion 39

Références bibliographiques 41

Introduction

Aujourd’hui, l’étude des intéractions entre biomolécules suscite un vif intérêt au sein de la com-munauté scientifique. Elle représente un enjeu considérable dans les domaines de la pharmacologieet des biotechnologies.

En effet, les interactions concernant les protéines jouent un rôle fondamental dans de nom-breux processus biologiques. Pour traiter certaines pathologies, les agents actifs synthétisés par lesindustries pharmaceutiques doivent interagir avec des biomolécules spécifiques sans pour autantpertuber leur environnement. Cela suppose donc d’étudier précisement les sites actifs des moléculescibles.

Cependant, les études in vivo requièrent des expérimentations coûteuses, longues et laborieusesà mettre en oeuvre. Pour analyser un seul type d’interaction, il faut généralement synthétiserplusieurs molécules spécifiques. Trouver un agent actif approprié peut nécessiter des mois voire desannées de tests en laboratoire sans que le succès des recherches ne soit garanti.

La modélisation moléculaire constitue un soutien important à l’expérimentation. Ces dernièresannées, les outils de modélisation ont permis de réaliser des prédictions très pertinentes. A l’échellemoléculaire, ils sont utilisés pour analyser les altérations responsables de certaines maladies et pourconcevoir de nouveaux médicaments.

Malheureusement, les méthodes de modélisation classiques présentent des limitations impor-tantes qui empêchent de prendre en compte la flexibilité des molécules d’une manière générale.Cette flexibilité doit être considérée pour développer des outils de modélisation précis.

De récents travaux de robotique permettent désormais de traiter des problèmes concernant lemouvement contraint de mécanismes articulés complexes.

En effet, les techniques d’exploration par échantillonnage aléatoire introduites en planificationde mouvement depuis une dizaine d’années ont remplacé les méthodes déterministes classiques ets’appliquent désormais à une grande classe de systêmes mécaniques, ouvrant des perspectives pluslarges que les applications en robotique, notamment en modélisation moléculaire. Ces méthodestentent de relier une configuration initiale à une configuration finale en construisant un graphedes configurations. Les noeuds de ce graphe sont choisis aléatoirement dans l’espace des configu-rations, prenant en compte les degrés de liberté du système. Une fois construit, le graphe capturela connectivité de l’espace de configuration, tenant compte d’un ensemble de contraintes. Cettebase méthodologique donne lieu à un foisonnement de techniques avec des heuristiques adaptéesà diverses classes de problèmes. Le groupe Recherche et Intelligence Artificielle du LAAS a unelongue expérience dans ce domaine et développe depuis plusieurs années une plate-forme logicielleMove3D dédiée à ces applications.

Une approche originale mise en oeuvre récemment au LAAS consiste à modéliser les moléculescomme des systèmes mécaniques et à analyser leurs mouvements au travers des algorithmes derobotique. Les premiers résultats prometteurs ont poussé au développement d’une nouvelle plate-forme : BioMove3D.

2 Introduction

Plusieurs objectifs ont donc guidé le déroulement de mon stage. Dans un premier temps, ils’agissait de comprendre les fondements théoriques de planification de mouvement et les spécificitésde l’algorithmique du mouvement moléculaire.

Sur le plan pratique, je devais contribuer au développement de nouvelles fonctionnalités liées àla biologie structurale dans le logiciel Move3D.

A terme, ces développements devaient permettre de faciliter les efforts de recherche algorith-mique sur deux applications particulières :

• L’analyse de la mobilité des boucles protéiques,• Le calcul et l’analyse du chemin d’accès d’un ligand au site actif d’une protéine.

La première partie de ce rapport (chapitre 1) présente les bases théoriques de la planificationde mouvement ; après avoir défini les concepts et les outils nécessaires, nous posons le problèmedans sa forme la plus générale et présentons les méthodes récentes qui permettent de le résoudre.

Le chapitre 2 montre comment exploiter les méthodes précédentes pour répondre aux difficultésposées par la modélisation moléculaire à l’heure actuelle. Nous expliquons la démarche suiviepour modéliser une molécule sous forme de système mécanique articulé ; nous présentons aussi lestechniques qui permettent de traduire les contraintes moléculaires et les algorithmes spécifiquesqui permettent de traiter les mouvements moléculaires contraints.

Ma contribution est plus particulièrement mise en relief dans le chapitre 3. En effet, l’objectiftechnique de mon stage de Master Recherche était de participer aux premiers développementsd’un logiciel spécifique à la modélisation moléculaire : BioMove3D. En accord avec les besoinsdes chercheurs en planification de mouvement et des biolologistes, il fallait structurer les donnéesd’ordre biochimique et les données d’ordre mécanique à partir de différentes sources d’information.J’ai donc été amené à définir de nouvelles structures de données appropriées à la modélisationmoléculaire. Dans la partie 3.2, je justifie leur conception ; j’explique ensuite leur mise en oeuvre(section 3.3).

De plus, la nouvelle plate-forme BioMove3D comporte désormais un module de calcul énergé-tique utilisant l’interface de programmation que j’ai développée. Son intégration est présentée dansla partie 3.4.

Enfin, à partir des développements précédents, des améliorations algorithmiques sont envisa-gées : elles seraient susceptibles d’améliorer l’efficacité et les performances des applications exis-tantes. De plus, elles exploiteraient pleinement les nouvelles structures de données. Nous présente-rons ces perspectives d’évolution dans un dernier chapitre (chapitre 4).

Chapitre 1

Méthodes : Mécanismeset planification de mouvement

Dans de nombreux domaines scientifiques, les problèmes sont posés et résolus à partir de modèlesdes systèmes réels. Dans le domaine de la planification de mouvement, nous manipulons des modèlesgéométriques inspirés des développements de la robotique classique. Ainsi, pour modéliser les objetspropres au domaine de la modélisation moléculaire, nous ferons appel à ces notions (présentées dansla partie 1.1).

Une fois ces bases établies, le problème consiste à explorer un espace dans lequel les contraintescinématiques ont une interprétation géométrique. Nous mettrons cela en évidence en formulantprécisément le problème de planification de mouvement (partie 1.2).

1.1 Modélisation mécanique

1.1.1 Représentation d’un mécanisme articuléCorps rigides

Les éléments que nous allons manipuler sont des objets rigides. Ces corps rigides (appelés sim-plement rigides par abus de langage) sont en mouvement dans l’espace physique à trois dimensionsR3 ; en robotique, il est traditionnellement appelé espace de la tâche. Ainsi, un rigide est donc aussicaractérisé par un ensemble de paramètres qui précisent sa position et son orientation dans cetespace. Concrètement, un repère fixe dans R3 est défini comme repère absolu ; un autre repère estattaché à l’objet que l’on désire caractériser. La position relative du repère de l’objet par rapportau repère absolu (Fig. 1.1) est donnée par :

• un vecteur (xo, yo, zo) correspondant à la position de l’origine du repère de l’objet dans lerepère absolu,• une matrice 3×3 dont les colonnes sont formées par les cosinus directeurs des axes du repère

de l’objet dans le repère absolu.

Nous distinguerons par la suite deux catégories d’objets : les objets mobiles correspondant auxcorps rigides qui constituent le système en mouvement, et les objets statiques (généralement, desobstacles). Notons qu’un objets mobile peut être un obstacle si les corps du système articulé enmouvement ne doivent pas entrer en collision entre eux.

4Chapitre 1. Méthodes

Mécanismes et planification de mouvement

γ

α

β

{xo, yo, z

o}FW

O

FOZ

XO

X

Y ′, Y ′′

YO

Z′

Y

Y

Z′′, ZO

X, X′

Z

X′′

Fig. 1.1 – Six paramètres {xo, yo, zo, γ, β, α} definissent la position et l’orientation d’un solide.

Mécanisme articulé

Un mécanisme articulé est un ensemble de corps rigides partiellement connectés entre eux.Deux rigides voisins sont reliés par une liaison J qui limitent leurs mouvements relatifs.Il existe donc plusieurs types de liaisons en fonction des degrés de liberté de mouvement qu’elles

autorisent. Dans ce document, nous considérerons principalement trois types de liaisons :

• Les liaisons type freeflying : elles ne contraignent aucun mouvement, les trois rotations et lestrois translations sont permises.• Les liaisons rotoïdes : elles empêchent toute translation.• Les liaisons prismatiques : elle ne permettent qu’une seule translation selon un axe donné.

Par conséquent, on associe à chaque articulation une ou plusieurs variable(s) articulaire(s)correspondant aux degrés de liberté permis. Une variable articulaire peut prendre plusieurs valeursdans un intervalle limité (articulation contrainte par la présence d’arrêts mécaniques).

Variables articulaires et configurations

Le modèle tridimensionnel d’un mécanisme est défini par la position spatiale de tous ses corpsrigides. Pour des systèmes ne faisant intervenir que des liaisons prismatiques ou rotoïdes, il estpossible de représenter le mouvement d’un corps mobile par rapport au corps qui le précède enutilisant quatre variables (variables articulaires) : le principe est décrit dans [Craig 89]. Nous avonsrespecté ce principe en adoptant la convention de Dénavit Hartenberg modifiée (mDH).

Ainsi, deux variables articulaires dépendent de la géométrie du rigide précédent :

• ai−1 (link length),• αi−1 (link twist).

Les deux autres caractérisent l’interconnexion des rigides :

• δi (link offset),• θi (joint angle).

1.1. Modélisation mécanique 5

Zi−1Zi

Yi−1

Xi−1

Xi

αi−1

ai−1

Yi

di

θi

Ai−1Ai

Ji−1 axisJi axis

Fig. 1.2 – Paramètres définissant la position relative de deux rigides connectés par une ar-ticulation à 1 degré de liberté (en respectant la convention mDH présentée dans [Craig 89]).

Une transformation homogène (sous-forme de matrice 4 × 4) permet de passer d’un rigide ausuivant (matrice 1.1).

i−1Ti =

cos θi − sin θi 0 ai−1

sin θi cosαi−1 cos θi cosαi−1 − sinαi−1 −di sinαi−1

sin θi sinαi−1 cos θi sinαi−1 cosαi−1 di cosαi−1

0 0 0 1

(1.1)

En fixant une valeur pour chaque variable articulaire d’un mécanisme à chaîne ouverte, nouspouvons définir une position précise de ce mécanisme : il s’agira d’une configuration.

1.1.2 Contraintes de fermetureLa chaîne cinématique peut comporter des chaînes fermées appelées boucles (un exemple est

donné sur la figure 1.3). Lorsqu’une ou plusieurs boucles sont impliquées dans un mécanismearticulé, certaines variables articulaires ne sont plus indépendantes : cela restreint les configurationsenvisageables pour le système. Mathématiquement, cela se traduit par des équations de fermeture.

Les équations de fermeture peuvent être obtenues par une unique relation entre les transforma-tions homogènes associées aux rigides de la boucle.

Si le système présente plusieurs boucles, une même variable articulaire pourra être impliquéedans plusieurs relations.

Les contraintes de fermeture s’expriment ainsi par un système d’équations non linéaires multi-variables dont la résolution est très complexe voire impossible analytiquement.



θ2

θ3

θ4

b

g

θ1

h

a

Fig. 1.3 – Un assemblage planaire dont la chaîne cinématiqueest fermée.

1.2 La planification de mouvementRésoudre un problème de planification de mouvement consiste à calculer les mouvements réali-

sables par un système physique dans son environnement. Dans cette partie, nous approfondissonscette définition à l’aide de la notion d’espace de configuration.

1.2.1 Notion d’espace de configurationCette notion a été introduite par Lozano-Pérez en 1983 ([Lozano 83]) et constitue l’un des

piliers de la formulation du problème de planification de mouvement. Ainsi que nous l’avons déjàmentionné, une configuration, notée q , est un ensemble minimal de paramètres qui permet depositionner un système mobile dans l’espace physique.

L’ensemble des configurations q que peut adopter un système articulé constitue l’espace deconfiguration C.

Dans notre cas, les contraintes imposées par les articulations réduisent le nombre de paramètresrequis pour localiser un corps. Nous avons vu que ces paramètres correspondaient aux degrés deliberté permis par les articulations du mécanisme. Pour les chaînes cinématiques ouvertes, l’espacede configuration correspond à l’espace des variables articulaires.

1.2.2 Formulation du problèmeA l’origine, le problème de planification de mouvement a été formulé de la façon suivante.Soit un système poly-articulé A dans un environnement statique comportant nobst obstacles

B1 . . .Bnobst, on donne une position et une orientation initiale du système ainsi qu’une position et

une orientation cibles dans l’espace de la tâche. Il s’agit de générer un chemin τ définissant uneséquence continue de positions (et orientations) permettant d’éviter les collisions avec les Bi ; si untel chemin n’existe pas, il faut rendre compte de l’échec de la recherche.

1.2. La planification de mouvement 7

Dans l’espace de configuration, la recherche d’un chemin acceptable sera guidée par trois règlesmajeures :

• Eviter les collisions avec des obstacles,• Eviter les collisions entre deux corps rigides distincts du système articulé (les auto-collisions),• Satisfaire les contraintes de fermeture des éventuelles boucles dans la chaîne cinématique.

On représente donc dans l’espace des variables articulaires les zones interdites correpondantaux obstacles de l’espace de la tâche. Les contraintes de fermeture des boucles modifient considéra-blement la topologie de l’espace des configurations acceptables. En présence de telles contraintes,les configurations possibles forment un ensemble de d’hypersurfaces (des sous-variétés mathéma-tiques) contenu dans l’espace articulaire (1.4). Un chemin acceptable sera donc un chemin définisur ces surfaces et reliera les configuration de départ (qinit) et d’arrivée (qbut). Il peut ne pas yavoir de solution à un tel problème si qinit et qbut ne sont pas situées sur des surfaces en contact.

Q

q4

M1

M2

q5

q1

q2

Qobst

Qobst

Qobst

θ1

θ3

θ2

M3

M4

Sq3 M2

M1

Fig. 1.4 – Formulation du problème de planification de mouvement en présence de contraintes de ferme-tures. L’espace des variables articulaires est noté Q et la projection des obstacles Qobst



1.2.3 Les méthodes d’exploration probabilistesPlusieurs démarches ont été proposées pour contourner la complexité inhérente aux problèmes

de planification de mouvement. Parmi celles-ci, depuis une dizaine d’années, des approches pro-babilistes ont permis d’envisager la résolution de problèmes mettant en jeu un grand nombre devariables articulaires.

Méthodes de type Probabilistic RoadMap (PRM)

D’après [Kavraki 96], lorsque l’on résout un problème de planification de mouvement selonl’approche PRM, trois phases doivent être envisagées :

• une phase d’apprentissage pour capturer la connexité de l’espace par construction d’ungraphe de recherche,• une phase de recherche dans ce graphe,• une phase de lissage de la trajectoire pour éliminer les détours parasites créés par la

génération aléatoire.

Fig. 1.5 – (a) Le graphe (à gauche) - (b) La trajectoire (au centre) - (c) L’op-timisation (à droite).

La phase d’apprentissage consiste à tirer aléatoirement une configuration uniformément danstout l’espace des configurations et à l’ajouter au graphe si elle est dans l’espace libre.

Cette phase met en oeuvre un planificateur local pour construire des chemins qui respectentles contraintes cinématiques du système articulé entre la configuration tirée et les configurationsles plus proches.

On vérifie que ces chemins locaux sont valides en discrétisant et en testant l’absence de collisionspour chaque configuration intermédiaire. Un détecteur de collision permet de déterminer sices conditions de non collision sont remplies : il évalue d’une part les collisions entre le systèmemécanique et les obstacles mais aussi les auto-collisions au sein même du système. Si le cheminlocal est valide , il devient une arête du graphe, sinon il est ignoré. Apres avoir ajouté un certainnombre de configurations au graphe (paramètre de l’algorithme), on considère que cet ensemble dechemins locaux capture bien la connexité de l’espace (cf. Figure 1.5 (a) ).

Les appels au détecteur de collision sont très nombreux lors de l’exécution de l’algorithme. Sesperformances dépendent donc en partie des performances du détecteur de collision.

1.2. La planification de mouvement 9

La phase de recherche répond au problème de l’existence d’une trajectoire entre une configu-ration initiale et une configuration finale. Cela revient à relier ces configurations au réseau générédans la phase d’apprentissage, et à déterminer si elles appartiennent à une même composanteconnexe. Si tel est le cas, une trajectoire répondant au problème posé pourra être construite parconcaténation des chemins locaux de la composante connexe de liaison (cf. Figure 1.5 (b) ).

La phase d’optimisation / lissage met en oeuvre une méthode d’optimisation de la trajectoireinitialement planifiée. Selon un critère de coût établi, elle permet de tendre vers un meilleur cheminrépondant au problème posé (cf. Figure 1.5 (c) ).

Les approches basées sur ce principe sont dits "multi-query" car, après la phase d’apprentissage,on peut résoudre plusieurs problèmes, de manière très rapide, en effectuant plusieurs requêtes(plusieurs appels à la phase de recherche).

L’algorithme PRM permet d’obtenir de très bons résultats, même pour des problèmes compor-tant de nombreux degrés de liberté. Cependant, sur des problèmes présentant des passages étroits(dans l’espace des configurations), ses performances diminuent. En effet, il est plus difficile de tireraléatoirement une configuration dans un passage étroit que dans une zone large. Il faut donc tirerbeaucoup plus de points pour capturer la connexité de l’espace.

La méthode RRT (Rapidly-exploring Random Tree)

Si la méthode PRM opère un échantillonnage aléatoire de l’espace libre, les RRTs ([Kuffner 00])sont basés sur un principe de diffusion dans cet espace à partir d’une source. Les graphes engen-drés sont donc des arbres dont les racines sont des positions données (point de départ et fin dumouvement que l’on veut planifier).

Fig. 1.6 – Expansion d’un arbre RRT dans un espace libre.

Les arbres RRT se construisent incrémentalement depuis la position de départ (et éventuel-lement d’arrivée pour la version bidirectionnelle). Ils ne nécessitent pas d’avoir des planificateurslocaux symétriques. Par contre l’arbre créé est détruit à chaque fin d’expérience, et ne servira plussi on change les positions initiales et finales. C’est donc une méthode qui fait une recherche unique.

L’algorithme comporte deux phases, la recherche d’une trajectoire et son optimisation (cettedeuxième phase est similaire à celle présente dans la méthode PRM). Dans la version mono-directionelle de l’algorithme, on fait une diffusion uniquement à partir de la position de départ eton essaye d’atteindre la position finale. En revanche, dans la variante bidirectionnelle, on fait une



diffusion à partir des deux positions (départ et arrivée) et on essaye de connecter les deux arbresgénérés.

L’algorithme considère l’extension d’un arbre (ou deux arbres pour la version bidirectionnelle).L’extension des arbres se fait en deux temps. Un tirage aléatoire permet de déterminer le noeudde l’arbre que l’on tentera d’étendre (choix du plus proche voisin) ; la configuration tirée n’estpas nécessairement contenue dans l’espace libre. Par contre, elle donne la direction d’extension del’arbre. Ensuite, on recherche une nouvelle configuration réalisable (appartenant à l’espace libre)sur le chemin local défini par cette direction.

Il y a deux manières de placer cette nouvelle configuration :

• La méthode Extend : on place la nouvelle configuration à une distance de l’arbre égale à unpas donné sur le chemin local,• La méthode Connect : on parcourt le chemin local vers la configuration tirée aléatoirement

et on place la nouvelle configuration, soit au contact du premier obstacle trouvé, soit àl’extrémité du chemin local. En pratique, on utilise la methode extend itérativement avecun pas faible jusqu’à ce que la configuration soit en collision et on conserve la derniereconfiguration libre tirée.

Une fois garantie qu’il existe un chemin local entre l’arbre et la nouvelle configuration alors onajoute celle-ci à l’arbre ainsi que le segment qui relie ces configurations. L’algorithme se terminelorsque l’on peut rejoindre l’objectif à partir de l’arbre initial ou lorsque l’on a dépassé le nombremaximum de noeuds autorisés.

Fig. 1.7 – Exemple de trajectoire donnée par un algorithme RRT.

Cette méthode permet d’obtenir une expansion assez rapide du graphe, puisque à chaque étape,il n’est fait appel qu’une seule fois au planificateur local. La propagation du graphe est biaisée parles positions aléatoires tirées dans tout l’espace. Cette particularité entraîne une extension rapidedu graphe vers les grands espaces libres. Contrairement à une marche aléatoire pure et simpledont l’efficacité est réduite (elle explorerait peu d’espace en comparaison du nombre de positionsgénérées), cette méthode permet de couvrir rapidement de grands espaces de façon assez dense.

En pratique, la méthode RRT permet de sortir facilement d’espaces très contraints, pour lesquelsla méthode PRM classique ne donne pas de résultat satisfaisant en un temps fini.

Chapitre 2

ApplicationLe mouvement moléculaire

2.1 Les interactions moléculaires en biologie

2.1.1 Les entités moléculaires : protéines et ligands

Les protéines sont de longues molécules, des polymères, constituées d’acides aminés liés. On parlede protéine lorsque plus de 100 acides aminés sont liés au sein d’une chaîne d’acides aminés. Onestime qu’il existe environ trente mille protéines différentes chez l’Homme, dont 2% seulement ontété décrites.

Dans notre organisme, elles sont les résultantes du message génétique contenu dans nos gènes.Elles ont des fonctions très diverses : certaines pourront avoir une fonction structurale (elles parti-cipent à la cohésion structurale des cellules entre elles), enzymatique (elles catalysent les réactionschimiques de la matière vivante) ou encore une fonction de messager (pour les protéines impliquéesdans des processus de signalisation cellulaire). On les retrouve sous différentes formes : enzymes,hormones, récepteurs, neurotransmetteurs . . ..

Fig. 2.1 – Une intéraction ligand - protéine.

12Chapitre 2. Application

Le mouvement moléculaire

Les monomères élémentaires qui constituent les protéines, les acides aminés, sont au nombrede 20. Bien qu’ils soient de compositions atomiques différentes, ils ont tous la même structure :un squelette N-Cα-C-O commun sur lequel est attaché une chaine latérale R spécifique à chacund’entre eux.Le groupe amide -CO-NH- liant deux acides aminés constitue une liaison peptidique.En conséquence, chaque polymère d’une protéine est souvent mentionné comme étant une chaînepolypeptidique.

Fig. 2.2 – Les briques élémentaires d’une protéine sont les acides aminés connectéspar des liaisons peptidiques.

Une protéine est généralement composée de plusieurs chaînes polypeptidiques. On distingueainsi différents niveaux d’organisation dans une structure protéique.

La struture primaire correspond à l’ordre d’enchaînement des acides aminés. La séquenceest donnée en partant de l’acide aminé N-terminal (extrémité NH2) vers l’acide aminé C-terminal(extrémité COOH) qui correspond au sens de la synthèse des protéines.

Les plans de deux liaisons peptidiques successives s’orientent l’un par rapport à l’autre parrotation autour des liaisons N-Cα (angle φ) et Cα-C (angle ψ) . C’est la disposition de ces plansles uns par rapport aux autres qui va être à l’origine de la structure spatiale de la protéine.

Dans chaque liaison peptidique, les centres respectifs des quatre atomes -CO-NH- et des deuxcarbones α des acides aminés sont situés dans un même plan. Géométriquement, cela se traduitpar une rotation quasi-impossible de la liaison peptidique ( angle ω nul ou égal à π) 1.

La struture secondaire correspond à un arrangement régulier des acides aminés selon un axe.Il existe deux types principaux de structures secondaires : l’hélice, caractérisée par l’enroulementdes liaisons peptidiques autour d’un axe, et le feuillet plissé dans lequel deux chaînes sont disposéesparallèlement l’une à l’autre et orientées en sens inverse.

Les structures tertiaire et quaternaire mettent en évidence les repliements de la chaîneprotéique (voir figure 2.3). Ces repliements sont liés à l’existence de résidus encombrants ou chargés.La structure de la molécule s’organise alors selon les trois directions de l’espace. Plusieurs sousunités protéiques peuvent être associées par des interactions électrostatiques (liaisons hydrogènesentre acides aminés, liaisons ioniques, liaisons hydrophobes entre résidus apolaires, ponts disulfures. . .).

1La rotation autour de la liaison peptidique n’est pas complètement bloquée : en réalité, ω peut varier trèslégèrement.

2.1. Les interactions moléculaires en biologie 13

Fig. 2.3 – Structures tertiaire et quaternaire d’une protéine. Sur la figure de gauche,on distingue très bien les différentes boucles entre les hélices.

Un ligand est une molécule pouvant se lier de façon non covalente à un récepteur ou à un sitespécifique sur une protéine. Il est très souvent amené à entrer en intéraction avec elle (figure 2.1).La protéine joue alors le rôle d’un récepteur sur lequel il se lie de façon spécifique. Cet arrimageinduit généralement une réaction.

La structure des ligands n’est pas aussi ordonnée que celle des protéines. Ils arborent différentesformes et compositions chimiques.

2.1.2 Intérêt de l’étude des interactionsConcevoir un nouveau médicament demande souvent de trouver un ligand qui va parfaitement

se loger dans le site récepteur d’une protéine. En effet, les récepteurs disposés sur la membraneextérieure des cellules permettent de transmettre des messages nécessaires à la régulation de l’ac-tivité de l’organisme. Or ces récepteurs sont des protéines. Lorsque ce mécanisme d’intéraction estperturbé, il faut trouver des molécules capables de le rétablir. Pour cela, les industries pharmaceu-tiques utilisent des méthodes exhaustives, en particulier la technique du screening. Le principe decette approche consiste à choisir une famille chimique de molécules et à les passer au crible d’unebatterie de tests pour déceler celles qui présentent une activité ayant un possible effet thérapeu-tique. Généralement, moins de 1% des molécules testées sont retenues. Cette méthode a fait sespreuves depuis longtemps mais elle est lente et couteuse 2.

Dans la nature, les réactions chimiques sont très souvent catalysées par des enzymes. La réactiona généralement lieu sur une petite molécule - le ligand - lorsqu’elle se trouve dans le site actif del’enzyme. L’accessibilité du ligand à ce site peut se révéler être un facteur déterminant pour laréaction.

2A titre d’illustration, la mise au point d’un médicament exige environ 8 à 12 ans de recherche et de dévelop-pement ; Pour une nouvelle molécule, le coût était estimé à 2 ou 3 milliards de francs en 1999 (sources : Syndicatnational de l’industrie pharmaceutique).



2.2 Prédiction des mouvements moléculaires : problématiqueA partir de la conformation d’une protéine, les travaux récents tentent d’approcher la flexibilité

moléculaire, pour mieux comprendre comment elle interagit avec d’autres molécules.

2.2.1 Influence de la flexibilité des moléculesLes macromolécules biologiques comportent généralement des segments particulièrement flexibles,

appelés boucles ; ces dernières jouent un rôle fondamental dans les interactions moléculaires. Dansles réactions enzymatiques, une petite molécule (le ligand) doit accéder au site actif d’une pro-téine ; l’accès sera d’autant plus aisé qu’aucune boucle de la protéine n’entrave le chemin qui mèneà la cavité catalytique. De même, les chaînes flexibles à la surface des anticorps ont pour pro-priété d’adapter leur configuration à l’antigène associé. Il est donc essentiel de prendre en comptela flexibilité des boucles moléculaires lorsque l’on désire développer des techniques informatiquespermettant de prédire des interactions avec précision.

2.2.2 Principes et limites de approches énergétiquesPour prédire les interactions moléculaires, les chercheurs emploient des techniques de simula-

tions informatiques intensives. Les outils classiques de modélisation se basent sur l’évaluation del’énergie associée aux différentes conformations (ou configurations) : la structure moléculaire a eneffet tendance à adopter les positions de plus basse énergie. Plusieurs approches sont particulière-ment utilisées : la dynamique moléculaire et les simulations de Monte-Carlo en font partie. A cejour, s’il est vrai que ces méthodes permettent de modéliser de petits mouvements, elles ne sont pasen mesure de prédire l’influence des mouvements de grande ampleur sur l’activité de la molécule.Deux raisons sont principalement invoquées :

• La complexité des modèles énergétiques allonge considérablement les temps de calculs. Defait, il n’est possible d’envisager que des modèles énergétiques très simplifiés ; seules desvariations de conformations très locales sont étudiées avec des modèles plus raffinés.• Les algorithmes actuels ont tendance à être piégés par les minima locaux de la fonction

d’énergie de la molécule ; ils ne parviennent pas à garantir un minimum énergétique surl’ensemble des configurations possibles. Ainsi, la prédiction reste à nouveau purement localealors que des conformations plus favorables énergétiquement peuvent exister.

L’analyse globale des conformations d’une ou de plusieurs molécules en interaction demeuredonc un problème largement ouvert.

2.3 Une approche géométrique de la modélisation moléculaire

2.3.1 Contraintes propres à la modélisation moléculaire

Les degrés de liberté d’une molécule sont établis à partir des interactions atomiques de liaison(liaisons covalentes) ; ils prennent aussi en compte d’autres types d’interactions.

Les interactions de liaison sont modélisées par la variation des positions relatives des atomes,généralement données en coordonnées intrinsèques à la molécule :

• La longeur des liaisons (stretching)• L’angle de liaison (bending)• L’angle de torsion (torsion)

2.3. Une approche géométrique de la modélisation moléculaire 15

Fig. 2.4 – Variations des positions relatives des atomes au sein d’une molécule.

De petites variations des deux premiers paramètres (stretching et bending) par rapport à leursvaleurs idéales produisent une grande augmentation de l’énergie de la conformation associée. Dansle modèle mécanique, ils sont donc maintenus constants. En revanche, on associe à chaque anglede torsion une articulation rotoïde.

Des contraintes de fermeture des boucles sont introduites dans la chaîne cinématique mo-délisant la chaîne moléculaire. En effet, dans de nombreuses études, l’architecture globale de lamolécule est connue et seulement certains segments non inclus dans les hélices ou les feuillets de lastructure sont potentiellement flexibles. Le premier et le dernier atome de chaque segment doiventrester liés aux éléments fixes de la chaîne.

Les contraintes répulsives permettent de prendre en compte le fait qu’une grande quantité d’éner-gie est nécessaire pour rapprocher deux atomes plus prêt que ne le permet leur rayon de Van derWalls. Les conformations acceptables devront donc être dépourvues de clashs stériques (collisionentre deux atomes représentés par des sphères de rayons égaux aux rayons de Van der Walls deséléments associés).

Deux contraintes attractives ont une influence importante sur l’énergie associée à une confor-mation : les interactions hydrophobes et les liaisons hydrogènes. Elles restreignent le mouvementde certains atomes et impliquent donc des contraintes de distances et d’orientation dans le modèlemécanique.

2.3.2 Modèle géométrique des moléculesLes algorithmes de planification de mouvement pour la biologie moléculaire sont exécutés sur

des modèles géométriques de la molécule étudiée. La structure de ces modèles respecte les principesde modélisation que nous avons introduits dans le chapitre 1.

Les atomes sont représentés par des sphères. Les groupes d’atomes connectés par des liaisonsrigides forment des corps rigides et les articulations rotoïdes entre ces corps permettent de tenircompte des torsions. Un repère cartésien est associé à chaque corps. Les positions et orientationsrelatives des repères consécutifs sont définies par des matrices homogènes de transformation sem-blables à la matrice 1.1. La seule variable est l’angle de torsion.

La figure 2.5 met en évidence le modèle mécanique associé à un acide aminé.La structure secondaire de la molécule sera modélisée grâce à la notion de groupe rigide (un

rigide peut être constitué de plusieurs acides aminés).



Fig. 2.5 – Modèle mécanique d’un acide aminé.

2.4 Algorithmes géométriques dédiés à la modélisation molé-culaire

La démarche développée au LAAS consiste à exploiter le parallélisme existant entre les systèmesmécaniques et les molécules. Elle s’appuie sur une analyse conformationnelle en deux étapes : unpremier traitement géométrique des principales contraintes moléculaires puis une phase de raffine-ment à partir de modèles énergétiques. Nous allons présenter les principes du filtrage géométriquede façon plus détaillée.

2.4.1 Exploration de l’espace de conformationL’exploration conformationnelle met en oeuvre une technique de planification par échantillon-

nage, basée sur une recherche incrémentale type RRT. En effet, les mouvements moléculaires sonten général extrêment contraints du fait de l’encombrement stérique de l’environnement et descontraintes de fermeture associées à la boucle que l’on désire étudier.

Le principe de base de l’algorithme consiste à faire progressivement croître un arbre dont la ra-cine représente la configuration de départ de la molécule (il a déja été abordé dans la section 1.2.3).On cherche alors à connaître la connectivité de l’espace atteignable et à joindre la configuration dedépart qinit à une configuration d’arrivée qbut.

A chaque itération, une configuration est tirée aléatoirement dans l’espace de configuration.Cette configuration permet de déterminer le noeud de l’arbre que l’on tentera d’étendre (choix duplus proche voisin) ainsi que la direction d’exploration. La stratégie d’exploration utilisée vise àfavoriser les régions de l’espace les moins explorées.

Les conformations tirée respectent les contraintes de fermeture associées aux boucles et auxponts hydrogènes (voir 2.4.2). D’autre part, plusieurs tests sont effectués le long du chemin reliantqinit à qbut dans l’espace de configuration : l’absence de collision et l’intégrité de la boucle doiventêtre maintenus.

L’exploration est menée jusqu’à ce que l’arbre RRT parvienne à rejoindre la configuration finale

2.4. Algorithmes géométriques dédiés à la modélisation moléculaire 17

(par exemple, la configuration dans laquelle un ligand aura réussi à s’arrimer au site actif d’uneprotéine). Si la configuration finale n’est pas atteinte au bout d’un certain nombre d’itérationsconséquent, on considère qu’aucune solution n’existe.

2.4.2 Echantillonnage des conformations en présence de bouclesLes conformations satisfaisant des contraintes de fermeture de boucles sont échantillonnées

grâce à une technique intitulée RLG (Random Loop Generator).Selon cette approche, la chaîne fermée associée à la boucle est décomposée en :

• une chaîne passive (6 articulations consécutives),• une chaîne active (les autres articulations de la boucle).

Les variables articulaires de la chaîne active sont successivement échantillonées à l’aide d’unalgorithme géométrique qui cherche à augmenter la chance d’obtenir une solution pour la chaînepassive. A chaque itération, un test de collision est effectué. Une fois que la configuration de lachaîne active est complètement déterminée, la configuration de la chaîne passive est obtenue parrésolution d’un problème de cinématique inverse à 6 degrés de liberté.

2.4.3 Détection de collisionLa performance du mécanisme de détection de collision est essentielle. En effet, théoriquement,

il faudrait tester l’ensemble de toutes les paires d’atomes non liés dans le modèle. Le coût d’un teltest est quadratique.

Un algorithme dédié aux applications de modélisation moléculaire a été développé ([Ruiz 05]) :BioCD. Il prend en compte les auto-collisions et le calcul informatique des distances dans desmodèles comportant un nombre important d’articulations.

Il repose sur des structures de données hiérarchiques qui codent la forme de la protéine à diffé-rents niveaux de détails. Cela permet ainsi de réduire la dimension du système à tester. Le premierniveau se base plutôt sur une vue d’ensemble de la molécule sous forme d’éléments rigides articulésalors que le second s’attache aux collisions internes aux rigides du premier niveau. L’avantage estde pouvoir réaliser des tests de collision de façon efficace tout en ayant aussi la possibilité de mettreà jour les structures de données rapidement.

Chapitre 3

LogicielLes premiers pas de BioMove3D

3.1 BioMove3D : un réel besoinMove3D est un plate forme logicielle permettant de traiter des problèmes de planification de

mouvement pour une large classe de systèmes. Sa généricité s’est avérée avantageuse dans denombreuses applications. Cependant, elle peut aussi constituer un frein à la souplesse et à la facilitéde programmation : cela se vérifie en particulier pour les applications de biologie moléculaire.

3.1.1 Cohabitation de différents formats de données dans Move3DLa description d’un modèle dans Move3D respecte un format précis appelé format P3D. Ce

dernier permet de définir une liste d’obstacles, qui peut être vide, et un système mécanique. Lachaîne cinématique de ce système est décrite séquentiellement par une alternance de corps et d’ar-ticulations. Les algorithmes de planification de mouvement pour la biologie moléculaire implantésdans Move3D utilisent des structures de données renseignées à l’aide de tels fichiers P3D.

D’autre part, dans le domaine de la biologie structurale, la communauté scientifique manipuledepuis longtemps un format de données adapté à la description des macromolécules : le format dela Protein Data Bank. Le logiciel Move3D ne pouvait pas traiter des fichiers sources écrits selonles conventions de ce format particulier.

Bien que le format P3D soit basé sur une syntaxe et une sémantique relativement simples, ilétait inconcevable de créer manuellement les modèles mécaniques associés aux molécules étudiées :les modèles de la Protein Data Bank comportent bien souvent plus de 2500 atomes. Un premiertraducteur indépendant de Move3D avait déjà été mis en place par J. Cortés mais il fallait encoreréaliser plusieurs opérations manuellement (traduction d’une protéine à partir du format PDB,traduction séparée du ligand, adaptation des indices des articulations dans les fichiers P3D . . .).Il semblait donc essentiel de concevoir un module de traduction du format PDB au format P3Dainsi qu’une interface graphique appropriée pour charger aisément des modèles moléculaires sur laplate-forme logicielle Move3D.

20Chapitre 3. Logiciel

Les premiers pas de BioMove3D

3.1.2 Nouvelles structures de données dédiées aux applications moléculairesdans BioMove3D : motivations

Plusieurs améliorations algorithmiques étaient envisagées (chapitre 4). Malheureusement, ellesétaient difficilement applicables aux structures existantes de Move3D. En effet, la complexité etla grande quantité d’information que les structures de Move3D encapsulent défavorisent la perfor-mance des traitements informatiques. Cela est d’autant plus vrai que les algorithmes de planifica-tion de mouvement demandent de fréquentes mises à jour des données.

D’autre part, le degré de flexibilité des boucles et des structures moléculaires en général devaitêtre facilement paramétrables pour les développeurs et pour les chercheurs : cela demandait doncune intervention à la fois sur la structuration du code source (développeurs) et sur l’implémentationdes modèles mécaniques propres à la biologie moléculaire (chercheurs). Une nouvelle interface deprogrammation des applications (API, Application Programming Interface) offrait l’avantage deregrouper les nombreuses opérations mécaniques élémentaires sous la forme d’une boîte à outils defonctionnalités facilement exploitable au cours des futurs développements.

Cette couche logicielle devait aussi offrir la possibilité d’interfacer d’autres applications plusaisément, en particulier celles qui sont destinées au raffinement énergétique (deuxième étape desalgorithmes dédiés à la planification du mouvement moléculaire). Un premier pas dans la concré-tisation de ce projet est présenté dans la section 3.4.

Outre une plus grande modularité, elle devait permettre, à terme, de spécifier des contraintesde mouvement beaucoup plus aisément qu’à présent. Sur Move3D, cette opération se fait encoremanuellement ; elle demande quelquefois une intervention au niveau du code source de l’application.

D’autres avantages apparaissaient en faveur de la conception d’une couche logicielle évoluée ;par exemple, la manipulation des informations biochimiques et mécaniques indépendamment duformat de description du visualisateur graphique pourrait faciliter l’intégration des fonctionnalitésde planification de mouvement aux logiciels de visualisation actuels (VMD, RasMol, PyMol . . .).

Les évolutions décrites précédemment s’inscrivent dans une démarche de migration des appli-cations de Move3D liées à la biologie vers une plate-forme spécifique : BioMove3D.

3.2 Vers une représentation cohérente des molécules

3.2.1 Une molécule selon le format de la Protein Data BankLa Protein Data Bank est un dépôt international de données expérimentales concernant lesmacromolécules biologiques. Elle fournit la description tridimensionnelle de structures protéiques.A ce titre, elle est largement utilisée par la communauté scientifique et l’industrie.

Les archives contiennent :

• une information essentielle : les coordonnées des atomes constituant la molécule, obtenuesgénéralement par analyses cristallographiques,

• d’autres informations : des données supplémentaires sur les structures primaire et secondairede la molécule, des précisions sur les paramétres expérimentaux liés aux techniques de réso-nance magnétiques nucléaires et aux outils d’analyse cristallographique, des citations bibli-ographiques . . .

3.2. Vers une représentation cohérente des molécules 21

L’ensemble de ces informations est accessible via un site internet1 maintenu par le RCSB(Research Collaboratory for Structural Bioinformatics).

Le format des données fournies par la PDB se concrétise en un fichier texte portant l’extension.pdb. Selon les dernières spécifications fournies sur le site internet de la PDB, ce fichier contient unensemble d’informations structuré de façon précise.

Cependant, la plupart des fichiers de la PDB ne présentent pas la totalité des informationsmentionnées ci-dessus. En effet, les données essentielles à la modélisation et la représentation d’unemolécule à l’aide d’un visualisateur classique sont regroupées dans une partie intitulée Coordinatesection. Ce sont précisemment ces informations biochimiques qui sont nécessaires à BioMove3Dpour construire la structure mécanique associée à une molécule.

Ainsi que nous l’avons précisé dans le chapitre précédent (2.1.1), une protéine est constituée d’unenchaînement d’acides aminés caractéristique. Ces derniers jouent le rôle de briques élémentaireset ont une composition atomique déterminée. Pour décrire la structure tridimensionnelle d’unemacromolécule biologique, il faut donc disposer des coordonnées de tous les atomes élémentairesde chacun des acides aminés de la molécule. Le format de la PDB respecte ce principe.

Fig. 3.1 – Extrait d’un fichier de la Protein Data Bank.

Chaque ligne débutant par le mot clé ATOM dans la section Coordinate contient les champssuivants :

1. Le numéro de série de l’atome : il est incrémenté à chaque définition d’un nouvel atome.Il permet d’identifier de façon unique un atome dans la molécule, indépendamment de l’acideaminé ou de la chaîne à laquelle il appartient.

2. Le nom de l’atome : pour les protéines, ce nom est dicté par une syntaxe aux régles rela-tivement précises. Elle respecte les conventions de nommage établies par les biologistes. Enrevanche, lorsque l’on considère un ligand ou une autre molécule (sucre . . . etc.), la nomen-clature utilisée reste relativement lâche et ne semble pas respecter un standard déterminé.

3. Le nom du résidu : de même que précédemment, les noms des résidus sont parfaitement dé-finis pour les protéines : ce sont les noms standards communément utilisés par les biochimisteset les biologistes.

1http ://www.rcsb.org/pdb/



4. L’identifiant de la chaîne peptidique contenant le résidu : il s’agit généralement d’unelettre (A, B). Si la protéine est constituée d’une seule chaîne, ce champ n’est pas renseigné.

5. Le numéro du résidu : il identifie un résidu de façon unique dans la molécule, indépen-damment de sa chaîne d’appartenance éventuelle. Il est incrémenté à chaque définition d’unnouveau résidu.

6. Les coordonnées de l’atome : elles sont au nombre de trois (positions selon les axesorthogonaux x, y, z). L’unité utilisée est l’Angstrom.

3.2.2 Structuration de l’information biochimiqueProtein Structure Format

La Protein Data Bank fournie une description relativement plane des informations biochi-miques. En effet, l’ensemble de la (ou des) molécule(s) décrites par un fichier PDB source apparaità partir du niveau de description le plus bas que l’on puisse envisager : l’atome.

Les structures de données PSF (Protein Structure Format) hiérarchisent les informationsen plusieurs niveaux cohérents avec les modèles moléculaires actuels 3.2.

Un atome regroupe l’ensemble des informations données par une ligne du fichier PDB source.Il comporte aussi des informations supplémentaires : sa connectivité est représentée par une

liste de références aux atomes auxquels il est associé par des liaisons covalentes dans la réalité.

Fig. 3.2 – Diagramme de classes simplifié du format PSF Protein Structure Format .


Cette dernière caractéristique donne ainsi à l’ensemble des atomes une structure de graphe,particulièrement efficace lorsque l’on désire parcourir une molécule atome par atome. Nous exploi-terons pleinement cette structure lorsque nous reconstituerons la chaîne cinématique associée à unligand.

Un résidu ou acide aminé est défini à partir d’un ensemble d’atomes fonction de sa nature (sonnom dans les fichiers de la PDB).

Un atome peut être référencé au sein d’un acide aminé :

• soit en tant qu’atome de la chaîne principale,• soit en tant qu’atome de la chaîne latérale.

Les différents atomes qui constituent un acide aminé donné sont précisément définis (voir la défi-nition des protéines 2.1.1). Le canevas de constitution d’un acide aminé est donc spécifié à l’aided’une énumération des atomes qui le constituent. Nous verrons cependant que certains atomespeuvent être présents de façon optionnelle. Cette difficulté technique a été surpassée au niveaudes structures de données par l’élaboration de tableaux non contraints ; les tableaux d’atomes deschaînes principale et latérale d’un acide aminé présentent donc une partie fixe, nécéssairementcomplétée, et une partie variable, destinée à recevoir les atomes optionnels. L’ordre des atomesréférencés dans la partie fixe des tableaux a aussi son importance (contrainte imposée par BioCD).

Pour un même acide aminé, nous avons défini deux canevas de base :

• Un canevas sans atomes d’hydrogène pour être en mesure de lire les fichiers issus directementde la PDB,• Un canevas avec atomes d’hydrogène.

Enfin, il est possible d’accéder séquentiellement aux acides aminés précédent et suivant dans lamolécule grâce à une structure de liste doublement chaînée.

Une chaîne peptidique représente un ensemble d’acides aminés. Nous avons intégré la notionde sous-chaîne (identifiée par un numéro) au sein même d’une chaîne peptidique. En effet, il estquelquefois difficile de caractériser certains segments protéiques expérimentalement. Cela se traduitalors par une discontinuité des informations dans le fichier PDB (saut dans le numéro de séquencedes acides aminés). Un sous-chaîne, telle que nous l’avons définie, correspond à la plus grandeportion intègre d’une chaîne peptidique.

Une molécule peut être soit une protéine, soit un ligand. A terme, il pourrait s’agir aussi d’unacide ribonucléique. Le type de molécule détermine la structure de données sous-jacente qui lareprésente.

• Pour une protéine, les atomes sont hiérarchisés et regroupés au sein d’acides aminés eux-mêmeinclus dans des chaînes peptidiques.• Pour un ligand, seul le graphe des atomes liés synthétise les informations biochimiques.

On associe à chaque molécule le nom du fichier source PDB dans lequel elle est définie.

Un environnement moléculaire regroupe toutes les molécules que l’utilisateur est amené à ma-nipuler à un moment donné.



D’une manière générale , toutes les structures mises en places ont été conçues de telle façon qu’ilsoit possible de parcourir la hiérarchie des informations aisément. Ainsi, il est toujours possibled’accéder à un composé (un acide aminé par exemple) à partir de son composant (un atome de cemême acide aminé) et vice-versa.

Ce découpage structurant n’intervient pas seulement sur le plan des informations d’ordre biochi-mique. Chaque structure décrite précédemment est associée à son équivalent sur le plan mécanique.

3.2.3 Structuration mécanique des chaînes moléculairesArticulated Molecular Chain

La structure mécanique associée à une molécule peut être perçue selon différents niveaux dedétails.

Conformément aux modèles issus du domaine de la robotique, il est possible de définir la chaînecinématique associée à une macromolécule biologique comme un enchaînement de rigides connectésentre eux par des articulations.

Cependant, l’étude de la flexibilités des boucles demande un niveau de représentation supplé-mentaire : la notion de boucle, de segments rigides ou mobiles doivent être clairement identifiablesau travers des structures de données manipulées. A cela s’ajoute une nouvelle perspective : pouvoirreprésenter un environnement moléculaire et le mouvement relatif de plusieurs molécules.

Les nouvelles structure de données AMC (Articulated Molecular Chain) répondent à cesbesoins.

Un rigide regroupe un ensemble d’atomes connectés par des liaisons rigides : les atomes d’unmême rigide ne sont pas en mouvement les uns par rapport aux autres. En revanche, le mouvementd’un rigide provoque le déplacement de l’ensemble des atomes qu’il inclut, sans modifier leurspositions relatives.

La succession des rigides constitutifs du système forme une chaîne cinématique qu’il est pos-sible de parcourir aisément (implémentation sous forme de liste à cellules doublement chainées).Plusieurs transformations permettent de naviguer dans la chaîne cinématique et de mettre à jourles positions des rigides et des atomes sous-jacents. Ce mécanisme sera explicité dans la partie3.3.2.

Une articulation référence les informations relatives à un vecteur q de variables articulaires.Chacune de ces variables articulaires est intégrée dans la conformation de la molécule.

Il peut s’agir :

• d’une articulation rotoïde : elle est alors spécifiée par la position des quatre atomes définissantson axe de rotation (les quatre atomes du dièdre d’articulation). Une unique variable articu-laire caractérise l’articulation : il s’agit de la valeur de l’angle de rotation. Les articulationsφ, ψ et ω de la chaîne principale d’un acide aminé sont de ce type.• d’une articulation type freeflying : dans ce cas, la position et l’orientation du repère attaché

à cette articulation sont parfaitement définies par un vecteur à six composantes (trois pourla position, trois pour l’orientation). Ce type d’articulation permet de représenter un repèreabsolu dans l’environnement moléculaire. Il est aussi particulièrement utile pour caractériserla position et l’orientation d’une molécule ou d’un fragment moléculaire libre par rapport àune autre molécule.


Fig. 3.3 – Diagramme de classes simplifié du format AMC Articulated Molecular Chain.

Les valeurs permises pour ces différentes variables sont spécifiées par des intervalles de définitionéventuellement disjoints.

Une sous-chaîne permet de représenter un sous-ensemble de la chaîne cinématique complèted’une molécule. Il s’agit d’un regroupement d’acides aminés dont on désire caractériser le mouve-ment dans l’ensemble de la chaîne moléculaire. La figure 3.4 montre que la boucle d’une moléculepeut être considérée comme une sous-chaîne flexible rattachée à deux autres sous-chaînes. Oncomprend ainsi l’utilité d’une telle structure de données : il devient possible de définir des sous-ensembles mécaniques correspondants aux boucles et aux segments fixes de la molécule.

Au sein d’une sous-chaîne, on distingue une unique chaîne principale : il s’agit de l’enchaine-ment de rigides connectant le premier acide aminé de la sous-chaîne au dernier. Il est possible deparcourir cette sous-chaîne dans les deux sens (à partir du premier ou du dernier rigide, voir 3.3).

Enfin, les chaînes latérales de la sous-chaîne viennent se connecter à la chaîne principale : ilsera possible de bloquer ou non leur mouvement et d’étudier ainsi leur inflence dans les interactionsmoléculaires.

Les contraintes n’ont pas encore été totalement implémentées. Elles devraient permettre de dé-finir des relations entre les éléments mécaniques sur deux plans :



Sous-chaîne très flexible de la boucle

Sous-chaînes peu flexibles autour de la

boucle

Rigides de la chaîne principale des acides

aminés articulés de la boucle

Sous-chaînes selon le format Articulated Moclecular Chain

Fig. 3.4 – Une boucle protéique vue comme une sous-chaîne flexible.

• le degré d’articulation des chaînes latérales et les interactions entre sous-chaînes au sein d’unemême molécule,• les interactions entre différentes molécules au sein d’un même environnement.

Finalement, la hiérarchie des structures mécaniques intervenant dans un environnement molé-culaire peut donc être représentée schématiquement selon la figure 3.5.


Fig. 3.5 – Synthèse des relations mécaniques liant les objets d’un environnement moléculaire.



3.3 Elaboration des informations

Le développement de la nouvelle interface de programmation a été réalisé selon deux approches.La première répondait à un besoin à court terme : être en mesure de traduire un fichier au for-mat PDB en une structure de données P3D directement exploitable par Move3D. L’autre visaità fournir un ensemble de fonctionnalités facilement exploitables pour les futurs développementsalgorithmiques du nouveau logiciel BioMove3D.

Ces deux approches sont illustrées dans la figure 3.6.

Fig. 3.6 – Des développements réalisés sur deux plans : l’intégration du traducteurdans Move3D et l’implémentation d’une API dédiée à la biologie moléculaire au seinde BioMove3D.

3.3.1 Première intégration dans Move 3D : le traducteurLa traduction d’un fichier au format PDB en structures de données exploitables par Move3D se

fait en deux étapes. Tout d’abord, l’ensemble des informations du fichier PDB source est analyséet mémorisé dans des structures de données PSF. Ensuite, les structures PSF extraites servent desupport pour élaborer le système mécanique selon le format P3D.

Dorénavant, au lancement de Move3D, l’utilisateur peut lire deux types de fichiers sources :

• Un fichier P3D,• Un ou plusieurs fichier(s) PDB,

La définition d’un ligand peut être associée à sa protéine cible dans un même fichier PDB ouau contraire être définie dans un fichier distinct.

Pour pouvoir construire convenablement la structure mécanique P3D, les informations bio-chimiques encapsulées dans les structures PSF ne suffisaient pas. Il fallait offrir à l’utilisateur lapossibilité de spécifier le degré d’articulation du système mécanique :

3.3. Elaboration des informations 29

• Pour les protéines, l’utilisateur doit indiquer les résidus qu’il veut articuler ainsi que la chaîneà articuler (principale et/ou latérale),• Pour les ligands, il doit déterminer les dièdres définissant les axes d’articulation.

Il a donc fallu définir un format adapté à la représentation de ces deux types d’information ainsiqu’une interface d’interaction adéquate.

Fig. 3.7 – A gauche, la fenêtre de définition des dièdres pour un ligand ; à droite, l’interface permettantde définir les acides aminés à articuler dans une protéine.

Désormais, après chargement du (des) fichier(s) source(s), il est possible de préciser les informa-tions nécessaires à l’élaboration de la structure mécanique articulée grâce à une interface fenêtrée.A tout moment, l’utilisateur a la possibilité d’enregistrer ses paramètres dans un fichier (fichierAAA pour Articulated Amino Acid et fichier JDS pour Joint Dihedral Specification). Il pourra ainsiles réutiliser lors d’une prochaine session de travail.

Les structures P3D de Move3D sont enfin renseignées grâce aux structures PSF et aux para-mètres d’articulation définis par l’utilisateur. Cette opération est transparente et ne génère pas defichier P3D superflu.

3.3.2 Nouvelles fonctions d’interfaceIl est possible d’envisager une molécule selon deux points de vue :

• selon ses caractéristiques biochimiques (format PSF, voir 3.2.2),• selon ses caractéristiques mécaniques (format AMC, voir 3.2.3),



Le nouveau logiciel BioMove3D est fondé sur l’intégration de ces deux formats de données.Chaque entité des structures PSF est liée à un équivalent mécanique dans les strutures AMC 2.

Nous avons mis en place des fonctions d’interface utilisant les fonctions d’accès propres auformat PSF et au format AMC pour générer la structure mécanique d’une protéine ou d’un ligand.

L’élaboration des structures mécaniques associées aux protéines fait intervenir plusieurs opé-rations élémentaires.

L’utilisateur ou le développeur doit indiquer quelles seront les différentes sous-chaînes méca-niques du système (en donnant par exemple les numéros de séquence des acides aminés extrêmesde chacune des futures sous-chaînes).

Chaque sous-chaîne mécanique est construite progressivement en parcourant la chaîne molécu-laire définie dans le format PSF. Lorsque l’on atteind un acide aminé débutant une sous-chaînedéfinie comme flexible, chaque acide aminé qui le suit est découpé en un ensemble de rigides liésentre eux par des articulations rotoïdes. Notons que plusieurs niveaux d’articulation peuvent êtrespécifiés : articulation de la chaîne principale des acides aminés et/ou articulation des chaîneslatérales.

Fig. 3.8 – Principe de construction des structures mécaniques appliqué à deux acidesaminés. Les chaînes principales constituent un unique rigide, les chaînes latérales sontentièrement articulées.

Chaque articulation est déterminée par un dièdre formé par les quatre atomes entourant l’axede rotation. La valeur de la variable articulaire associée à une rotation est calculée à partir despositions de ces quatre atomes, données dans les structures PSF (calcul illustré sur la figure 3.9).

2Notons d’ailleurs que de nombeuses classes portent les mêmes noms dans les diagrammes de classes respectifs,PSF (3.2) et AMC (3.3).


Fig. 3.9 – Calcul de l’angle de torsion à partir d’un dièdre.

Pour chaque acide aminé, l’utilisateur des fonctions d’interface n’a pas à spécifier les différentsdièdres. En effet, la composition et la structure atomique des acides aminés suit un canevas précis :les dièdres étaient donc connus a priori. Un gros effort a été fourni pour masquer tous les calculsmécaniques et géométriques en les intégrant au sein même des fontions d’interface. Concrètement,cela a demandé de développer une fonction de calcul par acide aminé.

Une fois que la totalité de la chaîne moléculaire a été parcourue, plusieurs fonctions associéesaux structures AMC mettent à jour les positions relatives des atomes au sein de chaque rigide.C’est également au cours de cette dernière étape que les matrices de transformation homogènepermettant de parcourir la chaîne cinématique sont calculées. Chaque rigide se voit associé àquatre transformations (figure 3.10) :

• Deux d’entre elles sont directement liées à la géométrie intrinsèque du système mécanique(nT0 et pT0); elles resteront constantes quelques soient les changements de conformation dela molécule.

• Les deux autres (Tq et nTq) dépendent de la configuration du système à un instant donné.

Cette distinction pourrait améliorer les performances des algorithmes demandant un grandnombre de calculs géométriques avec des configurations variables. De plus, parmi les quatre ma-trices, certaines font référence au repère suivant dans la chaîne cinématique (elle sont préfixées parun n pour next) alors que d’autres sont établies par rapport au repère précédent (elles sont préfixéepar un p pour previous) ; cela laisse donc la possibilité de parcourir la chaîne cinématique dans lesdeux sens.



Fig. 3.10 – Transformations homogènes associées à un rigide. Elles permettent de parcourir la chaînecinématique dans les deux sens.


La structure mécanique d’un ligand est générée selon une procédure différente. Contrairementaux protéines, elle n’est pas déterminée à priori. La construction de la chaîne cinématique de rigidesassociée repose donc sur les dièdres spécifiés par l’utilisateur.

La chaîne moléculaire correspondant au ligand, de structure quelconque, va être décomposéeen un arbre sans cycle.

Nous exploitons la connectivité des atomes de la molécule accessible à partir des structures dedonnées PSF et construisons un arbre couvrant à partir de ce graphe de connectivité. Il fallaitporter une attention particulière aux cycles que pouvait comporter le ligand (présence de noyauxbenzéniques par exemple). L’algorithme utilisé est présenté ci-après (3.1).

Algorithme 3.1 : Construire_Rigides_Depuis_Racine

Entrées : La molécule M, l’atome racine d’exploration Aracine, la listes des dièdres DiedresSorties : La molécule à jourM, la liste des racines à explorer AtomesRacines

Creer_Rigide(Rcourant)Ajouter_Atome(Rcourant, Aracine)

AtomesRacines ⇐ Aracine

AtomesAExplorer ⇐ Aracine

AtomesLies ⇐ ∅début

tant que AtomesAExplorer 6= ∅ fairepour chaque Acourant ∈ AtomesAExplorer faire

AtomesLies ⇐ Get_Atomes_Lies(Acourant)Rcourant ← Get_Rigide_Parent(Acourant)pour chaque Alie ∈ AtomesLies faire

si Est_Dans_un_Rigide(Alie) alorssi Sont_Dans_Articulation(Diedres, Acourant, Alie) alors

Creer_Rigide(Rlie)Ajouter_Atome(Rlie, Alie)Set_Rigide_Suivant(Rcourant, Rlie)Set_Rigide_Precedent(Rlie, Rcourant)AtomesRacines ⇐ Alie

sinonAjouter_Atome(Rcourant,Alie)AtomesAExplorer ⇐ Alie

sinonRlie ← Get_Atomes_Lies(Alie)si Sont_Connectes(Rlie, Rcourant) alors Lever_Erreur()

fin

Le parcours du graphe de connectivité des structures PSF est réalisé en largeur d’abord. Leprincipe consiste à choisir un atome racine de la chaîne (dans la liste des racines AtomesRacines),à le placer dans un premier rigide (Rcourant) et à explorer ses liaisons covalentes (liste d’atomesliés AtomesLies).



• Si la liaison entre l’atome courant (Acourant) et l’atome lié (Alie) est l’axe de rotation d’undièdre, un nouveau rigide est créé ; l’atome lié est défini comme prochain atome racine (il estinséré dans la liste AtomesLies).• Dans le cas où la liaison ne participe pas à un dièdre, l’atome lié est inséré dans le rigide

courant (Rcourant) et l’exploration sera poursuivie à partir de cet atome.• Enfin, l’atome lié peut être déjà contenu dans un rigide ; pour éviter toute erreur liée à la

présence d’un cycle dans la chaîne moléculaire, un test permet de détecter si le rigide courantet le rigide de l’atome lié sont déjà connectés : une erreur est levée si cela est le cas (fonctionLever_Erreur).

Une fois que tous les atomes de la liste des racines ont été traités, la structure mécanique duligand est complète.

L’ensembles des fonctions d’accès et de mise à jour des structures de données PSF et AMCconstitue également un apport important au niveau de l’interface de programmation. Pour chaquestructure (atome, acide aminé, chaîne, molécule, rigide, articulation, . . .), des accesseurs et des mo-dificateurs permettent de mettre à jour les informations biochimiques et mécaniques. Ces fonctionsont été implémentées avec le soucis de faciliter les futurs développements : des noms évocateurset cohérents on été choisis pour chacune d’entre elles. Elles pourront ainsi être interfacées avecd’autres modules applicatifs dans les futures versions BioMove3D.

3.4 Le module énergétique

3.4.1 Intérêt d’une approche énergétiqueLes conformations obtenues par filtrage géométrique dans BioMove3D ne sont pas forcément

rigoureusement valides d’un point de vue énergétique. Ce filtrage permet de rejeter beaucoupde conformations incorrectes mais nécessitait d’être combiné avec des calculs énergétiques pouraméliorer la finesse de la prédictivité. Une méthode a été récemment développée sur BioMove3D.Elle a été mise en oeuvre à l’aide des fonctions de calcul énergétique du logiciel AMBER (AssistedModel Building with Energy Refinement).

AMBER permet d’évaluer l’énergie associée à la conformation donnée d’une molécule par rap-port à un champ de forces défini. En effet, l’énergie totale d’une molécule dépend des positionsrelatives de ses atomes. Elle fait intervenir différentes contributions énergétiques au sein d’uneéquation générale :

• des termes associés aux liaisons atomiques (énergies de tension, de flexion, de torsion),• des termes associés aux interactions entre atomes non liés (interactions de Van der Waals,

interactions électrostatiques . . . ).

En calculant l’énergie associée à une conformation, on peut évaluer de manière plus fine qu’avecles fonctions d’ordre géométrique la possibilité qu’elle a d’exister effectivement dans la nature.

3.4.2 Mise en oeuvre du module énergétique au sein de BioMove3DNous avons vu précédemment que le calcul énergétique nécessitait un accès aisé aux informations

biochimiques caractérisant la (ou les) molécule(s) étudiée(s).

3.4. Le module énergétique 35

J’ai été amené à participer à l’intégration de l’application AMBER au sein de BioMove3D. Eneffet, à terme, le module énergétique devrait exploiter pleinement le format de données hiérarchiséPSF pour réaliser ses calculs. Les principales informations nécessaires concernent l’atome et l’acideaminé dans lequel il se situe, en particulier :

• la nature de l’atome,• la nature de l’acide aminé,• les positions des atomes,• la connectivité des atomes.

L’interface de programmation développée offre des fonctions d’accès simples à manipuler etexplicites pour les futurs développeurs qui travailleront sur l’intégration de l’application AMBER.Elle permet surtout de récupérer aisément les informations précises que nous avons détaillées ci-dessus à partir de la struture de données associée à la molécule étudiée.

Il a fallu cependant faire face à plusieurs difficultés techniques. Les fichiers sources issus dela PDB ne spécifient généralement que les atomes lourds de chaque acide aminés. Pourtant, lesatomes d’hydrogène ont une influence (par action électrostatique) sur les mouvements de certainssegments moléculaires : les ponts qu’ils forment avec d’autres atomes sont à l’origine de contraintesnon négligeables. Les logiciels de simulation de champs de force ajoutent ces atomes d’hydrogènemanquants aux modèles moléculaire issus de la PDB. Or, en fonction du modèle énergétique utilisé,la description d’un même atome d’hydrogène varie.

Ainsi, nous avons été confronté à des descriptions issues d’un même fichier PDB mais complétéespar CHARMM3 et AMBER de façon différente :

• Les noms des atomes d’hydrogène ne suivaient pas les mêmes conventions,• Un même acide aminé pouvait se déclinait en plusieurs variantes dans l’application AMBER;

le nom des variantes était alors totalement “exotique” par rapport aux conventions adoptéesdans la PDB.• L’ordre des atomes était modifié par le programme AMBER.

Cela a eu des conséquences non néligeables sur le travail fourni pour intégrer le module éner-gétique dans BioMove3D. La gestion des modifications d’ordre opérée par AMBER a notammentfait l’objet de développements spécifiques au niveau de BioMove3D. Il est désormais possible degénérer un modèle mécanique et de mener en parallèle des calculs énergétiques à partir d’un fichierPDB respectant indifféremment les conventions AMBER ou les conventions CHARMM.

3CHARMM est un second logiciel de modélisation moléculaire permettant de réaliser des calculs d’énergie.

Chapitre 4

PerspectivesAméliorations algorithmiques

4.1 L’échantillonnageLorsqu’une molécule comporte une ou plusieurs boucles, le filtrage géométrique des configura-

tions moléculaires acceptables repose en grande partie sur l’algorithme RLG. Des améliorationssont envisagées sur ce plan.

Il s’agirait de généraliser les algorithmes existants à partir des nouvelles structures de donnéesAMC développées au cours de mon stage. En effet, nous avons vu dans le chapitre précédent (cha-pitre 3) que ces structures facilitaient le parcours de la chaîne cinématique du système mécanique.Aujourd’hui, l’ensemble des algorithmes de planification de mouvement pour la modélisation molé-culaire sont encore implantés au sein de Move3D et utilisent le format P3D. En conséquence, de parleur conception, les techniques de recherche conformationnelle actuelles ont tendance à favoriser lamobilité de certains segments au dépend d’autres dans les boucles protéiques.

Pour remédier à ce problème, il faudrait développer un algorithme plus élaboré qui permettraitde produire une distribution homogène des configurations acceptables. Concrètement, cet algo-rithme interviendrait au niveau de la décomposition en chaîne active et passive des boucles (voir2.4.2 pour plus de précision sur cette approche). Il s’agirait de jouer sur le placement de la chaînepassive lors de l’échantillonnage.

4.2 Boucles multiplesLes algorithmes actuels traitent chaque boucle séparément. Cette particularité peut être une

limite lorsque plusieurs segments flexibles partagent le même espace (boucles hypervariables desanticorps par exemple).

A titre d’exemple, nous donnons ci-dessous la représentation de la surface d’une protéine avantet après l’arrimage d’un ligand dans son site actif (figure 4.1). La cavité catalytique de cetteprotéine est entourée d’un ensemble de boucles ; leurs mouvements modifient la topologie de lacavité catalytique à tel point que la site d’arrimage ne semble pas exister en l’absence de ligand(figure de gauche).

38Chapitre 4. Perspectives

Améliorations algorithmiques

Fig. 4.1 – Une protéine dont la topologie est très variable ; en cause : de mul-tiples boucles flexibles.

Il est très difficile d’identifier les mouvements de boucles qui permettent de laisser un passageau ligand avec les algorithmes actuels.Il faudrait donc développer une méthode considérant lesmouvements coordonnés d’un ensemble de boucles.

4.3 Exploration combinée boucles/ligandsDe façon similaire au problème soulevé dans la partie précédente, jusqu’à présent, la mobilité

des boucles protéiques et l’accessibilité d’un ligand vis-à-vis du site actif ont été étudiées indépen-damment.

Désormais, l’objectif est de combiner ces deux approches en une seule. En ce sens, il seraitintéressant d’identifier les segments éventuellement flexibles de la protéine et de prendre en compteleurs mouvements pour calculer le chemin d’accès du ligand.

Conclusion

La problématique autour de laquelle s’articule le travail réalisé au LAAS dans le domaine dela planification de mouvement pour la modélisation moléculaire sous-tend un enjeu scientifique detaille. L’expérience du groupe RIA en matière de planification de mouvement a permis de dévelop-per de premiers outils de modélisation efficaces. J’ai éprouvé beaucoup de plaisir en participant àces travaux.

Durant cinq mois, j’ai conçu et intégré dans la plateforme générique de planification Move3Ddu groupe RIA un niveau supplémentaire de modélisation dédié à la représentation de macromolé-cules biologiques sous forme de chaînes cinématiques articulées. Cette étape a représenté un effortimportant d’apprentissage du logiciel Move3D, l’acquisition de connaissances de base en biolo-gie structurale et modélisation de mécanismes, ainsi qu’un travail de programmation relativementconséquent.

Cet initiation à la recherche représente pour moi une expérience enrichissante. Le stage de Mas-ter a été l’occasion de mettre en œuvre plusieurs notions techniques acquises en spécialité Génieinformatique à l’INSA (processus de développement, conception, programmation en langage C . . .).Mes acquis n’ont pas été les seuls à être mis à l’épreuve : les problèmes abordés ont aussi nécessitéun effort d’adaptation important. En effet, la planification de mouvement pour la modélisationmoléculaire se situe à la croisée de plusieurs grandes disciplines scientifiques (la biochimie, l’infor-matique, la mécanique, la robotique, la physique . . .) : cela entretient son originalité, sa richessemais aussi sa complexité.

En quatrième année, un projet tutoré m’avait permis de repérer quelques problématiques ac-tuelles de la robotique et avait excité ma curiosité ; il y a un an, je réalisais un stage technique dequatrième année dans un laboratoire d’étude des systèmes informatiques : je découvrais donc ledomaine de la recherche. Aujourd’hui, grâce à ce stage, j’ai enfin réussi à mettre en commun cesdeux aspects.

Les six mois que je viens de passer au LAAS m’ont donné l’opportunité d’appréhender lequotidien des chercheurs. La richesse des réflexions et des échanges qui animent le laboratoire,l’excitation que l’on éprouve quand un nouvel algorithme fonctionne, la joie que l’on savourelorsqu’il s’agit d’expliquer l’objet de son travail à son entourage : ces petits plaisirs sont bien réels.Pourtant, travailler dans un tel contexte demande aussi de la pugnacité et un certain recul.

J’ai également constaté que la recherche demandait beaucoup d’humilité ; la planification demouvement a fait l’objet de nombreux développements théoriques relativement complexes : vouloircomprendre les concepts de ce domaine dans tous leurs moindres détails aurait été un objectifirréaliste.

40 Conclusion

Enfin, cette participation à un projet de recherche m’a appris à envisager les choses selondifférents niveaux de précision, qu’il s’agisse de comprendre une approche indépendamment de sonimplémentation ou qu’il soit nécessaire de reformuler un travail relativement technique dans uncontexte plus général.

Ce stage m’aura apporté des connaissances techniques en informatique, des notions dans d’autresdomaines scientifiques ainsi qu’une capacité à prendre du recul par rapport au travail que je fournis.

Il y a un an, la possibilité de participer aux travaux de Juan Cortés et Thierry Siméon appa-raissait au premier rang de mes motivations. Aujourd’hui, il s’agit d’une formidable expérience.Cela demeurera donc un très bon souvenir.

Références bibliographiques

[Craig 89] J.J. Craig. Introduction to robotics : Mechanics and control. Addison-Wesley, 1989.

[Cortés 04a] J. Cortés, T. Siméon. Sampling-Based Motion Planning under Kinematic Loop-Closure Constraints. Proc. WAFR, 2004.

[Cortés 04b] J. Cortés, T. Siméon, M. Remaud-Siméon, V. Tran. Geometrical Algorithms forthe Conformational Analysis of Long Protein Loops. Journal of Computational Che-mistry, 25, 956-967, 2004.

[Cortés 05] J. Cortés, T. Siméon, V. Ruiz de Angulo, D. Guieysse, M. Remaud-Siméon, V. Tran.A Path Planning Approach for Computing Large-Amplitude Motions of Flexible Mo-lecules. International conference on Intelligent Systems for Molecular Biology, 2005.

[Kavraki 96] L.E. Kavraki, P. Svestka, J.-C. Latombe & M.H. Overmars. Probabilistic Roadmapsfor Path Planning in High-Dimensional Configuration Spaces. IEEE Transactions onRobotics and Automation, vol. 12(4), pages 566–580, 1996.

[Kuffner 00] J.J. Kuffner & S.M. LaValle. RRT-Connect : An Efficient Approach to Single-QueryPath Planning. Proc. IEEE Int. Conf. on Robotics and Automation, pages 995–1001,2000.

[Latombe 91] J.-C. Latombe. Robot motion planning. Kluwer Academic Publishers, 1991.

[LaValle 01c] S.M. LaValle & J.J. Kuffner. Rapidly-Exploring Random Trees : Progress andProspects. In B.R. Donald, K.M. Lynch & D. Rus, editors, Algorithmic and Compu-tational Robotics : New Directions (WAFR2000), pages 293–308. A.K. Peters, 2001.

[Lozano-Pérez 83] T. Lozano-Pérez. Spatial Planning : A Configuration Space Approach. IEEETransactions on Computers, vol. 32(2), pages 108–120, 1983.

[Ruiz 05] V. Ruiz De Angulo, J. Cortés, T. Siméon BioCD : An efficient Algorithm for Self-Detection and Distance Computation between Highly Articulated Molecular Models.Robotics : Science and Systems, 2005.

RésuméL’étude des interactions entre biomolécules représente aujourd’hui un enjeu considérable. Ces

dernières années, les outils de modélisation ont permis de réaliser des prédictions très pertinentes.Malheureusement, les méthodes employées présentent des limitations qui empêchent de prendre encompte la flexibilité des molécules d’une manière générale.

Une approche originale mise en oeuvre récemment au Laboratoire d’Analyse et d’Architecturedes Systèmes consiste à modéliser les molécules comme des systèmes mécaniques articulés et àanalyser leurs mouvements au travers des algorithmes de robotique. Actuellement, elle s’appuiesur une plate-forme logicielle générique de planification de mouvement : Move3D.

Dans ce cadre, mon stage d’initiation à la recherche répond à plusieurs objectifs. Tout d’abord,il s’agit de comprendre les principes de base de la planification de mouvement et les spécificités del’agorithmique du mouvement moléculaire.

Cette approche théorique est mise à profit sur le plan pratique à l’occasion du développementd’une nouvelle application logicielle de planification de mouvement dédiée à la biologie moléculaire :BioMove3D . D’une part, de nouvelles structures de données sont conçues et implémentées pourrépondre aux difficultés posées par l’analyse du mouvement des molécules ; elles visent à unemeilleure intégration des informations biochimiques et des informations mécaniques nécessaires àla modélisation. D’autres part, un nouveaux module de calcul énergétique permet de raffiner lesprédictions de mouvements obtenues géométriquement. A terme, il devrait utiliser les nouvellesstructures de données.

Ainsi, l’ensemble des développements décrits précédemment permettent d’envisager des amé-liorations algorithmiques importantes : l’étude des mouvements de structures moléculaires pluscomplexes deviendrait alors possible.

Documents

STAGE DE MASTER RECHERCHE - LAAS-CNRShomepages.laas.fr/nic/AMoRo/publi/RapportStageBrice.pdfUne fois ces bases établies, le problème consiste à explorer un espace dans lequel les