Kováč Jakub, Warren Robert, Braga Marília D V, Stoye Jens
Department of Computer Science, Faculty of Mathematics, Physics, and Informatics, Comenius University, Bratislava, Slovakia.
J Comput Biol. 2011 Sep;18(9):1231-41. doi: 10.1089/cmb.2011.0116.
We study three classical problems of genome rearrangement--sorting, halving, and the median problem--in a restricted double cut and join (DCJ) model. In the DCJ model, introduced by Yancopoulos et al., we can represent rearrangement events that happen in multichromosomal genomes, such as inversions, translocations, fusions, and fissions. Two DCJ operations can mimic transpositions or block interchanges by first extracting an appropriate segment of a chromosome, creating a temporary circular chromosome, and then reinserting it in its proper place. In the restricted model, we are concerned with multichromosomal linear genomes and we require that each circular excision is immediately followed by its reincorporation. Existing linear-time DCJ sorting and halving algorithms ignore this reincorporation constraint. In this article, we propose a new algorithm for the restricted sorting problem running in O(n log n) time, thus improving on the known quadratic time algorithm. We solve the restricted halving problem and give an algorithm that computes a multilinear halved genome in linear time. Finally, we show that the restricted median problem is NP-hard as conjectured.
我们在受限的双切割与连接（DCJ）模型中研究基因组重排的三个经典问题——排序、减半和中位数问题。在Yancopoulos等人提出的DCJ模型中，我们可以表示多染色体基因组中发生的重排事件，如倒位、易位、融合和裂变。两个DCJ操作可以通过首先提取染色体的适当片段、创建一个临时环状染色体，然后将其重新插入到合适位置来模拟转座或块交换。在受限模型中，我们关注多染色体线性基因组，并且要求每次环状切除后紧接着进行重新整合。现有的线性时间DCJ排序和减半算法忽略了这种重新整合约束。在本文中，我们提出了一种用于受限排序问题的新算法，其运行时间为O(n log n)，从而改进了已知的二次时间算法。我们解决了受限减半问题，并给出了一个在线性时间内计算多线性减半基因组的算法。最后，我们证明了受限中位数问题如所推测的那样是NP难的。
