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