Title: Exemplar or Matching: Modeling DCJ Problems with Unequal Content Genome Data,
Abstract: The edit distance under the DCJ model can be computed in linear time for
genomes with equal content or with Indels. But it becomes NP-Hard in the
presence of duplications, a problem largely unsolved especially when Indels are
considered. In this paper, we compare two mainstream methods to deal with
duplications and associate them with Indels: one by deletion, namely
DCJ-Indel-Exemplar distance; versus the other by gene matching, namely
DCJ-Indel-Matching distance. We design branch-and-bound algorithms with set of
optimization methods to compute exact distances for both. Furthermore, median
problems are discussed in alignment with both of these distance methods, which
are to find a median genome that minimizes distances between itself and three
given genomes. Lin-Kernighan (LK) heuristic is leveraged and powered up by
sub-graph decomposition and search space reduction technologies to handle
median computation. A wide range of experiments are conducted on synthetic data
sets and real data sets to show pros and cons of these two distance metrics per
se, as well as putting them in the median computation scenario.