Sorting With Forbidden Intermediates

Carlo Comin 1, 2 Anthony Labarre 1 Romeo Rizzi 2 Stéphane Vialette 1
1 LIGM - Laboratoire d'Informatique Gaspard-Monge
2 Dipartimento di Informatica [Verona]
Abstract : A wide range of applications, most notably in comparative genomics, involve the computation of a shortest sorting sequence of operations for a given permutation, where the set of allowed operations is fixed beforehand. Such sequences are useful for instance when reconstructing potential scenarios of evolution between species, or when trying to assess their similarity. We revisit those problems by adding a new constraint on the sequences to be computed: they must avoid a given set of forbidden intermediates, which correspond to species that cannot exist because the mutations that would be involved in their creation are lethal. We initiate this study by focusing on the case where the only mutations that can occur are exchanges of any two elements in the permutations, and give a polynomial time algorithm for solving that problem when the permutation to sort is an involution.
Document type :
Conference papers
Complete list of metadatas

Cited literature [16 references]  Display  Hide  Download
https://hal-upec-upem.archives-ouvertes.fr/hal-01287040
Contributor : Anthony Labarre <>
Submitted on : Friday, March 11, 2016 - 4:48:54 PM
Last modification on : Thursday, July 5, 2018 - 2:45:49 PM
Long-term archiving on: Monday, June 13, 2016 - 8:35:51 AM

File

1602.06283v1.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01287040, version 1
  • ARXIV : 1602.06283

Collections

UPEC-UPEM | CNRS | ENPC | PARISTECH | LIGM | LIGM_MOA | ESIEE-PARIS

Citation

Carlo Comin, Anthony Labarre, Romeo Rizzi, Stéphane Vialette. Sorting With Forbidden Intermediates. Third International Conference on Algorithms for Computational Biology (AlCoB 2016), María Botón-Fernández; Carlos Martín-Vide; Miguel A. Vega-Rodríguez; Florentina Lilica Voicu, Jun 2016, Trujillo, Spain. ⟨hal-01287040⟩

Export

BibTeX TEI DC DCterms EndNote

Share

Metrics

Record views

261

Files downloads

192

Contact

Informations

CCSD