中文摘要：

基因组移位排序在基因组重组排序计算研究中占有重要位置．交互型移位和非交互型移位均为移位的特殊形式．目前见到的多种移位排序算法均是针对交互型移位而得到的，未见基因组一般移位排序计算的研究结果．文中讨论包括交互型移位和非交互型移位的一般移位排序问题的求解方法，给出该问题的一个多项式时间算法．算法的关键在于将一般移位排序问题在线性时间内归约为交互型移位排序问题，利用交互型移位排序的算法来求解一般移位排序．作者的算法证实了Ozery-Flato等关于一般移位排序问题可以多项式时间解决的猜测．

英文摘要：

Sorting genomes by translocations plays an important role in the research of genome rearrangement. Translocation is a prevalent rearrangement event in the evolution of multi-chromosomal species which exchanges ends between two chromosomes. Translocations include recip- rocal translocations and non-reciprocal translocations. Translocation sorting problem asks to find a shortest sequence of translocations to transform one genome into another. Several polynomial algorithms have been presented, all of them only allowing reciprocal translocations. Thus they can only be applied to a pair of genomes having the same set of chromosome ends. Such a restriction can be removed if non-reciprocal translocations are also allowed. In this paper, the authors study for the problem of sorting by generalized translocations, which allows both reciprocal and non-reciprocal translocations, and present a polynomial-time algorithm for this problem, in which the problem of sorting by generalized translocations is reduced in linear time to the problem of sorting by reciprocal translocations. This algorithm confirms Ozery-Flato＇s conjecture that sorting by generalized translocations could be solved in polynomial time.