Non-breaking Similarity of Genomes with Gene Repetitions

摘要

In this paper we define a new similarity measure, the nonbreaking 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 H, 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 H such that the resulting genomes G and H have the maximum non-breaking similarity. We have the following results. 1. 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-n~(1-∈) polynomial-time approximation unless P=NP. (Also, ENbS is W-complete.) 2. We show that for several practically interesting cases of the Exemplar Non-breaking Similarity problem, there are polynomial time algorithms.