Return to Job offers

Optimisation combinatoire avancée appliquée à la génomique

Encadrants :

Titre du stage : Optimisation combinatoire avancée appliquée à la génomique

Mots clés : solveur, graphes, algorithme exact, optimisation linéaire en nombres entiers

Rémunération : indemnisation standard (≈ 500 Euros/mois)

Description du stage :

L’alignement multiple de séquences [1] (Fig 1) est une technique fondamentale en bioinformatique. Elle est à la base d’un grand nombre d’analyses telles que les études de phylogénie moléculaire, celles sur les propriétés des protéines et des acides nucléiques. Il existe de nombreuses méthodes heuristiques pour obtenir une solution approchée du problème de la recherche du meilleur alignement multiple de séquences. La seule méthode exacte proposée est la programmation dynamique multidimensionnelle qui est 0(LN) en temps et mémoire où N est le nombre de séquences à aligner et L leur longueur. Cette méthode est donc inutilisable en pratique dès que le nombre de séquences et/ou leur longueur sont un tant soit peu grands.

Hebergeur d'image

Nous souhaitons dans ce stage étudier une approche alternative fournissant également une solution exacte du problème. Cette approche est basée sur la transformation du problème d’alignement multiple de séquences en un problème de graphe, ce dernier étant résolu par une méthode d’optimisation combinatoire en nombres entiers (Integer Linear programming).

Ce stage est en collaboration avec l’Unité Mathématique et Informatique Appliquée du Génome à l’environnement dont les chercheurs peuvent fournir les données spécifiques ainsi que leur grande compétence du domaine. Aucun pré-requis en Bioinformatique et Génomique n’est nécessaire dans ce contexte. Un modèle initial sera proposé à l’étudiant ayant choisi le sujet. Les premières expérimentations effectuées avec ce modèle montrent que l’on peut obtenir une solution optimale au problème de l’alignement multiple de séquences. Néanmoins, la taille des problèmes que l’on peut résoudre en des temps raisonnables reste encore très réduite.

Le but du stage est, dans un premier temps, d’analyser d’où viennent les goulots d’étranglement limitant cette taille puis de proposer et tester différentes stratégies pour y remédier. Tout au long de ce stage, l’étudiant sera amené à utiliser des solveurs modernes d’optimisation tels que Gurobi [2] et Cplex [3]. Il apprendra à les manipuler via des langages de programmation divers tels qu’AMPL [4] et Python, lui permettant ainsi d’acquérir de solides bases en modélisation et en prototypage d’applications destinées à la recherche.

Compétences requises :

Connaissances en Python 3 et en algorithmique des graphes et surtout un intérêt pour la conception d’algorithmes d’optimisation.

Références :

  1. Notredame, C (2007). “Recent Evolutions of Multiple Sequence Alignment Algorithms”. PLOS Computational Biology. 3 (8)
  2. GUROBI
  3. CPLEX
  4. AMPL

Permanent link to this article: https://team.inria.fr/genscale/job-offers/optimisation-combinatoire-avancee-appliquee-a-la-genomique/