Advertisement
Published in:
2010 | OriginalPaper | Chapter
The Zero Exemplar Distance Problem
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Given two genomes with duplicate genes,
Zero Exemplar Distance
is the problem of deciding whether the two genomes can be reduced to the same genome without duplicate genes by deleting all but one copy of each gene in each genome. Blin, Fertin, Sikora, and Vialette recently proved that
Zero Exemplar Distance
for monochromosomal genomes is NP-hard even if each gene appears at most two times in each genome, thereby settling an important open question on genome rearrangement in the exemplar model. In this paper, we give a very simple alternative proof of this result. We also study the problem
Zero Exemplar Distance
for multichromosomal genomes without gene order: from one direction, we show that this problem is NP-hard even if each gene appears at most two times in each genome; from the other direction, we show that this problem admits a polynomial-time algorithm if only one of the two genomes has duplicate genes, and is fixed-parameter tractable if the parameter is the maximum number of chromosomes in each genome.