Le 11/12/2018 par Rodolphe :

Description : en bio-informatique, le problème d'échafaudage permet de reconstituer un génome à partir de séquences appelées contigs. Une des approche possible pour résoudre ce problème est de prendre en considération qu'un même contig peut apparaître plusieurs fois dans le génome. Un graphe d'échafaudage (G,M,w,m) est un graphe simple et non orienté G, muni d'un couplage parfait M (représentant les contigs), d'une fonction de poids w sur les arêtes n'appartenant pas au couplage (représentant le taux de confiance que deux contigs se suivent dans la séquence complète) et d'une fonction de multiplicité m sur les arêtes de couplage (représentant le nombre de fois qu'un contig peut apparaître). Le problème d'échafaudage consiste alors à trouver dans un graphe d'échafaudage, une collection de marches alternantes, ouvertes ou fermées, respectant la contrainte de multiplicité et de poids maximum. Ce problème est NP-complet.

Cependant, le défaut majeur de cette approche est qu'elle peut produire des séquences chimériques à cause de la présence de chemin dit ambigus. Le problème de la linéarisation consiste à retirer parcimonieusement les arêtes d'un graphe de solution, issu de l'échafaudage, de façon à détruire tous les chemins ambigus. Le problème de la linéarisation est NP-complet.

Nous avons déjà développé et implémenté quelques outils permettant de résoudre ce problème de façon exacte ou approchée. Nous aimerions comparer ces méthodes avec des métaheuristiques, dont voici une liste non exhaustive :
- algorithmes de recherche locale : gradient, tabou;
- algorithmes évolutionnistes;
- recuit simulé;
- algorithmes de colonie de fourmis;

L'objective de ce stage est d'implémenter dans notre programme quelques unes de ces métaheuristiques et de les comparer entre elles et avec les méthodes déjà existantes. Toute idée pour une nouvelle approche est bien entendu bienvenue.

Profil recherché : le principal prérequis est de savoir programmer en C++. Des connaissances théoriques en complexité, approximation, programmation mathématiques peuvent également être utiles.

Encadrants: Tom.davot@lirmm.fr, chateau@lirmm.fr, rgirou@lirmm.fr