Titre :

Genome Dedoubling by DCJ and Reversal

Auteur(s) :

Thomas, Antoine [Auteur]
Bioinformatics and Sequence Analysis [BONSAI]
Varré, Jean-Stéphane [Auteur]
Bioinformatics and Sequence Analysis [BONSAI]
Aïda, Ouangraoua [Auteur]
Bioinformatics and Sequence Analysis [BONSAI]

Titre de la revue :

BMC Bioinformatics

Éditeur :

BioMed Central

Date de publication :

2011

ISSN :

1471-2105

Mot(s)-clé(s) en anglais :

Segmental Duplication
Ancestral Genome
Duplicate Segment
Rearrangement Event
Linear Time Complexity

Discipline(s) HAL :

Informatique [cs]/Bio-informatique [q-bio.QM]

Résumé en anglais : [en]

BackgroundSegmental duplications in genomes have been studied for many years. Recently, several studies have highlighted a biological phenomenon called <i>breakpoint-duplication</i> that apparently associates a significant ...
Lire la suite >BackgroundSegmental duplications in genomes have been studied for many years. Recently, several studies have highlighted a biological phenomenon called <i>breakpoint-duplication</i> that apparently associates a significant proportion of segmental duplications in Mammals, and the Drosophila species group, to breakpoints in rearrangement events.ResultsIn this paper, we introduce and study a combinatorial problem, inspired from the breakpoint-duplication phenomenon, called the <i>Genome Dedoubling Problem</i>. It consists of finding a minimum length rearrangement scenario required to transform a genome with duplicated segments into a non-duplicated genome such that duplications are caused by rearrangement breakpoints. We show that the problem, in the Double-Cut-and-Join (DCJ) and the reversal rearrangement models, can be reduced to an APX-complete problem, and we provide algorithms for the Genome Dedoubling Problem with 2-approximable parts. We apply the methods for the reconstruction of a non-duplicated ancestor of <i>Drosophila yakuba</i>.ConclusionsWe present the <i>Genome Dedoubling Problem</i>, and describe two algorithms solving the problem in the DCJ model, and the reversal model. The usefulness of the problems and the methods are showed through an application to real Drosophila data.Lire moins >

Langue :

Anglais

Comité de lecture :

Oui

Audience :

Internationale

Vulgarisation :

Non

Commentaire :

Proceedings of the Ninth Annual Research in Computational Molecular Biology (RECOMB) Satellite Workshop on Comparative Genomics

Collections :

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

Source :

Harvested from HAL