A Dynamic Programming Algorithm for Unsigned (1,2)-Exemplar Breakpoint Distance Problem with Span Constraint

The exemplar breakpoint distance problem (EBD for short) is NP-hard, even when one of the genomes, called G_1, has no repetition, and the other genome, called G_2, has genes that appear at most twice in the genome ((1, 2)-Exemplar Breakpoint Distance Problem or EBD(1, 2) for short). Unless P=NP, there is no polynomial time algorithm for EBD(1, 2). In this paper, we focus on unsigned EBD(1, 2), where both G₁ and G₂ are unsigned genomes. A genome G is called an s-span genome if all the genes from the same gene family are within distance at most s in G. For unsigned EBD (1, 2), if G_2 is an s-span genome, we call this new problem unsigned s-span EBD (1, 2). We develop a dynamic programming algorithm to compute the exemplar breakpoint distance of unsigned s-span EBD(1, 2), and prove its correctness. The space complexity of the algorithm is O(s4^sn), and the time complexity of the algorithm is O(s4^sn^3), where n is the size of G_1.