TY - GEN
T1 - Non-breaking similarity of genomes with gene repetitions
AU - Chen, Zhixiang
AU - Fu, Bin
AU - Xu, Jinhui
AU - Yang, Boting
AU - Zhao, Zhiyu
AU - Zhu, Binhai
PY - 2007
Y1 - 2007
N2 - 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.
AB - 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.
UR - https://www.scopus.com/pages/publications/37749034336
U2 - 10.1007/978-3-540-73437-6_14
DO - 10.1007/978-3-540-73437-6_14
M3 - Conference contribution
AN - SCOPUS:37749034336
SN - 9783540734369
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 119
EP - 130
BT - Combinatorial Pattern Matching - 18th Annual Symposium, CPM 2007, Proceedings
PB - Springer Verlag
T2 - 18th Annual Symposium on Combinatorial Pattern Matching, CPM 2007
Y2 - 9 July 2007 through 11 July 2007
ER -