Zhang Meng, Arndt William, Tang Jijun
College of Computer Science and Technology, Jilin University, China.
Pac Symp Biocomput. 2009:138-49.
The "double-cut-and-join" (DCJ) model of genome rearrangement proposed by Yancopoulos et al. uses the single DCJ operation to account for all genome rearrangement events. Given three signed permutations, the DCJ median problem is to find a fourth permutation that minimizes the sum of the pairwise DCJ distances between it and the three others. In this paper, we present a branch-and-bound method that provides accurate solution to the multichromosomal DCJ median problems. We conduct extensive simulations and the results show that the DCJ median solver performs better than other median solvers for most of the test cases. These experiments also suggest that DCJ model is more suitable for real datasets where both reversals and transpositions occur.
扬科波洛斯等人提出的基因组重排“双切割与连接”（DCJ）模型使用单一的DCJ操作来解释所有基因组重排事件。给定三个带符号排列，DCJ中位数问题是找到第四个排列，使其与其他三个排列之间的成对DCJ距离之和最小。在本文中，我们提出了一种分支定界方法，该方法能为多染色体DCJ中位数问题提供精确解。我们进行了广泛的模拟，结果表明，在大多数测试案例中，DCJ中位数求解器的性能优于其他中位数求解器。这些实验还表明，DCJ模型更适用于同时发生反转和转座的真实数据集。
