Tandem Halving Problems by DCJ

Antoine Thomas 1 Aïda Ouangraoua 1, * Jean-Stéphane Varré 1, 2, *
* Auteur correspondant
1 BONSAI - Bioinformatics and Sequence Analysis
LIFL - Laboratoire d'Informatique Fondamentale de Lille, Inria Lille - Nord Europe
Abstract : We address the problem of reconstructing a non-duplicated ancestor to a partially duplicated genome in a model where duplicated content is caused by several tandem duplications throughout its evolution and the only allowed rearrangement operations are DCJ. As a starting point, we consider a variant of the Genome Halving Problem, aiming at reconstructing a tandem duplicated genome instead of the traditional perfectly duplicated genome. We provide a distance in O(n) time and a scenario in O(n2) time. In an attempt to enhance our model, we consider several problems related to multiple tandem reconstruction. Unfortunately we show that although the problem of reconstructing a single tandem can be solved polynomially, it is already NP-hard for 2 tandems.
Type de document :
Communication dans un congrès
Workshop on Algorithms in Bioinformatics, Sep 2012, Ljubljana, Slovenia. Springer Berlin Heidelberg, 7534, pp.417-429, 2012, 〈10.1007/978-3-642-33122-0_33〉
Liste complète des métadonnées

Littérature citée [10 références]  Voir  Masquer  Télécharger

https://hal.archives-ouvertes.fr/hal-00749019
Contributeur : Jean-Stéphane Varré <>
Soumis le : mardi 6 novembre 2012 - 14:48:53
Dernière modification le : vendredi 8 janvier 2016 - 01:06:58
Document(s) archivé(s) le : samedi 17 décembre 2016 - 07:57:40

Fichier

article3.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

Antoine Thomas, Aïda Ouangraoua, Jean-Stéphane Varré. Tandem Halving Problems by DCJ. Workshop on Algorithms in Bioinformatics, Sep 2012, Ljubljana, Slovenia. Springer Berlin Heidelberg, 7534, pp.417-429, 2012, 〈10.1007/978-3-642-33122-0_33〉. 〈hal-00749019〉

Partager

Métriques

Consultations de
la notice

299

Téléchargements du document

121