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. [12] denned 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.