Comment se rendre au LAPCS

Tri par inversions de complexité sous-quadratique

Eric Tannier, projet Helix

Le problème du tri des permutations signées par inversions est motivé par la théorie du réarrangement génomique en biologie moléculaire. Étant donnés deux génomes représentés par des permutations signées des mêmes éléments (par exemple des gènes orthologues), le but est de trouver une séquence d'inversions de taille minimum, qui transforme un génome en l'autre. Nous décrivons une méthode de tri des permutations signées par inversion de complexité en temps O(n). Les meilleurs algorithmes connus sont de complexité O(n^2), l'obstacle principal à une amélioration étant la détection à chaque pas des inversions dites "sûres". Nous éliminons cette étape dans notre méthode, et en utilisant une structure de représentation des permutations introduite précédemment pour construire une heuristique pour le tri par inversions, nous construisons une méthode exacte en temps sous-quadratique. Ceci répond à une question posée par Ozery-Flato et Shamir sur l'existence d'un tel algorithme.