The Rooted SCJ Median with Single Gene Duplications

Resource type
Date created
2018-10-01
Authors/Contributors
Abstract
The median problem is a classical problem in genome rearrangements. It aims to compute a gene order that minimizes the sum of the genomic distances to k>=3 given gene orders. This problem is intractable except in the related Single-Cut-or-Join and breakpoint rearrangement models. Here we consider the rooted median problem, where we assume one of the given genomes to be ancestral to the median, which is itself ancestral to the other genomes. We show that in the Single-Cut-or-Join model with single gene duplications, the rooted median problem is NP-hard. We also describe an Integer Linear Program for solving this problem, which we apply to simulated data, showing high accuracy of the reconstructed medians.
Document
Description
16th International Conference, RECOMB-CG 2018, Magog-Orford, QC, Canada, October 9-12, 2018, Proceedings. Part of the Lecture Notes in Computer Science book series (LNCS, volume 11183).
Published as
Mane A.C., Lafond M., Feijão P., Chauve C. (2018). The Rooted SCJ Median with Single Gene Duplications. In: Blanchette M., Ouangraoua A. (eds) Comparative Genomics. RECOMB-CG 2018. Lecture Notes in Computer Science, vol 11183. Springer
Document title
The Rooted SCJ Median with Single Gene Duplications
Editor
Blanchette M., Ouangraoua A.
Date
2018
Copyright statement
Copyright is held by the author(s).
Scholarly level
Peer reviewed?
Yes
Language
Member of collection