Xin Chen
Ming Li
ABSTRACT
We present a lossless compression algorithm, Gen-Compress, for DNA sequences, based on searching for approximate repeats. Our algorithm achieves the best compression ratios for benchmark DNA sequences, comparing to other DNA compression programs [3, 7]. Significantly better compression results show that the approximate repeats are one of the main hidden regularities in DNA sequences.
We then describe a theory of measuring the relatedness between two DNA sequences. We propose to use d(x, y) = 1 — K(x) - K(x|y)/K(xy to measure the distance of any two sequences, where K stands for Kolmogorov complexity [5]. Here, K(x) - K(x|y) is the mutual information shared by x and y. But mutual information is not a distance, there is no triangle inequality. The distance d(x, y) is symmetric. It also satisfies the triangle inequality, and furthermore, it is universal [4].
It has not escaped our notice that the distance measure we have postulated can be immediately used to construct evolutionary trees from DNA sequences, especially those that cannot be aligned, such as complete genomes. With more and more genomes sequenced, constructing trees from genomes becomes possible [1, 2, 6, 8]. Kolmogorov complexity is not computable. We use GenCompress to approximate it. We present strong experimental support for this theory, and demonstrate its applicability by correctly constructing a 16S (18S) rRNA tree, and a whole genome tree for several species of bacteria. Larger scale experiments are underway at the University of Waterloo, with very promising results.
- 1.!goore, J L. &. Brown, W.M., Big trees from tittle genomes mitochondrial gene order as a phylogenetic tool. Curt. Opin. Genet. Dev. 8(6), 668-74 (1998).Google Scholar
Cross Ref
- 2.Fitz-Gibbon, $.T & House, C H., Whole genome-bases phylogeny analysis of free-living microorganisms, Nucleic Acids Res. 27(21) 4218-22 (1999).Google ScholarCross Ref
- 3.Grumbach, S & Tahi, F., A new challenge for compression algorithms' genetic sequences. Journal of Information Processin~ and Management, 30:6(1994), 875-866 Google ScholarDigital Library
- 4.Li, M. Notes, 1999.Google Scholar
- 5.Li, M & Vit~nyi, P., An introduction to Kolmogoro~ coraplc~tSl and ~ta applications, $prJnger-Verlag, 1997 Google ScholarDigital Library
- 6.Nadeau, J.H. & Sankoff, D., Trends Genet. 14,495 (1998).Google ScholarCross Ref
- 7.i~_, Rivals, J-P Delahaye, M. {)auchet and O. Delgrange A Guaranteed Compression Scheme for Repetitive DNA Sequences LiFL Lille I Univ. tech. report IT-285, 1995Google Scholar
- 8.$net, B, Bork, P, & Huynen, M.A., Genome phylogeny based on gene content, Nature Genetics 21, (1999)Google Scholar
- A compression algorithm for DNA sequences and its applications in genome comparison
Recommendations
DNA clustering and genome complexity
Early global measures of genome complexity (power spectra, the analysis of fluctuations in DNA walks or compositional segmentation) uncovered a high degree of complexity in eukaryotic genome sequences. The main evolutionary mechanisms leading to ...
Comments