Name
Title | ||
|---|---|---|
Transformation distances: a family of dissimilarity measures based on movements of segments. |
Abstract | ||
|---|---|---|
Motivation: Evolution acts in several ways on DNA: either by mutating a base, 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; Kececioglu and Sankoff, 1994; Kececioglu and Ravi, 1995). The latter distances generally 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 distances, which quantify the dissimilarity between two sequences in terms of segment-based events. We focus on the case where segment-copy, -reverse-copy and -insertion ave allowed in our set of operations. Those events are weighted 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 possible scripts that build T knowing S with segment-based operations. The underlying idea is related to Kalmogorov complexity theory. We present an algorithm which, given two sequences S and T, computes exactly and efficiently the transformation distance from S to T. Unlike alignment methods, the method we propose does not necessarily respect the order of the residues within 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. |
Year | DOI | Venue |
|---|---|---|
1999 | 10.1093/bioinformatics/15.3.194 | BIOINFORMATICS |
Keywords | Field | DocType |
sequence alignment,point mutation,minimum description length,graphical interface | Sequence alignment,Kolmogorov complexity,Computer science,Molecular evolution,Minimum description length,Algorithm,Genome rearrangement,Genetics,Retrotransposon | Journal |
Volume | Issue | ISSN |
15 | 3 | 1367-4803 |
Citations | PageRank | References |
28 | 3.66 | 1 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jean-Stéphane Varré | 1 | 125 | 18.73 |
| Jean-Paul Delahaye | 2 | 325 | 54.60 |
| Eric Rivals | 3 | 388 | 41.14 |