Skip to Main content Skip to Navigation
Reports

Perfect Sorting by Reversals

Marie-France Sagot 1 Eric Tannier
1 HELIX - Computer science and genomics
Inria Grenoble - Rhône-Alpes, LBBE - Laboratoire de Biométrie et Biologie Evolutive - UMR 5558
Abstract : In computational biology, gene order data is often modelled as signed permutations. A classical problem in genome comparison is to detect conserved segments in a permutation, that is, genes that are co-localised in several species, indicating that they remained grouped during evolution. A second largely studied problem related to gene order data is to compute a minimum scenario of reversals that transforms a signed permutation into another. Several studies began to mix the two problems, and it was observed that their results are not always compatible : often parsimonious scenarios of reversals break conserved segments. In a recent study, Bérard, Bergeron and Chauve stated as an open question whether it was possible to design a polynomial time algorithm to decide if there exists a minimum scenario of reversals that transforms a genome into another while keeping the clusters of co-localised genes together. In this paper, we give this polynomial algorithm, and thus generalise the theoretical result of the aforementioned paper.
Document type :
Reports
Complete list of metadata

https://hal.inria.fr/inria-00070466
Contributor : Rapport de Recherche Inria <>
Submitted on : Friday, May 19, 2006 - 8:35:26 PM
Last modification on : Monday, February 10, 2020 - 4:36:45 PM
Long-term archiving on: : Sunday, April 4, 2010 - 9:16:49 PM

Identifiers

  • HAL Id : inria-00070466, version 1

Collections

Citation

Marie-France Sagot, Eric Tannier. Perfect Sorting by Reversals. RR-5540, INRIA. 2005, pp.13. ⟨inria-00070466⟩

Share

Metrics

Record views

298

Files downloads

308