Estimating DNA sequence entropy

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Estimating DNA sequence entropy

Full text

Pdf (982 KB)

Source

Symposium on Discrete Algorithms archive
Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms table of contents

San Francisco, California, United States

Pages: 409 - 418

Year of Publication: 2000

ISBN:0-89871-453-2

Authors

J. Kevin Lanctot	Dept. of Computer Science, University of Waterloo, Waterloo, Ont. N2L 3G1, Canada
Ming Li	University of Waterloo
En-hui Yang	University of Waterloo

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIAM : Society for Industrial and Applied Mathematics

Publisher

Society for Industrial and Applied Mathematics Philadelphia, PA, USA

Bibliometrics

Downloads (6 Weeks): 8, Downloads (12 Months): 61, Citation Count: 4

Additional Information:

references cited by index terms collaborative colleagues peer to peer

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	BioInformatics Group Homepage, http:// wh .math. uwaterloo, ca.
	2	Martin Farach , Michiel Noordewier , Serap Savari , Larry Shepp , Abraham Wyner , Jacob Ziv, On the entropy of DNA: algorithms and measurements based on memory and rapid convergence, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.48-57, January 22-24, 1995, San Francisco, California, United States
	3	S. Grumbac.h and F. Tahi, Compression of DNA sequences. Proceedings of the IEEE Symposium on Data Compression, 340-350, 1993
	4	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]
	5	Dan Gusfield, Algorithms on strings, trees, and sequences: computer science and computational biology, Cambridge University Press, New York, NY, 1997
	6	John E. Hopcroft , Jeffrey D. Ullman, Introduction To Automata Theory, Languages, And Computation, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
	7	J. Kieffer and E. Yang, Grammar Based Codes: A New Class of Universal Lossless Source Codes, submitted for journal publication.
	8	J. Kieifer and E. Yang, Ergodic Behavior of Graph Entropy, ERA Amer. Math. Society, Vol. 3, no. 1, pp. II-16, 1997.
	9	B. Lewin, Genes VI, Oxford University Press, Oxford, 1997.
	10	P. Lib, A. Politi, M. Buiatti, and S. Ruff'o, High Statistics Block Entropy Measures of DNA Sequences, Journal of Theoretical Biology 180 (1996), 151-160.
	11	D. Loewenstern and P. Yiarfilos, Significantly Lower Entropy Estimates for Natural DNA Sequences, accepted for publication in the Journal of Computational Biology.
	12	National Center for Bioteehnology Information, Entrez Nudeotide Query, http://w~nw.ncbi.nlm.nih, gov/ }atbin-post/Entrez/query?d~--n_s.
	13	A. Schm~tt and H. Herzel, Estimating the Entropy of DNA Sequences, Journal of Theoretical Biology 188 (1997), 369-377.
	14	E. Ukkonen, On-Line Construction of Suffix Trees, Algorithmica 14 (1995) 249-260.
	15	E. Yang and J. Kieifer, Efficient universal lossless compression algorithms based on a greedy sequential grammar transform-Part one: Without context models, to appear in IEEE Trans. In}orrn. Theory.
	16	E. Yaug and J. Kieffer, Universal source coding theory based on grammar transforms, Proc. of the 1999 IEEE Information Theory and Communications Workshop, Kruger National Park, South Africa, June 20-25, pp. 75-77.
	17	P. Yian~los, CDNA source code, http:// www. neci .nj .nee. com/homepages/pny/software/ cdna/main.html.

CITED BY 4

	Gergely Korodi , Ioan Tabus, An efficient normalized maximum likelihood algorithm for DNA sequence compression, ACM Transactions on Information Systems (TOIS), v.23 n.1, p.3-34, January 2005
	Simon Miles , Sylvia C. Wong , Weijian Fang , Paul Groth , Klaus-Peter Zauner , Luc Moreau, Provenance-based validation of e-science experiments, Web Semantics: Science, Services and Agents on the World Wide Web, v.5 n.1, p.28-38, March, 2007
	Wojciech Rytter, Application of Lempel--Ziv factorization to the approximation of grammar-based compression, Theoretical Computer Science, v.302 n.1-3, p.211-222, 13 June 2003
	Gergely Korodi , Ioan Tabus, Compression of Annotated Nucleotide Sequences, IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB), v.4 n.3, p.447-457, July 2007

INDEX TERMS

Primary Classification:
G. Mathematics of Computing
G.2 DISCRETE MATHEMATICS

Additional Classification:
F. Theory of Computation
F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
F.2.2 Nonnumerical Algorithms and Problems
Subjects: Computations on discrete structures
F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES

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

General Terms:
Algorithms, Design, Human Factors, Measurement, Performance, Theory, Verification

Collaborative Colleagues:

J. Kevin Lanctot: colleagues

Ming Li: colleagues

En-hui Yang: colleagues

Peer to Peer - Readers of this Article have also read:

Constructing reality Proceedings of the 11th annual international conference on Systems documentation
Douglas A. Powell , Norman R. Ball , Mansel W. Griffiths
Data structures for quadtree approximation and compression Communications of the ACM 28, 9
Hanan Samet
A hierarchical single-key-lock access control using the Chinese remainder theorem Proceedings of the 1992 ACM/SIGAPP Symposium on Applied computing
Kim S. Lee , Huizhu Lu , D. D. Fisher
An intelligent component database for behavioral synthesis Proceedings of the 27th ACM/IEEE Design Automation Conference on
Gwo-Dong Chen , Daniel D. Gajski
The GemStone object database management system Communications of the ACM 34, 10
Paul Butterworth , Allen Otis , Jacob Stein

Adobe Acrobat

QuickTime

Windows Media Player

Real Player