Exploring the Solution Space of Sorting by Translocations

Genome sorting is a way to trace back the genomes of two species to their common ancestor. The study of genome rearrangements allows to better understand the process of evolution and is an important tool in comparative genomics. Given two genomes A and B, the goal is to find a shortest sequence of exchanges of non-empty chromosome ends that transform A into B. The length of such a shortest sequence is called the translocation distance between A and B, and the problem of finding the optimal sequence of translocations is called the sorting by translocations problem. For most problem instances, however, several minimum length sequences or optimal sequences of translocation exist, and in the absence of any additional information, no one is of greater value than the others. The problem of finding all optimal solutions for sorting by translocations is thus a natural generalization of sorting by translocations. In this paper, an algorithm is presented to find all solutions for sorting by translocations.