Translocation-Deletions Distance Formula for Sorting Genomes

Given two signed multi-chromosomal genomes Pi and Gamma, where gene set of Gamma is the proper subset of that of Pi, the problem of sorting by translocation-deletions, which is abbrebiated as STD, is to find the shortest sequence transforming Pi to Gamma via the two operations mentioned above only. A lower bound of the distance from Pi to Gamma and an asymptotically optimal algorithm has been given. In this paper we present a formula to calculate the translocation-deletions distance for the first time. Moreover, we improved the existing algorithms to a new one, which is the first algorithm presenting the precise distance and the optimal translocation and deletion sequence in polynomial-time. After giving the algorithm analysis, we illustrate the performence with an example.