Non-breaking Similarity of Genomes with Gene Repetitions

摘要

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 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{sup}(1-ε) polynomial-time approximation unless P=NP. (Also, ENbS is W[l]-complete.) (2) We show that for several practically interesting cases of the Exemplar Non-breaking Similarity problem, there are polynomial time algorithms