Tandem Halving Problems by DCJ
Type de document :
Communication dans un congrès avec actes
Titre :
Tandem Halving Problems by DCJ
Auteur(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]
Bioinformatics and Sequence Analysis [BONSAI]
Laboratoire d'Informatique Fondamentale de Lille [LIFL]
Bioinformatics and Sequence Analysis [BONSAI]
Ouangraoua, Aïda [Auteur correspondant]
Bioinformatics and Sequence Analysis [BONSAI]
Varré, Jean-Stéphane [Auteur correspondant]
Bioinformatics and Sequence Analysis [BONSAI]
Laboratoire d'Informatique Fondamentale de Lille [LIFL]
Titre de la manifestation scientifique :
Workshop on Algorithms in Bioinformatics
Ville :
Ljubljana
Pays :
Slovénie
Date de début de la manifestation scientifique :
2012-09-10
Titre de l’ouvrage :
Algorithms in Bioinformatics
Titre de la revue :
Lecture Notes in Computer Science
Éditeur :
Springer Berlin Heidelberg
Springer
Springer
Date de publication :
2012
Discipline(s) HAL :
Informatique [cs]/Bio-informatique [q-bio.QM]
Sciences du Vivant [q-bio]/Bio-Informatique, Biologie Systémique [q-bio.QM]
Sciences du Vivant [q-bio]/Bio-Informatique, Biologie Systémique [q-bio.QM]
Résumé en anglais : [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 ...
Lire la suite >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.Lire moins >
Lire la suite >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.Lire moins >
Langue :
Anglais
Comité de lecture :
Oui
Audience :
Internationale
Vulgarisation :
Non
Collections :
Source :
Fichiers
- https://hal.archives-ouvertes.fr/hal-00749019/document
- Accès libre
- Accéder au document
- http://arxiv.org/pdf/1206.6899
- Accès libre
- Accéder au document
- https://hal.archives-ouvertes.fr/hal-00749019/document
- Accès libre
- Accéder au document
- document
- Accès libre
- Accéder au document
- article3.pdf
- Accès libre
- Accéder au document
- 1206.6899
- Accès libre
- Accéder au document