Approximability and Fixed-Parameter Tractability for the Exemplar Genomic Distance Problems. In: Chen J, Cooper SB, editors. Theory and Applications of Models of Computation. Berlin: Springer Berlin Heidelberg; 2009. pp. 71-80. [DOI: 10.1007/978-3-642-02017-9_10]

A Dynamic Programming Algorithm For (1,2)-Exemplar Breakpoint Distance

The exemplar breakpoint distance problem is motivated by finding conserved sets of genes between two genomes. It asks to find respective exemplars in two genomes to minimize the breakpoint distance between them. If one genome has no repeated gene (called trivial genome) and the other has genes repeating at most twice, it is referred to as the (1, 2)-exemplar breakpoint distance problem, EBD(1, 2) for short. Little has been done on algorithm design for this problem by now. In this article, we propose a parameter to describe the maximum physical span between two copies of a gene in a genome, and based on it, design a fixed-parameter algorithm for EBD(1, 2). Using a dynamic programming approach, our algorithm can take O(4(s)n(2)) time and O(4(s)n) space to solve an EBD(1, 2) instance that has two genomes of n genes where the second genome has each two copies of a gene spanning at most s copies of the genes. Our algorithm can also be used to compute the maximum adjacencies between two genomes. The algorithm has been implemented in C++. Simulations on randomly generated data have verified the effectiveness of our algorithm. The software package is available from the authors.

An exact algorithm for the zero exemplar breakpoint distance problem

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.