The transformation distance: A dissimilarity measure based an movements of segments.

Abstract

Evolution acts in several ways on DNA : either by mutating a base, or inserting, deleting or copying a segment of the sequence [17, 18, ?]. Classical alignment methods deal with point mutations [19], genome-level mutations are studied using genome rearrangement distances [1, 2, 8, 9]. Those distances are mostly evaluated by a number of transpositions of genes. Here we define a new distance, called transformation distance, which quantifies the dissimilarity between two sequences in term of segment-based events (without requiring a preliminary identification of genes). Those events are weighted by their description length. The transformation distance from S to T is the Minimum Description Length among all possible scripts that build the sequence T knowing the sequence S with segment-based operations. The underlying idea is related to Kolmogorov complexity theory. Herein, we focus on the case where segment-copy, -reverse-copy and-insertion operations are allowed. We present an algorithm which computes the transformation distance. A biological application on Tnt1 tobacco retrotransposon is presented