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.
Home