Location of repetitive regions in sequences by optimizing a compression method.
Suppose that a biologist wishes to study some local property P of genetic sequences. If he can design (with a computer scientist) an algorithm C which efficiently compresses parts of the sequence which satisfy P, then our algorithm TurboOptLift locates very quickly where property P occurs by chance on a sequence, and where it occurs as a result of a significant process. Under some conditions, the time complexity of TurboOptLift is O(n log n). We illustrate its use on the practical problem of locating approximate tandem repeats in DNA sequences.
Delgrange
O
O
Université de Mons-Hainaut, Mons, Belgique. Olivier.Delgrange@umh.ac.be
Dauchet
M
M
Rivals
E
E
D000465:Algorithms; D001483:Base Sequence; D019295:Computational Biology / Q000379:methods; D003198:Computer Simulation; D003205:Computing Methodologies; D004247:DNA / Q000737:chemistry* / Q000235:genetics; D012091:Repetitive Sequences, Nucleic Acid; D016415:Sequence Alignment; D012984:Software
D004247:DNA