An efficient normalized maximum likelihood algorithm for DNA sequence compression

ABSTRACT

This article presents an efficient algorithm for DNA sequence compression, which achieves the best compression ratios reported over a test set commonly used for evaluating DNA compression programs. The algorithm introduces many refinements to a compression method that combines: (1) encoding by a simple normalized maximum likelihood (NML) model for discrete regression, through reference to preceding approximate matching blocks, (2) encoding by a first order context coding and (3) representing strings in clear, to make efficient use of the redundancy sources in DNA data, under fast execution times. One of the main algorithmic features is the constraint on the matching blocks to include reasonably long contiguous matches, which not only reduces significantly the search time, but also can be used to modify the NML model to exploit the constraint for getting smaller code lengths. The algorithm handles the changing statistics of DNA data in an adaptive way and by predictively encoding the matching pointers it is successful in compressing long approximate matches. Apart from comparison with previous DNA encoding methods, we present compression results for the recently published human genome data.

REFERENCES

• 1: Don Adjeroh , Yong Zhang , Amar Mukherjee , Matt Powell , Tim Bell, DNA Sequence Compression Using the Burrows-Wheeler Transform, Proceedings of the IEEE Computer Society Conference on Bioinformatics, p.303, August 14-16, 2002
• 2: Altschul, S., Gish, W., Miller, W., Myers, E., and Lipman, D. 1990. Basic local alignment search tool. J. Mol. Biol. 215, 403--410.
• 3: Chen, X., Kwong, S., and Li, M. 2001. A compression algorithm for DNA sequences. IEEE Engineering in Medicine and Biology. 61--66.
• 4: Chen, X., Li, M., Ma, B., and Tromp, J. 2002. DNACompress: fast and effective DNA sequence compression. Bioinformatics 18, 1696--1698.
• 5: Grumbach, S. and Tahi, F. 1993. Compression of DNA sequences. In Proceedings of the Data Compression Conference. 340--350.
• 6: Stéphane Grumbach , Fariza Tahi, A new challenge for compression algorithms: genetic sequences, Information Processing and Management: an International Journal, v.30 n.6, p.875-886, 1994 [doi>10.1016/0306-4573(94)90014-0]
• 7: J. Kevin Lanctot , Ming Li , En-hui Yang, Estimating DNA sequence entropy, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.409-418, January 09-11, 2000, San Francisco, California, United States
• 8: Li, M., Badger, J., Chen, X., Kwong, S., Kearney, P., and Zhang, H. 2001. An information based sequence distance and its application to whole mitochondrial genome phylogeny. Bioinformatics 17, 149--154.
• 9: Ming Li , Xin Chen , Xin Li , Bin Ma , Paul Vitányi, The similarity metric, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 10: David Loewenstern , Peter N. Yianilos, Significantly Lower Entropy Estimates for Natural DNA Sequences, Proceedings of the Conference on Data Compression, p.151, March 25-27, 1997
• 11: Ma, B., Tromp, J., and Li, M. 2002. PatternHunter: Faster and more sensitive homology search. Bioinformatics 18, 440--445.
• 12: Matsumoto, T., Sadakane, K., and Imai, H. 2000. Biological sequence compression algorithms. In Genome Informatics Workshop. Universal Academy Press, 43--52.
• 13: Pearson, W. and Lipman, D. 1988. Improved tools for biological sequence comparison. In Proc. Natl. Acad. Sci. USA. Vol. 85. 2444--2448.
• 14: Rissanen, J. 1976. Generalized Kraft inequality and arithmetic coding. IBM J. Res. Dev. 20, 3, 198--203.
• 15: Rivals, E., Delahaye, J., Dauchet, M., and Delgrange, O. 1995. A guaranteed compression scheme for repetitive DNA sequences. Tech. Rep. IT--285, LIFL Lille I Univ.
• 16: Ioan Tabus , Gergely Korodi , Jorma Rissanen, DNA sequence compression using the normalized maximum likelihood model for discrete regression, Proceedings of the Conference on Data Compression, p.253, March 25-27, 2003
• 17: Ioan Tabus , Jorma Rissanen , Jaakko Astola, Classification and feature gene selection using the normalized maximum likelihood model for discrete regression, Signal Processing, v.83 n.4, p.713-727, April 2003 [doi>10.1016/S0165-1684(02)00470-X]
• 18: Wilbur, W. and Lipman, D. 1983. Rapid similarity searches of nucleic acid and protein data banks. In Proc. Natl. Acad. Sci. USA. Vol. 80. 726--730.
• 19: Williams, H. and Zobel, J. 1997. Compression of nucleotide databases for fast searching. Computer Applications in the Biosciences 13, 5, 549--554.
• 20: Ziv, J. and Lempel, A. 1977. A universal algorithm for sequential data compression. IEEE Trans. Inform. Theory 23, 3, 337--343.

INDEX TERMS

Primary Classification:
  E. Data
  E.4 CODING AND INFORMATION THEORY
      Subjects: Data compaction and compression

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Markov processes; Correlation and regression analysis

  J. Computer Applications
  J.3 LIFE AND MEDICAL SCIENCES
      Subjects: Biology and genetics

General Terms:
Algorithms, Theory

Keywords:
Approximate sequence matching, DNA compression, normalized maximum likelihood model