Article

Free access

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

Authors:

Xin Chen,

Sam Kwong,

Ming LiAuthors Info & Claims

RECOMB '00: Proceedings of the fourth annual international conference on Computational molecular biology

Page 107

https://doi.org/10.1145/332306.332352

Published: 08 April 2000 Publication History

PDF eReader

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.

References

[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).

Crossref

Google Scholar

[2]

Fitz-Gibbon, $.T & House, C H., Whole genome-bases phylogeny analysis of free-living microorganisms, Nucleic Acids Res. 27(21) 4218-22 (1999).

Crossref

Google Scholar

[3]

Grumbach, S & Tahi, F., A new challenge for compression algorithms' genetic sequences. Journal of Information Processin~ and Management, 30:6(1994), 875-866

Digital Library

Google Scholar

[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

Digital Library

Google Scholar

[6]

Nadeau, J.H. & Sankoff, D., Trends Genet. 14,495 (1998).

Crossref

Google Scholar

[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, 1995

Google Scholar

[8]

$net, B, Bork, P, & Huynen, M.A., Genome phylogeny based on gene content, Nature Genetics 21, (1999)

Google Scholar

Cited By

View all

Munagala NAmanchi PBalasubramanian KPanicker ANagaraj N(2022)Compression-Complexity Measures for Analysis and Classification of CoronavirusesEntropy10.3390/e2501008125:1(81)Online publication date: 31-Dec-2022
https://doi.org/10.3390/e25010081
Dyke Parunak H(2022)A Grammar-Based Behavioral Distance Measure Between Ransomware VariantsIEEE Transactions on Computational Social Systems10.1109/TCSS.2021.30609729:1(8-17)Online publication date: Feb-2022
https://doi.org/10.1109/TCSS.2021.3060972
Gilmary RG M(2021)Bit Reduction based Compression Algorithm for DNA SequencesInternational Journal of Scientific Research in Science, Engineering and Technology10.32628/IJSRSET218529(270-277)Online publication date: 16-Oct-2021
https://doi.org/10.32628/IJSRSET218529
Show More Cited By

A compression algorithm for DNA sequences and its applications in genome comparison
1. Applied computing
  1. Life and medical sciences

Recommendations

Identification of human-specific transcript variants induced by DNA insertions in the human genome

Motivation: Many genes in the human genome produce a wide variety of transcript variants resulting from alternative exon splicing, differential promoter usage, or altered polyadenylation site utilization that may function differently in human cells. ...
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 ...
Genome-wide DNA sequence polymorphisms facilitate nucleosome positioning in yeast

Motivation: The intrinsic DNA sequence is an important determinant of nucleosome positioning. Some DNA sequence patterns can facilitate nucleosome formation, while others can inhibit nucleosome formation. Nucleosome positioning influences the overall ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

RECOMB '00: Proceedings of the fourth annual international conference on Computational molecular biology

April 2000

329 pages

ISBN:1581131860

DOI:10.1145/332306

Editors:
Ron Shamir
Tel-Aviv Univ., Israel
,
Satoru Miyano
Univ. of Tokyo, Tokyo, Japan
,
Sorin Istrail
Sandia National Labs
,
Pavel Pevzner
Univ. of Southern California
,
Michael Waterman
Univ. of Southern California

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 08 April 2000

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

RECOMB00

Sponsor:

SIGACT

RECOMB00: The Fourth Annual International Conference on Computational Molecular Biology

Tokyo, Japan

Acceptance Rates

Overall Acceptance Rate 148 of 538 submissions, 28%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

76
Total Citations
View Citations
1,214
Total Downloads

Downloads (Last 12 months)79
Downloads (Last 6 weeks)10

Reflects downloads up to 12 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Munagala NAmanchi PBalasubramanian KPanicker ANagaraj N(2022)Compression-Complexity Measures for Analysis and Classification of CoronavirusesEntropy10.3390/e2501008125:1(81)Online publication date: 31-Dec-2022
https://doi.org/10.3390/e25010081
Dyke Parunak H(2022)A Grammar-Based Behavioral Distance Measure Between Ransomware VariantsIEEE Transactions on Computational Social Systems10.1109/TCSS.2021.30609729:1(8-17)Online publication date: Feb-2022
https://doi.org/10.1109/TCSS.2021.3060972
Gilmary RG M(2021)Bit Reduction based Compression Algorithm for DNA SequencesInternational Journal of Scientific Research in Science, Engineering and Technology10.32628/IJSRSET218529(270-277)Online publication date: 16-Oct-2021
https://doi.org/10.32628/IJSRSET218529
Machado JRocha-Neves JAzevedo FAndrade J(2021)Advances in the computational analysis of SARS-COV2 genomeNonlinear Dynamics10.1007/s11071-021-06836-y106:2(1525-1555)Online publication date: 27-Aug-2021
https://doi.org/10.1007/s11071-021-06836-y
Kumar S(2021)Trends and Advancements in Genome Data Compression and Processing AlgorithmsSoft Computing: Theories and Applications10.1007/978-981-16-1696-9_15(163-170)Online publication date: 27-Jun-2021
https://doi.org/10.1007/978-981-16-1696-9_15
Perera WWannige C(2019)Modified Algorithm for Phylogenetic Tree Construction using Ant Colony Optimization2019 19th International Conference on Advances in ICT for Emerging Regions (ICTer)10.1109/ICTer48817.2019.9023716(1-7)Online publication date: Sep-2019
https://doi.org/10.1109/ICTer48817.2019.9023716
Absardi ZJavidan R(2019)A Fast Reference-Free Genome Compression Using Deep Neural Networks2019 Big Data, Knowledge and Control Systems Engineering (BdKCSE)10.1109/BdKCSE48644.2019.9010661(1-7)Online publication date: Nov-2019
https://doi.org/10.1109/BdKCSE48644.2019.9010661
Law B(2019)Application of signal processing for DNA sequence compressionIET Signal Processing10.1049/iet-spr.2018.5392Online publication date: 23-May-2019
https://doi.org/10.1049/iet-spr.2018.5392
Pocheville A(2018)Biological Information as Choice and ConstructionPhilosophy of Science10.1086/69983285:5(1012-1025)Online publication date: Dec-2018
https://doi.org/10.1086/699832
Seker ADelibas EDiri B(2017)DNA sequence compression within traditional text compression algorithms2017 25th Signal Processing and Communications Applications Conference (SIU)10.1109/SIU.2017.7960193(1-4)Online publication date: May-2017
https://doi.org/10.1109/SIU.2017.7960193
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Recommendations

Identification of human-specific transcript variants induced by DNA insertions in the human genome

DNA clustering and genome complexity

Genome-wide DNA sequence polymorphisms facilitate nucleosome positioning in yeast