On the entropy of DNA: Algorithms and measurements based on memory and rapid convergence

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

Martin Farach, Michiel Noordewier, Serap Savari, Larry Shepp, Abraham Wyner, Jacob Ziv

School of Arts and Sciences, Computer Science

Rutgers, The State University

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

61 Scopus citations

Abstract

We have applied the information theoretic notion of entropy to characterize DNA sequences. We consider a genetic sequence signal that is too small for asymptotic entropy estimates to be accurate, and for which similar approaches have previously failed. We prove that the match length entropy estimator has a relatively fast converge rate and demonstrate experimentally that by using this entropy estimator, we can indeed extract a meaningful signal from segments of DNA. Further, we derive a method for detecting certain signals within DNA - known as splice junctions - with significantly better performance than previously known methods. The main result of this paper is that we find that the entropy of genetic material which is ultimately expressed in protein sequences is higher than that which is discarded. This is an unexpected result, since current biological theory holds that the discarded sequences ("introns") are capable of tolerating random changes to a greater degree than the retained sequences ("exons").

Original language	English (US)
Title of host publication	Proceedings of the 6th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1995
Publisher	Association for Computing Machinery
Pages	48-57
Number of pages	10
ISBN (Electronic)	0898713498
State	Published - Jan 22 1995
Event	6th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1995 - San Francisco, United States Duration: Jan 22 1995 → Jan 24 1995

Publication series

Name	Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

Conference

Conference	6th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1995
Country/Territory	United States
City	San Francisco
Period	1/22/95 → 1/24/95

ASJC Scopus subject areas

Software
Mathematics(all)

Cite this

Farach, M., Noordewier, M., Savari, S., Shepp, L., Wyner, A., & Ziv, J. (1995). On the entropy of DNA: Algorithms and measurements based on memory and rapid convergence. In Proceedings of the 6th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1995 (pp. 48-57). (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms). Association for Computing Machinery.

@inproceedings{6602a8307e4d48b281953b5852e961f1,

title = "On the entropy of DNA: Algorithms and measurements based on memory and rapid convergence",

abstract = "We have applied the information theoretic notion of entropy to characterize DNA sequences. We consider a genetic sequence signal that is too small for asymptotic entropy estimates to be accurate, and for which similar approaches have previously failed. We prove that the match length entropy estimator has a relatively fast converge rate and demonstrate experimentally that by using this entropy estimator, we can indeed extract a meaningful signal from segments of DNA. Further, we derive a method for detecting certain signals within DNA - known as splice junctions - with significantly better performance than previously known methods. The main result of this paper is that we find that the entropy of genetic material which is ultimately expressed in protein sequences is higher than that which is discarded. This is an unexpected result, since current biological theory holds that the discarded sequences ({"}introns{"}) are capable of tolerating random changes to a greater degree than the retained sequences ({"}exons{"}).",

author = "Martin Farach and Michiel Noordewier and Serap Savari and Larry Shepp and Abraham Wyner and Jacob Ziv",

note = "Funding Information: Supported by DIMACS (Center for Discrete Mathematics and Theoretical Computer Science), a National Science Foundation Science and Technology Center under NSF contract STC-8809648. Funding Information: 'fu.cWc,.rotg~r8.odu;Supportedby DIMACS (Centerfor Discrete Mathematics aud Theoretical Computer Science), a National Science Foundation Science and Technology Center under NSF contract STC-8809648. ! noordowi~cs.rotgors.odu *,yskit.tdu qlasQresarch.att.com Il.j.Opl.~.ir.8turiord.odu; 6th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1995 ; Conference date: 22-01-1995 Through 24-01-1995",

year = "1995",

month = jan,

day = "22",

language = "English (US)",

series = "Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms",

publisher = "Association for Computing Machinery",

pages = "48--57",

booktitle = "Proceedings of the 6th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1995",

}

Farach, M, Noordewier, M, Savari, S, Shepp, L, Wyner, A & Ziv, J 1995, On the entropy of DNA: Algorithms and measurements based on memory and rapid convergence. in Proceedings of the 6th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1995. Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, Association for Computing Machinery, pp. 48-57, 6th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1995, San Francisco, United States, 1/22/95.

On the entropy of DNA: Algorithms and measurements based on memory and rapid convergence. / Farach, Martin; Noordewier, Michiel; Savari, Serap et al.
Proceedings of the 6th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1995. Association for Computing Machinery, 1995. p. 48-57 (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - On the entropy of DNA

T2 - 6th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1995

AU - Farach, Martin

AU - Noordewier, Michiel

AU - Savari, Serap

AU - Shepp, Larry

AU - Wyner, Abraham

AU - Ziv, Jacob

N1 - Funding Information: Supported by DIMACS (Center for Discrete Mathematics and Theoretical Computer Science), a National Science Foundation Science and Technology Center under NSF contract STC-8809648. Funding Information: 'fu.cWc,.rotg~r8.odu;Supportedby DIMACS (Centerfor Discrete Mathematics aud Theoretical Computer Science), a National Science Foundation Science and Technology Center under NSF contract STC-8809648. ! noordowi~cs.rotgors.odu *,yskit.tdu qlasQresarch.att.com Il.j.Opl.~.ir.8turiord.odu

PY - 1995/1/22

Y1 - 1995/1/22

N2 - We have applied the information theoretic notion of entropy to characterize DNA sequences. We consider a genetic sequence signal that is too small for asymptotic entropy estimates to be accurate, and for which similar approaches have previously failed. We prove that the match length entropy estimator has a relatively fast converge rate and demonstrate experimentally that by using this entropy estimator, we can indeed extract a meaningful signal from segments of DNA. Further, we derive a method for detecting certain signals within DNA - known as splice junctions - with significantly better performance than previously known methods. The main result of this paper is that we find that the entropy of genetic material which is ultimately expressed in protein sequences is higher than that which is discarded. This is an unexpected result, since current biological theory holds that the discarded sequences ("introns") are capable of tolerating random changes to a greater degree than the retained sequences ("exons").

AB - We have applied the information theoretic notion of entropy to characterize DNA sequences. We consider a genetic sequence signal that is too small for asymptotic entropy estimates to be accurate, and for which similar approaches have previously failed. We prove that the match length entropy estimator has a relatively fast converge rate and demonstrate experimentally that by using this entropy estimator, we can indeed extract a meaningful signal from segments of DNA. Further, we derive a method for detecting certain signals within DNA - known as splice junctions - with significantly better performance than previously known methods. The main result of this paper is that we find that the entropy of genetic material which is ultimately expressed in protein sequences is higher than that which is discarded. This is an unexpected result, since current biological theory holds that the discarded sequences ("introns") are capable of tolerating random changes to a greater degree than the retained sequences ("exons").

UR - http://www.scopus.com/inward/record.url?scp=84994364597&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84994364597&partnerID=8YFLogxK

M3 - Conference contribution

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 48

EP - 57

BT - Proceedings of the 6th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1995

PB - Association for Computing Machinery

Y2 - 22 January 1995 through 24 January 1995

ER -

On the entropy of DNA: Algorithms and measurements based on memory and rapid convergence

Abstract

Publication series

Conference

ASJC Scopus subject areas

Other files and links

Fingerprint

Cite this