A compression algorithm for DNA sequences and its applications in genome comparison

By Xin Chen, Sam Kwong, Ming Li. Annual International Conference on Research in Computational Molecular Biology, 2000

299 citations recorded by the source corpus.

We present a lossless compression algorithm, <italic>Gen-Compress</italic>, 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 <italic>d</italic>(<italic>x</italic>, <italic>y</italic>) = 1 — <italic>K</italic>(<italic>x</italic>) - <italic>K</italic>(<italic>x</italic>|<italic>y</italic>)/<italic>K</italic>(<italic>xy</italic> to measure the distance of any two sequences, where <italic>K</italic> stands for Kolmogorov complexity [5]. Here, <italic>K</italic>(<italic>x</italic>) - <italic>K</italic>(<italic>x</italic>|<italic>y</italic>) is the mutual information shared by <italic>x</italic> and <italic>y</italic>. But mutual information is not a distance, there is no triangle inequality. The distance <italic>d</italic>(<italic>x</italic>, <italic>y</italic>) 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 <italic>GenCompress</italic> 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.

Subfields: Artificial Intelligence, Genetics, Molecular Biology

View Paper: https://www.semanticscholar.org/paper/1d235873bdf24fe813af9ec4047924e44fc78a52

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Genetics

In Molecular Biology

Citations in the corpus

Time-series data mining (2012, methodology): “Similar approaches have been undertaken earlier in bioinformatics [Chen et al. 2000] and several compression techniques such as the Lempel-Ziv complexity [Otu and Sayood 2003] have been successfully applied to compute similarity between biological sequences.”
The similarity metric (2001, methodology): “Preliminary applications of the current approach were tentatively reported to the biological community and elsewhere [11], [31], [35].”
RNACompress: Grammar-based compression and informational complexity measurement of RNA secondary structure (2008, methodology): “Algorithms for compressing DNA sequences include GenCompress [13], DNACompress [14], Biocompress [15] and Cfact [16].”
Shared information and program plagiarism detection (2004, methodology): “It is possible to extend the theory to allow SID to handle the common code given by the professor by defining a conditional shared information distance d(x; yjProfessorCode) using the conditional Kolmogorov complexity.”
Causal Inference Using the Algorithmic Markov Condition (2008, methodology): “Compression algorithms have already been developed that are intended to approximate, for instance, the algorithmic information of genetic sequences [49], [50].”
Alignment-free sequence comparison-a review (2003, methodology): “In that report (Li et al., 2001), sequence compression is performed using the GenCompress software program (Chen et al., 1999), empirically assessing the Kolmogorov complexity, K (X), of a sequence, X by the length of its compressed representation.”
Fast-Find: A novel computational approach to analyzing combinatorial motifs (2006, methodology): “This type of 2-bit encoding has been widely used elsewhere (see for example, [19]).”
Towards parameter-free data mining (2004, methodology): “We took the first 16,300 symbols from the mitochondrial DNA of twelve primates and one “outlier” species, and hierarchically clustered them.”