Savard Olivier Tremblay, Gagnon Yves, Bertrand Denis, El-Mabrouk Nadia
DIRO, Université de Montréal, Montréal, Quebec, Canada.
J Comput Biol. 2011 Sep;18(9):1185-99. doi: 10.1089/cmb.2011.0136.
Given a phylogenetic tree involving whole genome duplication events, we contribute to solving the problem of computing the rearrangement and double cut-and-join (DCJ) distances on a branch of the tree linking a duplication node d to a speciation node or a leaf s. In the case of a genome G at s containing exactly two copies of each gene, the genome halving problem is to find a perfectly duplicated genome D at d minimizing the rearrangement distance with G. We generalize the existing exact linear-time algorithm for genome halving to the case of a genome G with missing gene copies. In the case of a known ancestral duplicated genome D, we develop a greedy approach for computing the distance between G and D, called the double distance. Two algorithms are developed in both cases of a genome G containing exactly two copies of each gene, or at most two copies of each gene (with missing gene copies). These algorithms are shown time-efficient and very accurate for both the rearrangement and DCJ distances.
给定一个涉及全基因组复制事件的系统发育树，我们致力于解决计算该树中连接复制节点d与物种形成节点或叶节点s的分支上的重排和双切割连接（DCJ）距离的问题。对于叶节点s处的基因组G，其中每个基因恰好有两个拷贝的情况，基因组减半问题是要在复制节点d处找到一个完美复制的基因组D，使其与G的重排距离最小。我们将现有的用于基因组减半的精确线性时间算法推广到存在缺失基因拷贝的基因组G的情况。在已知祖先复制基因组D的情况下，我们开发了一种用于计算G与D之间距离的贪心方法，称为双距离。针对基因组G中每个基因恰好有两个拷贝，或每个基因最多有两个拷贝（存在缺失基因拷贝）的两种情况，分别开发了两种算法。这些算法在重排距离和DCJ距离方面都显示出高效性和极高的准确性。
