Non-breaking similarity of genomes with gene repetitions

Zhixiang Chen, Bin Fu, Jinhui Xu, Boting Yang, Zhiyu Zhao, Binhai Zhu

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

22 Scopus citations


In this paper we define a new similarity measure, the non-breaking similarity, which is the complement of the famous breakpoint distance between genomes (in general, between any two sequences drawn from the same alphabet). When the two input genomes G and ℋ, drawn from the same set of n gene families, contain gene repetitions, we consider the corresponding Exemplar Non-breaking Similarity problem (ENbS) in which we need to delete repeated genes in G and ℋ such that the resulting genomes G and H have the maximum non-breaking similarity. We have the following results. - For the Exemplar Non-breaking Similarity problem, we prove that the Independent Set problem can be linearly reduced to this problem. Hence, ENbS does not admit any factor-n1-ε polynomial-time approximation unless P=NP. (Also, ENbS is W[1]-complete.) - We show that for several practically interesting cases of the Exemplar Non-breaking Similarity problem, there are polynomial time algorithms.

Original languageEnglish (US)
Title of host publicationCombinatorial Pattern Matching - 18th Annual Symposium, CPM 2007, Proceedings
PublisherSpringer Verlag
Number of pages12
ISBN (Print)9783540734369
StatePublished - 2007
Event18th Annual Symposium on Combinatorial Pattern Matching, CPM 2007 - London, ON, Canada
Duration: Jul 9 2007Jul 11 2007

Publication series

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


Other18th Annual Symposium on Combinatorial Pattern Matching, CPM 2007
CityLondon, ON

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'Non-breaking similarity of genomes with gene repetitions'. Together they form a unique fingerprint.

Cite this