Exemplar or matching: modeling DCJ problems with unequal content genome data

Zhaoming Yin, Jijun Tang, Stephen W. Schaeffer, David A. Bader

Research output: Contribution to journalArticlepeer-review

7 Scopus citations


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 (i.e., insertions and deletions) 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 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 exhibit pros and cons of these two distance metrics per se, as well as putting them in the median computation scenario.

Original languageEnglish (US)
Pages (from-to)1165-1181
Number of pages17
JournalJournal of Combinatorial Optimization
Issue number4
StatePublished - Nov 1 2016
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Computer Science Applications
  • Discrete Mathematics and Combinatorics
  • Control and Optimization
  • Computational Theory and Mathematics
  • Applied Mathematics


  • Double-cut and join (DCJ)
  • Genome rearrangement
  • Lin–Kernighan heuristic


Dive into the research topics of 'Exemplar or matching: modeling DCJ problems with unequal content genome data'. Together they form a unique fingerprint.

Cite this