Abstract: The problem of sorting by signed reversals is inspired by a genome rearrangement problem in computational molecular biology. Given two genomes represented as signed permutations of the same elements (e.g. orthologous genes), the problem consists in finding a most parsimonious scenario of reversals that transforms one genome into the other. We propose a method for sorting a signed permutation by reversals in time O(n). The best known algorithms run in time O(n^2), the main obstacle to an improvement being a costly operation of detection of so-called «safe» reversals. We bypass this detection and, using the same data structure as a previous random approximation algorithm, we achieve the same subquadratic complexity for finding an exact optimal solution. This answers an open question by Ozery-Flato and Shamir whether a subquadratic complexity could ever be achieved for solving the problem.

Résumé : 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'obsacle 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.

See also INRIA Research Report RR-5097, February 2004