Title :
A guaranteed compression scheme for repetitive DNA sequences
Author :
Rivals, E. ; Delahaye, J.-P. ; Dauchet, M. ; Delgrange, O.
Author_Institution :
Lab. d´´Inf. Fondamentale, Lille I Univ., Villeneuve d´´Ascq, France
Abstract :
We present a text compression scheme dedicated to DNA sequences. The exponential growing of the number of sequences creates a real need for analyzing tools. A specific need emerges for methods that perform sequences classification upon various criteria, one of which is the sequence repetitiveness. A good lossless compression scheme is able to distinguish between “random” and “significative” repeats. Theoretical bases for this statement are found in Kolmogorov complexity theory
Keywords :
DNA; computational complexity; data compression; medical signal processing; pattern classification; random processes; Kolmogorov complexity theory; guaranteed compression scheme; lossless compression scheme; random repeats; repetitive DNA sequences; sequence repetitiveness; sequences classification; significative repeats; text compression; Biological information theory; Complexity theory; DNA; Dictionaries; Encoding; Sequences; Sufficient conditions; Tree data structures;
Conference_Titel :
Data Compression Conference, 1996. DCC '96. Proceedings
Conference_Location :
Snowbird, UT
Print_ISBN :
0-8186-7358-3
DOI :
10.1109/DCC.1996.488385
