On the tandem duplication-random loss model of genome rearrangement

We initiate the algorithmic study of a new model of genome rearrangement, the tandem duplication-random loss model, in which a genome evolves via successive rounds of tandem duplication of a contiguous segment of genes, followed by the loss of one copy of each of the duplicated genes. This model is well-known in the evolutionary biology literature, where it has been used to explain many of the known rearrangements in vertebrate mitochondrial genomes. Based on the model, we formalize a notion of distance between two genomes and show how to compute it efficiently for two interesting regions of the parameter space. We then consider median problems (i.e. finding the point which minimizes the sum of distances to a given set of points under some distance function) in the context of maximum parsimony phylogenetic reconstruction for these two special cases. Surprisingly, one of them turns out to correspond to the well-known rank aggregation problem, while the other corresponds to the biologically interesting case of whole genome duplication and loss, and we give an O(log log n) additive approximation algorithm for the latter.