Transformation distances: a family of dissimilarity measures based on movements of segments

Motivation: Evolution acts in several ways on DNA: either by mutating a bas e, or by inserting, deleting or copying a segment of the sequence (Ruddle, 1997; Russell, 1994; Li and Grauer, 1991). Classical alignment methods deal with point mutations (Waterman, 1995), genome-level mutations are studied using genome rearrangement distances (Bafna and Pevzner; 1993, 1995; Kececi oglu and Sankoff, 1994; Kececioglu and Ravi, 1995). The latter distances ge nerally operate, not on the sequences, but an an ordered list of genes. To our knowledge, no measure of distance attempts to compare sequences using a general set of segment-based operations. Results: Here We define a new family of distances, called transformation di stances, which quantify the dissimilarity between two sequences in terms of segment-based events. We focus on the case where segment-copy, -reverse-co py and -insertion ave allowed in our set of operations. Those events are we ighted by their description length, but other sets of weights are possible when biological information is available. The transformation distance from sequence S to sequence Tis then the Minimun Description Length among all po ssible scripts that build T knowing S with segment-based operations. The un derlying idea is related to Kalmogorov complexity theory. We present an alg orithm which, given two sequences S and T, computes exactly and efficiently the transformation distance from S to T. Unlike alignment methods, the met hod we propose does not necessarily respect the order of the residues withi n the compared sequences and is therefore able to account for duplications and translocations that cannot be properly described by sequence alignment A biological application on Tnt1 tobacco retrotransposon is presented.