Sorting genomes by generalized translocations

Translocation is a prevalent rearrangement event in the evolution of multi-chromosomal species which exchanges ends between two chromosomes. A translocation is reciprocal if none of the exchanged ends is empty; otherwise, non-reciprocal. The problem of sorting by translocations asks to find a shortest sequence of translocations transforming one genome into another. The problem of sorting by reciprocal translocations can be solved in polynomial-time. Several algorithms have been developed for reciprocal translocation sorting. 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, we show how to extend the algorithm for sorting by reciprocal translocations to include non-reciprocal translocations, allowing us to compare genomes containing different chromosome ends. We call this problem sorting by generalized translocations. We present a polynomial algorithm for this problem. At a conceptual level, there is some similarity between our algorithm and the algorithm developed by Hannenhalli which is used to sort genomes by reversals and translocations.