Upload
abelle-boisseau
View
104
Download
0
Embed Size (px)
Citation preview
Soutenance de thèseBenjamin Parent
Directeurs : Bernard Vandenbunder Jean-Pierre Richard
29 octobre 2007
Algorithmes d’optimisationet d’analyse des problèmes multidimensionnels
non linéairesen Biologie et Biophysique
Plan de la présentation
0. Introduction
1. Échantillonnage conformationnel
2. Modélisation en Biologie systémique
3. Conclusion
3/53
Objectifs de la thèse
Appliquer les savoir-faire de l’Automatique à des
problèmes issus de la Biologie et de la Biochimie
dans la cellule, tout repose
sur des interactions moléculaires…
Étudier les interactions moléculaires
À l’échelle des molécules individuelles
Prédiction dans les cas « simples »
Aide à l’interprétation des expériences
Leur impact à l’échelle d’un module fonctionnel de la
cellule
IntroductionModélisation moléculaireBiologie systémiqueConclusion
4/53
Contexte humain
LIFL – ANR GRID(Info
Fondamentale)
Partie Modélisation
Glycobiologie
IRI
+ IBL
Enseignements
ISENLAGIS (Automatique,
G. Info et Signal)
PhLAM(physique
non-linéaire)
LIFL(calcul formel)
(multi-agents
)
Observatoire de Banyuls –
ANR
Math
Auto
IntroductionModélisation moléculaireBiologie systémiqueConclusion
Plan de la présentation
0. Introduction
1. Échantillonnage conformationnel
2. Modélisation en Biologie systémique
3. Conclusion
Échantillonnage conformationnel
Problématique et codage
Algorithme génétique
Hybridations
Méta optimisation
Parallélisation
7/53
Vers une estimation des affinités entre cibles moléculaires (docking)
Nécessité de décrire la flexibilité de chaque agent : exercice de prédiction de la géométrie
des ligands
des sites actifs
(10 à 1000 atomes)
Introduction
Modélisation moléculaireBiologie systémiqueConclusion
Problématique et codage
8/53
Stabilité donnée par les niveaux d’énergie
E estimée sur la base d’un champ de forcesHagler et al. [1974]
Tk
EEEnergyofconformer
B
exp~PrBoltzmann :
Introduction
Modélisation moléculaireBiologie systémiqueConclusion
Problématique et codage
Conformationsadoptées en
solution
Minima de lafonctionénergie
=
9/53
Le niveau de représentation d’un domaine est aussi fonction de sa largeur (facteur entropique)
Introduction
Modélisation moléculaireBiologie systémiqueConclusion
Problématique et codage
degré de liberté
énergie
10/53
La flexibilité des molécules repose
essentiellement sur la libre rotation autour
des liaisons inter atomiques
Introduction
Modélisation moléculaireBiologie systémiqueConclusion
Problématique et codage
11/53
12/53
Que doit faire l’algorithme ?
Explorer l’espace des géométries pour identifier les
conformations stables
Décrire les niveaux de peuplement des minima pertinents
Idéal : reconstruire la densité de probabilité sur l’espace
de phases
Comparaisons possibles avec les expériences
Introduction
Modélisation moléculaireBiologie systémiqueConclusion
Problématique et codage
AlgorithmeFichier
moléculaireinitial
Différentesconformationsmoléculaires
13/53
Validation des résultats avec des molécules dont la structure est connue expérimentalement
Domaine WW de
PIN
Filippine
Tryp. ZIP
mini -turn
Cyclo-dextrine
Tryp. Cage
Introduction
Modélisation moléculaireBiologie systémiqueConclusion
Problématique et codage
14/53
Problème mathématique de minimisation de fonction
Particularités :Très grandes dimensions (1…200 degrés de liberté)
Fortement multimodal (donc non linéaire)
Recherche de tous les minima utiles
LittératureMolécules de petites tailles Vengadesan [2003]
Grandes molécules, modèle simplifié
Dynamique moléculaire Roitberg [2007]
Introduction
Modélisation moléculaireBiologie systémiqueConclusion
Problématique et codage
Échantillonnage conformationnel
Problématique et codage
Algorithme génétique
Hybridations
Méta optimisation
Parallélisation
16/53
Choix d’une stratégie : Holland [1975]
les algorithmes génétiques (AG)
+ forte exploration de l’espace
+ population de solutions
+ concept d’héritage
+ modularité et adaptabilité
– consommateurs de ressources
– visitent les régions aberrantes
– stochastiques (mauvaise reproductibilité)
Algorithme génétiquesIntroduction
Modélisation moléculaireBiologie systémiqueConclusion
17/53
AG : principes
Solutions=
« chromosomes »
Population de solutions :
18/53
AG : principes
Évolution : opérateurs de croisement
… et de mutation
… n…i+1i
…’
n…
’i+
1
’i
’
’
parent1 :
parent2 :
… n…i+1imuté :
…’
n
’i+1i…
… ni+1’i…’
’
fils1 :
fils2 :
… ni+1’i…mutant :
19/53
AG : principes
population intermédiaire...
n
... n
... n
... n
... n
... n
... n
... n
aléatoire
... n
... n
... n
... n
population initiale
triée
population finale...
n
... n
... n
... n
triée
niveau de sélection
énergies
Validation sur des petites molécules organiques
Temps de calculs relativement longs
Échantillonnage conformationnel
Problématique et codage
Algorithme génétique
Hybridations
Méta optimisation
Parallélisation
21/53
Hybridations
MonteCarlo
Distributions de probabilité biaisées
Mutations Dirigées
Recherche taboue
Fragmentation
Introduction
Modélisation moléculaireBiologie systémiqueConclusion
Algorithmes génétiquesRelativement lents
Ne tirent pas parti de la physique du problème
Hybridation par des heuristiques complémentaires :
22/53
Muter un seul codon est très rarement viable
idée : muter et autoriser des réarrangements locaux
Évolution bloquée dans des minima locaux,
Aucune mutationne peut aider
Ajout d’unterme de contrainte,
Optimisation par Gradient
dans le nouveau paysage
Relaxation finale vers le minimum local
avoisinant
Lancé en parallèle
HybridationsIntroduction
Modélisation moléculaireBiologie systémiqueConclusion
énergie
θ1
θ2
23/53
Jeux de tests :
Par défaut, toutes les stratégies activées
Puis, tour à tour, désactivation d’une heuristique :
Sans mutation dirigée
Sans tabou
Distributions uniformes
Distributions minimisant les tensions locales
Trois à quatre tests pour chaque
Introduction
Modélisation moléculaireBiologie systémiqueConclusion
Hybridations
24/53
Hybridations
La solution expérimentale est trouvée parmi d’autres solutions
Introduction
Modélisation moléculaireBiologie systémiqueConclusion
Défaut Sans mut. dir. Sans tabou Tensions locales Distribution uniforme
Problématique et codage
Algorithme génétique
Hybridations
Méta optimisation
Parallélisation
Échantillonnage conformationnel
26/53
Les performances des AG dépendent (fortement) des « hyper paramètres » de contrôle :
Méta optimisation
Gestion de la population
Taille de population
Nombre de processus parallèles
Taux de migration
Gestion de l’évolution
Taux de croisement
Taux de mutation
Croisements à un et deux points
Gestion de la convergence
Fréquence des apocalypses
Condition globale d’arrêt
Pression de sélection
Élitisme
Âge maximal
Limite de dissimilitude
Introduction
Modélisation moléculaireBiologie systémiqueConclusion
27/53
nouvelle générationgénération temporaire
Méta optimisation
Pression de sélection
Élitisme
Âge maximal
Limite de dissimilitude
Introduction
Modélisation moléculaireBiologie systémiqueConclusion
28/53
p1 p2 p3 p4 p5 p6 pn
Gestion de la population
Taille de population
Nombre de processus parallèles
Taux de migration
Gestion de l’évolution
Taux de croisement
Taux de mutation
Croisements à un et deux pointsA.G.
Que faire avec ces paramètres ?
Méta optimisation
Pression de sélection
Élitisme
Âge maximal
Limite de dissimilitude
Gestion de la convergence
Fréquence des apocalypses
Condition globale d’arrêt
Introduction
Modélisation moléculaireBiologie systémiqueConclusion
29/53
Comment définir une stratégie optimale ?Comment comparer deux exécutions ?
Dans un contexte stochastique ?
La « meilleure » stratégie dépend-elle de la molécule traitée ?
Question ouverte : comment connaître a priori des hyper paramètres satisfaisants ?
Méta optimisationIntroduction
Modélisation moléculaireBiologie systémiqueConclusion
30/53
Problème d’optimisation classiqueÉvaluation de la qualité d’un échantillonnage :
Abordé par « méta »-algorithme génétique (µ-AG)
Introduction
Modélisation moléculaireBiologie systémiqueConclusion
Méta optimisation
31/53
Schéma
global :
AG paramétréIntroduction
Modélisation moléculaireBiologie systémiqueConclusion
Méta optimisation
32/53
molécule polycyclique
100
200
300
400
500
600
700
800
900
N° du Jeu de Paramètres
Paramètresoptimisés
Paramètresaléatoires
Éne
rgie
libr
e de
l’en
sem
ble
écha
ntill
onn
é
Introduction
Modélisation moléculaireBiologie systémiqueConclusion
Méta optimisation
33/53
Validations (résumé) :
Capacité exploratrice des AG
Stratégie de méta optimisation des hyper
paramètres
Hybridation avec heuristiques complémentairesParent [2007a]
Amélioration des temps de calculs
Long pour les tests du méta AG
Toujours prohibitif pour les plus grandes molécules
Introduction
Modélisation moléculaireBiologie systémiqueConclusion
Méta optimisation
Échantillonnage conformationnel
Problématique et codage
Algorithme génétique
Hybridations
Méta optimisation
Parallélisation
35/53
Parallélisation
Projet ANR Docking@grid avec l’équipe OPAC du
LIFL (Pr. Talbi)
http://dockinggrid.gforge.inria.fr/index.html
Grid5000 : environnement multiprocesseur
Généralisation des îles :
Multiplier les îles pas de sens
Indépendance totale bénéfice de l’architecture grille ?
Pande [2003]
Utilisation des solutions précédemment échantillonnées
Introduction
Modélisation moléculaireBiologie systémiqueConclusion
36/53
Parallélisation
- Hyper paramètres- Exécutables- Fichier moléculaire- Graines- Liste taboue
- meilleures solutions- succès de l’échantillonnage
Bases desolutions
échantillonnéesBanque d’insémination
clusters récents : grainesclusters connus : tabous
Bases des jeux d’hyperparamètres évalués
Arrêt : Nombre de
« Missions » max rien de neuf depuis
trop de missions
www.grid5000.fr
µ-AG
Récolte etclassificationdes solutions
Introduction
Modélisation moléculaireBiologie systémiqueConclusion
tant qu’ nœud libre,y déployer des îles
37/53
Parallélisation
Stratégie : surveiller la (re)visite de régions de solutions
Classification : par énergies autour des plus stables (paramètre de taille Dmax)
Panspermie : insémination des planètes par
Des « graines » attractrices (régions plus récentes que Nintens missions)
Des tabous répulsifs (déjà intensifiés)
Régler Dmax et Nintens est un problème délicat !
Introduction
Modélisation moléculaireBiologie systémiqueConclusion
38/53
ParallélisationIntroduction
Modélisation moléculaireBiologie systémiqueConclusion
ExpérimentalePrédite
Tryptophancage
39/53
ParallélisationIntroduction
Modélisation moléculaireBiologie systémiqueConclusion
Parent [2007b]
ExpérimentalePrédite
Tryptophanzipper
40/53
Conclusions et perspectives
Acquis :
Suite d’algorithmes efficaces et adaptatifs
Stratégies d’hybridation
Premiers déploiements parallèles
Vers du docking (résultats non-présentés) :
Outil de positionnement relatif de deux molécules
Stratégie de criblage
Bonachéra [2006]
Perspectives :
Déploiements massivement parallèles
Développement de nouvelles stratégies
Meilleure caractérisation des conformations
Algorithme de docking
Introduction
Modélisation moléculaireBiologie systémiqueConclusion
Plan de la présentation
0. Introduction
1. Échantillonnage conformationnel
2. Modélisation en Biologie systémique
3. Conclusion
42/53
Problématique
La forme des interactions a-t-elle un impact sur les
dynamiques ?
À l’échelle de la cellule : impossible de décrire
L’ensemble des événements moléculaires
L’ensembles de acteurs
Recours à un modèle : les concentrations
Continues
Déterministes
Dimension finie
IntroductionModélisation moléculaire
Biologie systémiqueConclusion
(solutions d’équations différentielles ordinaires)
43/53
Rythmes circadiens
On observe :
Des oscillations qui perdurent en conditions
d’éclairement constant, avec période 24h
Une compensation en température (robustesse
de la période)
La possibilité
de réinitialiser
le système
IntroductionModélisation moléculaire
Biologie systémiqueConclusion
44/53
Nakajima [2005]
IntroductionModélisation moléculaire
Biologie systémiqueConclusion
Réseaux de régulation
ADNgène : ABC
protéine : p
prot : abcpromo
teur
45/53
Modèle théorique
Mise en évidence avec un modèle minimal d’un mécanisme oscillant :
les profils de dégradation
non linéaires
IntroductionModélisation moléculaire
Biologie systémiqueConclusion
46/53
But : déstabiliser le système
Modèle théoriqueIntroductionModélisation moléculaire
Biologie systémiqueConclusion
47/53
Modèle théorique
Fonction de dégradation quelconque : f
Condition sur f pour avoir un point d’équilibre ε
Condition sur les paramètres pour que ε soit
instable entouré d’un cycle limite
( en jouant sur les pôles du modèle linéarisé)
On montre que f linéaire n’est pas suffisante
Qu’il est nécessaire que la dégradation soit
saturée
IntroductionModélisation moléculaire
Biologie systémiqueConclusion
48/53
Exemple : Michaëlis- Menten
f(p)=a.p/(b+p)
Beaucoup utilisée
Il est possible de remonter aux domaines de paramètres générant des oscillations :
IntroductionModélisation moléculaire
Biologie systémiqueConclusion
49/53
Domaine de paramètresIntroductionModélisation moléculaire
Biologie systémiqueConclusion
50/53
Conclusion, perspectives
Acquis :
mise en évidence d’un mécanisme déstabilisant par une
approche purement formelle
Perspectives :
Confronter des valeurs expérimentales avec les
domaines trouvés
Évaluer la robustesse du système par rapport aux
variations de température
Autres mécanismes déstabilisants : diffusion (
propagation)
IntroductionModélisation moléculaire
Biologie systémiqueConclusion
Plan de la présentation
0. Introduction
1. Échantillonnage conformationnel
2. Modélisation en Biologie systémique
3. Conclusion
52/53
Conclusion
Dans la description des interactions, il existe un fossé entre
les événements moléculaires individuels
et la dynamique des modules fonctionnels
Le rôle de l’interdisciplinaire est primordial
IntroductionModélisation moléculaireBiologie systémique
Conclusion
53/53
Conclusion
Articles :Bonachéra F., Parent B., Horvath D. (2006) Journal of Chemical Models
Parent B., Kökosy A., Horvath D. (2007) Soft Computing
Tantar A.-A., Melab N., Talbi E.-G., Parent B., Horvath D. (2007) Future Generation Computer Systems
Hanoulle X., Melchior A., Sibille N., Parent B., Denys A., Wieruszeski J.-M., Horvath D., Allain F., Lippens G., Landrieu I. (2007) Journal of Biological Chemistry
Conférences :Parent B., Lippens G., Horvath D. (2006) Gordon Research Conference, Suisse
Parent B., Tantar A.-A., Melab N., Talbi E.-G., Horvath D. (2007) Congress on Evolutionary Computation, Singapour
Morant P.-E., Vandermoere C., Thommen Q., Parent B., Lemaire F., Corellou F., Schwartz C., Bouget F.-Y., Lefranc M. (2007) Rencontres du Non-Linéaire, Paris
IntroductionModélisation moléculaireBiologie systémique
Conclusion
Mm
erciEm
erciR m
erciCm
erciI