Department of Computer Science, Montana State University, Bozeman, MT 59717, USA.
Bioinformatics. 2011 Feb 1;27(3):311-6. doi: 10.1093/bioinformatics/btq674. Epub 2010 Dec 6.
The double cut and join operation (abbreviated as DCJ) has been extensively used for genomic rearrangement. Although the DCJ distance between signed genomes with both linear and circular (uni- and multi-) chromosomes is well studied, the only known result for the NP-complete unsigned DCJ distance problem is an approximation algorithm for unsigned linear unichromosomal genomes. In this article, we study the problem of computing the DCJ distance on two unsigned linear multichromosomal genomes (abbreviated as UDCJ).
We devise a 1.5-approximation algorithm for UDCJ by exploiting the distance formula for signed genomes. In addition, we show that UDCJ admits a weak kernel of size 2k and hence an FPT algorithm running in O(2(2k)n) time.
双切割和连接操作（简称 DCJ）已被广泛用于基因组重排。尽管带符号的线性和圆形（单和多）染色体的基因组之间的 DCJ 距离已经得到了很好的研究，但对于 NP 完全的无符号 DCJ 距离问题，唯一已知的结果是无符号线性单染色体基因组的近似算法。在本文中，我们研究了计算两个无符号线性多染色体基因组（简称 UDCJ）之间的 DCJ 距离的问题。
我们通过利用带符号基因组的距离公式设计了一个 UDCJ 的 1.5 近似算法。此外，我们还表明 UDCJ 有一个大小为 2k 的弱核，因此可以在 O(2(2k)n)时间内运行的 FPT 算法。
