Sorting genomes by translocations and deletions.

Given two signed multi-chromosomal genomes Pi and Gamma with the same gene set, the problem of sorting by translocations (SBT) is to find a shortest sequence of translocations transforming Pi to Gamma, where the length of the sequence is called the translocation distance between Pi and Gamma. In 1996, Hannenhalli gave the formula of the translocation distance for the first time, based on which an O(n3) algorithm for SBT was given. In 2005, Anne Bergeron et al. revisited this problem and gave an elementary proof for the formula of the translocation distance which leads to a new O(n3) algorithm for SBT. In this paper, we show how to extend Anne Bergeron's algorithm for SBT to include deletions, which allows us to compare genomes containing different genes. We present an asymptotically optimal algorithm for transforming Pi to Gamma by translocations and deletions, providing a feasible sequence with length at most OPT+2, where OPT is the minimum number of translocations and deletions transforming Pi to Gamma. Furthermore, this analysis can be used to approximate the minimum number of translocations and insertions transforming one genome to another.