A lin-kernighan heuristic for the DCJ median problem of genomes with unequal contents

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution


In this paper, we designed a distance metric as DCJ-Indel-Exemplar distance to estimate the dissimilarity between two genomes with unequal contents (with gene insertions/deletions (Indels) and duplications). Based on the aforementioned distance metric, we proposed the DCJ-Indel-Exemplar median problem, to find a median genome that minimize the DCJ-Indel-Exemplar distance between this genome and the given three genomes. We adapted Lin-Kernighan (LK) heuristic to calculate the median quickly by utilizing the features of adequate sub-graph decomposition and search space reduction technologies. Experimental results on simulated gene order data indicate that our distance estimator can closely estimate the real number of rearrangement events; while compared with the exact solver using equal content genomes, our median solver can get very accurate results as well. More importantly, our median solver can deal with Indels and duplications and generates results very close to the synthetic cumulative number of evolutionary events.

Original languageEnglish (US)
Title of host publicationComputing and Combinatorics - 20th International Conference, COCOON 2014, Proceedings
PublisherSpringer Verlag
Number of pages12
ISBN (Print)9783319087825
StatePublished - 2014
Externally publishedYes
Event20th International Computing and Combinatorics Conference, COCOON 2014 - Atlanta, GA, United States
Duration: Aug 4 2014Aug 6 2014

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume8591 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference20th International Computing and Combinatorics Conference, COCOON 2014
Country/TerritoryUnited States
CityAtlanta, GA

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science


  • Double-cut and Join (DCJ)
  • Genome Rearrangement
  • Lin-Kernighan Heuristic


Dive into the research topics of 'A lin-kernighan heuristic for the DCJ median problem of genomes with unequal contents'. Together they form a unique fingerprint.

Cite this