Prix de la Fondation Dimitris N. Chorafas 2015 – Mingfu Shao

« Pour des formulations originales de programmes linéaires en nombres entiers dans le cadre de l'évolution des génomes par duplications, pertes et réarrangements, et l'apport pour leur résolution de techniques innovantes et efficaces alliant prétraitements et générations de contraintes. »

Nous présentons ici des algorithmes s’appliquant à des problèmes fondamentaux et inhérents à la comparaison de génomes entiers tels que la distance d’édition ou la distance médiane. Dans le cas d’une comparaison par paire de génomes entiers, nous avons développé le premier algorithme exact pour calculer la distance d’édition sous un modèle dit de DCJ (Double Cut and Join) et de duplication segmentale en présence de gènes dupliqués. Nous avons également divisé un algorithme (1.5+e)-approché pour calculer la distance d’édition sous les opérations DCJ complétées par des insertions et d’étions génomiques, ainsi qu’un algorithme exact et hautement rapide pour calculer la distance en points de cassure sous le modèle exemplaire. Dans le cas d’une comparaison multiple de génomes entiers, nous proposons un algorithme polynomial basé sur une formulation de flux. Ce dernier calcule les sous-graphes dit adéquats qui constituent une phase centrale du calcul de la médiane. En outre nous avons prouvé que s’il existe une borne supérieure à la distance médiane, cette dernière est exacte.

Ces méthodes furent appliquées au problème de détection des orthologues et paralogues entre deux génomes et démontrent ainsi la faisabilité d’une application systématique ¨à l’inférence de relations fonctionnelles ainsi qu’à l’annotation de génomes. En terme de performances, des tests sur des données biologiques indiquent que nos méthodes sont extrêmement rapides, applicables à des génomes entiers et obtiennent des résultats de haute précision.