Braga Marília D V, Stoye Jens
Technische Fakultät, Universität Bielefeld , Bielefeld, Germany.
J Comput Biol. 2010 Sep;17(9):1145-65. doi: 10.1089/cmb.2010.0109.
In genome rearrangements, the double cut and join (DCJ) operation, introduced by Yancopoulos et al. in 2005, allows one to represent most rearrangement events that could happen in multichromosomal genomes, such as inversions, translocations, fusions, and fissions. No restriction on the genome structure considering linear and circular chromosomes is imposed. An advantage of this general model is that it leads to considerable algorithmic simplifications compared to other genome rearrangement models. Recently, several works concerning the DCJ operation have been published, and in particular, an algorithm was proposed to find an optimal DCJ sequence for sorting one genome into another one. Here we study the solution space of this problem and give an easy-to-compute formula that corresponds to the exact number of optimal DCJ sorting sequences for a particular subset of instances of the problem. We also give an algorithm to count the number of optimal sorting sequences for any instance of the problem. Another interesting result is the demonstration of the possibility of obtaining one optimal sorting sequence by properly replacing any pair of consecutive operations in another optimal sequence. As a consequence, any optimal sorting sequence can be obtained from one other by applying such replacements successively, but the problem of finding the shortest number of replacements between two sorting sequences is still open.
在基因组重排中，2005年Yancopoulos等人提出的双切割与连接（DCJ）操作，能够表示多染色体基因组中可能发生的大多数重排事件，如倒位、易位、融合和裂变。该操作对线性和环状染色体的基因组结构没有限制。与其他基因组重排模型相比，这种通用模型的一个优点是它能使算法得到显著简化。最近，发表了几篇关于DCJ操作的论文，特别是有人提出了一种算法，用于找到将一个基因组排序为另一个基因组的最优DCJ序列。在这里，我们研究了这个问题的解空间，并给出了一个易于计算的公式，该公式对应于该问题特定实例子集的最优DCJ排序序列的确切数量。我们还给出了一种算法，用于计算该问题任何实例的最优排序序列的数量。另一个有趣的结果是，证明了通过适当地替换另一个最优序列中的任意一对连续操作，可以得到一个最优排序序列。因此，通过连续应用这种替换，可以从另一个最优排序序列得到任何最优排序序列，但两个排序序列之间最短替换次数的问题仍然悬而未决。
