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 |
Year | Venue | Keywords |
---|---|---|
1998 | German Conference on Bioinformatics | minimum description length,point mutation |
Field | DocType | Citations |
Combinatorics,Theoretical computer science,Genetics,Mathematics | Conference | 13 |
PageRank | References | Authors |
7.52 | 0 | 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 |