Title :

Tandem Halving Problems by DCJ

Author(s) :

Thomas, Antoine [Auteur]
Bioinformatics and Sequence Analysis [BONSAI]
Ouangraoua, Aïda [Auteur correspondant]
Bioinformatics and Sequence Analysis [BONSAI]
Varré, Jean-Stéphane [Auteur correspondant]
Laboratoire d'Informatique Fondamentale de Lille [LIFL]
Bioinformatics and Sequence Analysis [BONSAI]

Conference title :

Workshop on Algorithms in Bioinformatics

City :

Ljubljana

Country :

Slovénie

Start date of the conference :

2012-09-10

Book title :

Algorithms in Bioinformatics

Journal title :

Lecture Notes in Computer Science

Publisher :

Springer Berlin Heidelberg
Springer

Publication date :

2012

HAL domain(s) :

Informatique [cs]/Bio-informatique [q-bio.QM]
Sciences du Vivant [q-bio]/Bio-Informatique, Biologie Systémique [q-bio.QM]

English abstract : [en]

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 ...
Show more >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.Show less >

Language :

Anglais

Peer reviewed article :

Oui

Audience :

Internationale

Popular science :

Non

Collections :

• Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189

Source :

Harvested from HAL