Th
Forum 'Emplois' - Sujet créé le 2006-08-22
Bonjour,
Nous cherchons urgemment un étudiant pour une thèse avec le sujet joint. La bourse est régionale et dans le cadre de l’Ouest Génopole. Les candidats doivent avoir le profil Recherche Opérationnelle/Optimisation Combinatoire et la volonté d’appliquer ses compétences dans le domaine de la bioinformatique. La sélection s’effectuera sur dossier. Les demandes sont à adresser à randonov@irisa.fr.
Pourriez-vous diffuser cette annonce le plus largement possible.
Merci d’avance
Rumen Andonov,
Professeur, Université de Rennes 1,
IRISA, Campus universitaire de Beaulieu,
F-35042 Rennes Cedex France,
Tél. : +33 (0) 2 99 84 71 56
Fax : : +33 (0) 2 99 84 71 71
E-mail : randonov@irisa.fr
URL : [url=http://www.irisa.fr/symbiose/people/randonov
]http://www.irisa.fr/symbiose/people/randonov
[/url]
Alignements de graphes : application à la comparaison de structures protéiques
Laboratoire : IRISA/INRIA, projet bioinformatique SYMBIOSE
Directeur de thèse (HDR) : ANDONOV Rumen (Prof .)
Mots clés : optimisation combinatoire, modélisation de la structure protéique, algorithmique, théorie de graphes, modèles mathématiques
Problématique:
Les fonctions d’une protéine sont étroitement liées avec sa forme/structure tridimensionnelle (3D) et on considère généralement que des protéines avec des formes 3D similaires possèdent aussi des fonctions qui se ressemblent, ce qui donne un grand intérêt aux méthodes de comparaison de structures. A l’heure actuelle il existe de nombreuses approches pour découvrir la similarité entre les structures des protéines.
Dans l’approche « contact map overlap (CMO) » la proximité entre les atomes de carbone α de deux résidus est exprimée par une relation binaire « oui-non ». La structure 3D est présentée comme un graphe linéaire où les acides aminés sont des sommets et les arcs représentent les relations binaires entre eux. Le nombre maximum d’arcs communs peut être défini comme une mesure de similarité entre deux structures. La recherche de ce nombre a été démontrée un problème NP-complet.
Dans l’approche VAST « Vector Alignement Search Tool » la structure d’une protéine est considérée comme une suite ordonnée de structures secondaires (SSE) représentées par des vecteurs 3D. La similarité entre deux structures est finalement exprimée par la clique de poids maximum sur les arêtes dans le graphe d’alignement des structures. (Le poids des arêtes de ce graphe correspond à la valeur RMSD entre les vecteurs associés.) La recherche de la clique de poids maximum sur les arêtes est aussi un problème NP-complet qu’on ne sait pas résoudre sur les instances de protéines actuellement.
Ce qui unifie les deux approches c’est la nécessité d’aligner d’une manière optimale des objets de même type (des acides aminés ou des vecteurs 3D) , ce qui engendre un problème d’optimisation combinatoire difficile.
Il existe aussi une autre approche qui nécessite d’aligner une séquence avec une structure, connue comme le « protein threading » (PTP). Pour ce problème nous avons montré récemment que si un modèle mathématique adéquat est utilisé les instances avec des données réelles peuvent être résolues en temps polynomial [1].
Objectifs
L’objectif de la thèse est de proposer un cadre théorique commun pour les alignements séquence/structure et structure/structure, ainsi que de développer un logiciel permettant leur résolution efficace. Notre démarche est justifiée par la réussite déjà obtenue dans le cadre d’alignement séquence/structure : à un certain niveau d’abstraction toutes ces approches mènent au problème de la recherche d’un chemin optimal augmenté (« best augmented path ») dans un graphe k-parti. Nos résultats précédents montrent que pour ce type de problème, l’approche relaxation lagrangienne est très efficace [3].
Ces travaux se baseront sur une extension des concepts et méthodes utilisés, pour l'instant, pour la résolution du PTP [1,2,3]. Du point de vue du rayonnement international, l’objectif est de participer à la compétition CASP « Critical Assessment of Techniques for Protein Structure Prediction », qui réunit les meilleures équipes au niveau mondial sur le sujet.
Partenariat
Ce sujet se déroulera en collaboration très étroite avec l'unité MIG de l'INRA de Jouy-en-Josas et avec l’université de Sofia, Bulgarie.
Profil de candidat souhaité
Pour mener à bien ce projet, le candidat doit avoir une bonne maîtrise des méthodes d’optimisation combinatoire (programmation linéaire, heuristiques), une goût prononcé et des connaissances en algorithmique et théorie des graphes ; un bon niveau en développement informatique et la forte volonté d’appliquer toutes ces compétences dans le domaine de la bioinformatique.
Références :
1. R. Andonov, S. Balev and N. Yanev, (2004) Protein Threading Problem: From Mathematical Models to Parallel Implementations, INFORMS Journal on Computing, 16, 393-405
2. P. Veber, N. Yanev, R. Andonov, V. Poirriez, Optimal protein threading by cost-splitting, WABI 2005, 5th Workshop of Algorithms in Bioinformatics, Spain, September 2005, Lecture Notes in Bioinformatics, 3692, pp. 365-375
3. Poirriez, V., Marin, A., Andonov, R. and J-F Gibrat. (2005) FROST: revisited and distributed . 4th IEEE International Workshop on High Performance Computational Biology (HiCOMB'05), April, Denver, Colorado
Nous cherchons urgemment un étudiant pour une thèse avec le sujet joint. La bourse est régionale et dans le cadre de l’Ouest Génopole. Les candidats doivent avoir le profil Recherche Opérationnelle/Optimisation Combinatoire et la volonté d’appliquer ses compétences dans le domaine de la bioinformatique. La sélection s’effectuera sur dossier. Les demandes sont à adresser à randonov@irisa.fr.
Pourriez-vous diffuser cette annonce le plus largement possible.
Merci d’avance
Rumen Andonov,
Professeur, Université de Rennes 1,
IRISA, Campus universitaire de Beaulieu,
F-35042 Rennes Cedex France,
Tél. : +33 (0) 2 99 84 71 56
Fax : : +33 (0) 2 99 84 71 71
E-mail : randonov@irisa.fr
URL : [url=http://www.irisa.fr/symbiose/people/randonov
]http://www.irisa.fr/symbiose/people/randonov
[/url]
Alignements de graphes : application à la comparaison de structures protéiques
Laboratoire : IRISA/INRIA, projet bioinformatique SYMBIOSE
Directeur de thèse (HDR) : ANDONOV Rumen (Prof .)
Mots clés : optimisation combinatoire, modélisation de la structure protéique, algorithmique, théorie de graphes, modèles mathématiques
Problématique:
Les fonctions d’une protéine sont étroitement liées avec sa forme/structure tridimensionnelle (3D) et on considère généralement que des protéines avec des formes 3D similaires possèdent aussi des fonctions qui se ressemblent, ce qui donne un grand intérêt aux méthodes de comparaison de structures. A l’heure actuelle il existe de nombreuses approches pour découvrir la similarité entre les structures des protéines.
Dans l’approche « contact map overlap (CMO) » la proximité entre les atomes de carbone α de deux résidus est exprimée par une relation binaire « oui-non ». La structure 3D est présentée comme un graphe linéaire où les acides aminés sont des sommets et les arcs représentent les relations binaires entre eux. Le nombre maximum d’arcs communs peut être défini comme une mesure de similarité entre deux structures. La recherche de ce nombre a été démontrée un problème NP-complet.
Dans l’approche VAST « Vector Alignement Search Tool » la structure d’une protéine est considérée comme une suite ordonnée de structures secondaires (SSE) représentées par des vecteurs 3D. La similarité entre deux structures est finalement exprimée par la clique de poids maximum sur les arêtes dans le graphe d’alignement des structures. (Le poids des arêtes de ce graphe correspond à la valeur RMSD entre les vecteurs associés.) La recherche de la clique de poids maximum sur les arêtes est aussi un problème NP-complet qu’on ne sait pas résoudre sur les instances de protéines actuellement.
Ce qui unifie les deux approches c’est la nécessité d’aligner d’une manière optimale des objets de même type (des acides aminés ou des vecteurs 3D) , ce qui engendre un problème d’optimisation combinatoire difficile.
Il existe aussi une autre approche qui nécessite d’aligner une séquence avec une structure, connue comme le « protein threading » (PTP). Pour ce problème nous avons montré récemment que si un modèle mathématique adéquat est utilisé les instances avec des données réelles peuvent être résolues en temps polynomial [1].
Objectifs
L’objectif de la thèse est de proposer un cadre théorique commun pour les alignements séquence/structure et structure/structure, ainsi que de développer un logiciel permettant leur résolution efficace. Notre démarche est justifiée par la réussite déjà obtenue dans le cadre d’alignement séquence/structure : à un certain niveau d’abstraction toutes ces approches mènent au problème de la recherche d’un chemin optimal augmenté (« best augmented path ») dans un graphe k-parti. Nos résultats précédents montrent que pour ce type de problème, l’approche relaxation lagrangienne est très efficace [3].
Ces travaux se baseront sur une extension des concepts et méthodes utilisés, pour l'instant, pour la résolution du PTP [1,2,3]. Du point de vue du rayonnement international, l’objectif est de participer à la compétition CASP « Critical Assessment of Techniques for Protein Structure Prediction », qui réunit les meilleures équipes au niveau mondial sur le sujet.
Partenariat
Ce sujet se déroulera en collaboration très étroite avec l'unité MIG de l'INRA de Jouy-en-Josas et avec l’université de Sofia, Bulgarie.
Profil de candidat souhaité
Pour mener à bien ce projet, le candidat doit avoir une bonne maîtrise des méthodes d’optimisation combinatoire (programmation linéaire, heuristiques), une goût prononcé et des connaissances en algorithmique et théorie des graphes ; un bon niveau en développement informatique et la forte volonté d’appliquer toutes ces compétences dans le domaine de la bioinformatique.
Références :
1. R. Andonov, S. Balev and N. Yanev, (2004) Protein Threading Problem: From Mathematical Models to Parallel Implementations, INFORMS Journal on Computing, 16, 393-405
2. P. Veber, N. Yanev, R. Andonov, V. Poirriez, Optimal protein threading by cost-splitting, WABI 2005, 5th Workshop of Algorithms in Bioinformatics, Spain, September 2005, Lecture Notes in Bioinformatics, 3692, pp. 365-375
3. Poirriez, V., Marin, A., Andonov, R. and J-F Gibrat. (2005) FROST: revisited and distributed . 4th IEEE International Workshop on High Performance Computational Biology (HiCOMB'05), April, Denver, Colorado