Fast Discerning Repeats in DNA Sequences with a Compression Algorithm
Éric Rivals, Max Dauchet, Jean-paul Delahaye, Olivier Delgrange · 1997
Long direct repeats in genomes arise from molecular duplication mechanisms like retrotransposition, copy of genes, exon shuffling, . . . Their study in a given sequence reveals its internal repeat structure as well as part of its evolutionary history. Moreover, detailed knowledge about the mechanisms can be gained from a systematic investigation of repeats. The problem of finding such repeats is viewed as an NP-complete problem of the optimal compression of a sequence thanks to the encoding of its exact repeats. The repeats chosen for compression must not overlap each other as do the repeats which result from molecular duplications. We present a new heuristic algorithm where the selection of repeats is guided by two biologically sound criteria: their length and the absence of overlap between those repeats. Search Repeats allows to detect approximate repeat, as clusters of exact sub-repeats and to point out large insertions/deletions in them. Search Repeats takes only 3 second...