关键词: 基因组重组；交互移位排序；移位距离

Abstract:

During the past decades，several polynomial algorithms have been developed for the problem of sorting by reciprocal translocations (abbreviated as SRT), which is to find the shortest sequence of reciprocal translocations that transforms one genome into another. However, there are many shortest sequences of reciprocal translocations for most problem instances. In consequence, the problem of finding all the shortest sequences of reciprocal translocations is a natural generalization of SRT. This problem reduces easily to the problem of finding all  the “sorting reciprocal translocations” of one genome with respect to another—that is, all translocations ρ which can reduce the translocation distance of the resulting genome from another after applying ρ on one genome. In this paper, we give an efficient algorithm for finding all the sorting reciprocal translocations. While the new algorithm improves little in asymptotic time complexity, the experimental results show that it performs better in practice than the brute force method.

Key words: genome rearrangements;sorting by reciprocal translocations;translocation distance