The Prague Stringology Conference 2003

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. [VDR98] 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(n4) in time and O(n4) in space, where n is the size of the sequences. In this paper, we propose an improved algorithm which costs O(n2) in time and O(n2) in space. Furthermore, we extend the operation set by addi point deletions. We present an algorithm which is O(n3) in time and O(n2) in space for this extended case.

Download paper: Article in PostScript Article in PDF
 PostScript   PDF