Behshad Behzadi and Jean-Marc Steyaert

The Transformation Distance Problem Revisited

Evolution acts in several ways on biological sequences: either by mutating an element, or by inserting, deleting or copying a segment of the sequence. Varre et al. defined a transformation distance for the sequences, in which the evolutionary operations are copy, reverse copy and insertion of a segment. They also proposed an algorithm to calculate the transformation distance. This algorithm is O(n^4) in time and O(n^4) in space, where n is the size of the sequences. In this paper, we propose an improved algorithm which costs O(n^2) in time and O(n^2) in space. Furthermore, we extend the operation set by addi point deletions. We present an algorithm which is O(n^3) in time and O(n^2) in space for this extended case.