Behshad Behzadi and Jean-Marc Steyaert

**The Transformation Distance Problem Revisited**

Abstract: |

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(n
in time and
^{4})O(n in space, where ^{4})n is the size of the sequences. In
this paper, we propose an improved algorithm which costs
O(n in
time and ^{2})O(n in space. Furthermore, we extend the operation set by
addi point deletions. We present an algorithm which is
^{2})O(n in time and
^{3})O(n in space for this extended case.
^{2}) |

Download article: | ||

PostScript |