.png){kind=icon}
.png){kind=icon}
Return
An Exact Algorithm for the Zero Exemplar Breakpoint Distance Problem
.png){kind=icon}
PRE
AI
DOI：10.1109/TCBB.2013.127.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
The exemplar breakpoint distance problem is one of the most important problems in genome comparison and has been extensively studied in the literature. The exemplar breakpoint distance problem cannot be approximated within any factor even if each gene family occurs at most twice in a genome. This is due to the fact that its decision version, the zero exemplar breakpoint distance problem where each gene family occurs at most twice in a genome (ZEBD(2, 2) for short) is NP-hard. Thus, the basic version ZEBD(2, 2) has attracted the attention of many scientists. The best existing algorithm for ZEBD(2, 2) runs in O(n2(n)) time. In this paper, we propose a new algorithm for ZEBD(2, 2) with running time O(n(2)1.86121(n)). We have implemented the algorithm in Java. The software package is available upon request.
Keywords:
Exemplar breakpoint distance
genome
gene family
algorithms
time complexity
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
I
IF:
3.4
Papers:
3.3K
Citations:
6.4K