The rooted SCJ median with single gene duplications
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 but 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, that we apply to simulated data, showing high accuracy of the reconstructed medians.