The Prague Stringology Conference 2003
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(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: |  |
 |
| PostScript |