Behshad Behzadi and Jean-Marc Steyaert

On The Transformation Distance Problem

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) in space. Furthermore, we extend the operation set by adding deletions. We present an algorithm which is O(n^3) in time and O(n) in space for this more general model.