Information Content Using Different Contexts

1. e.g.1, e.g.2,
2. entropy,
3. arithmetic coding,
4. multinomial distribution,
5. LZ / ZL,
6. PPM prediction by partial match,
7. with mismatches,
8. the approximate repeats model (ARM),
9. the eXpert Model (XM),
10. contexts and difference plots (HBV), and
11. references.

Why compress biological sequences?

 

Not to save disc space (at least not yet^[*]) --

 

savings are <20%± for DNA, maybe <10%± protein.

 

The reason is the strong connection of compression to modelling:

 

Good compression <=> good model.

 

To discover pattern, structure, hypotheses.

 

 

(^[*]Although when several sequences are close relatives, then compression can give significant space savings.)

E.g.₁, assuming

 

pr(A) = pr(C) = pr(G) = pr(T) = 1/4,

 

- log₂(1/4) = +log₂(4) = 2 bits

 

A -> 00₂; C -> 01₂; G -> 10₂; T -> 11₂; is optimal.

 

Expected code length = 1/4×2 + 1/4×2+ 1/4×2+ 1/4×2 = 2 bits/symbol

E.g.₂, assuming

 

pr(A) = 1/2; pr(C) = 1/4; pr(G) = pr(T) = 1/8,

 

(Note 1/2 + 1/4 + 1/8 + 1/8 = 1)

 

- log₂(1/2) = 1; - log₂(1/4) = 2; - log₂(1/8) = 3

 

A -> 0₂; C -> 10₂; G -> 110₂; T -> 111₂; is optimal.

 

Expected code length = 1/2×1 + 1/4×2+ 1/8×3+ 1/8×3 = 1 ³/₄ bits/symbol

Entropy

 

- E_x log(pr(x)) = ∑_x:X - pr(x) . log(pr(x)),

 

which depends in pr( ) . . . Do you have the true model?

 

In sequences, pr( ) can be context dependent, have pr(x_i | x_1..i-1).

 

The entropy gives a lower limit for compression per symbol -- can't beat it on average.

 

 

BTW, Kullback Leibler distance,

KL(pr₁(),pr₂()) = ∑_x:X pr₁(x).{ - log(pr₂(x)) + log(pr₁(x)) }, ≥ 0.

. . .

. . . entropy

 

note, "the" entropy is essentially unknowable

 

unless you fix on one model for some reason

 

(but what is the "true" model for real data?).

 

Actual compression also depends on what is known (context, background knowledge, common knowledge)

 

but entropy is still a useful abstract concept.

 

. . .

. . . entropy, & coding v. stats.

 

Q: So if code_length = - log( probability )  (& probability = e^{- code_length}),  is that "all"?

 

A: yes and no:

 

Coding keeps us "honest":

every parameter (unless common knowledge) must be transmitted (at optimum precision).

 

There are many useful techniques & heuristics from file compression that do not corr. to any obvious "classical" statistical model.

Arithmetic coding

 

can get arbitrarily close to the theoretical lower limit

(the entropy of the data)

in bits per symbol, e.g., [Lan84],

 

provided it is given a good model of the data.

 

Hence

"Compression = Modelling + Coding",

 

and coding is now "solved", so . . .

 

a data compressor is as good, or bad, as its model.

 

 

NB. AC is capable of coding a symbol in fractions of a bit!

Multinomial distribution

 

e.g., α = {H,T}, or {A,C,G,T}, or {amino-acids}, etc.

 

1. combinatorial code,
2. adaptive code,
3. θ + data|θ.

 

code1 = code2

= log(|data|+|α|-1)! - log(|α|-1)! - log(#α₁)! - ... - log(#α_|α|)!,

 

code3 = code1 + (|α|-1) × a fraction of a bit per parameter,

provided θ is stated to optimum precision [BW69],

 

e.g., [click].

 

. . .

. . . multinomial

 

NB. DNA

order_0:   3 parameters,

order_1: 12 parameters  (four × 4-nomials),

etc.

 

and protein

order_0:   19 parameters,

order_1: 380 parameters  (20 × 20-nomials)

etc.

 

unless some structure (restriction) is imposed on models.

LZ [LZ76, ZL77]

 

very influential in text (file) compression,

 

two approaches:

 

build a header (dictionary) of repeated sub-strings,

replace each instance with a pointer-code into dictionary,

 

or

replace a repeated instance with

<escape code, pointer to 1st instance, length>.

 

And a nice quote:

"Roughly speaking, the complexity of a finite fully specified sequence is a measure of the extent to which the given sequence resembles a random one." --p.75 [LZ76]

 

. . .

. . . PPM [CW84]

 

is an LZ-inspired text compression algorithm which

 

builds a tree of contexts ("frequent" substrings). It consists of methods of

 

growing the tree,

 

gathering stats. per context, and

 

weighting predictions from short frequent contexts v. long infrequent ones.

 

. . .

. . . LZ & PPM, with mismatches [LY96] for Biol..

 

Repeats are exact in LZ and PPM.

 

[LY96] allowed some mismatches against a context;

 

must descend 4 × as many subtrees per mismatche per position,

 

must blend predictions from exact v. 1-mismatch v. 2-mismatches v. ... etc.,

 

as well as predictions from long v. short contexts which

 

is controlled by "several" parameters, to be estimated.

The Approximate Repeats Model (ARM) [AED98]

 

(or similar)

. . .

. . . ARM

 

ARM is simple (has few parameters),

 

its parameters relate directly to useful concepts (frequency, length, fidelity),

 

inspired by Ziv-Lempel [LZ76, ZL77], copies but now with mutations,

 

can think of ARM as

 

~ some base_model + some alignment_model.

 

. . .

. . . ARM

 

 

can make an ARM out of potentially any (self-)alignment model, and

 

any base model --

 

even another copy of ARM.

 

(And note that in modelling alignment the generic DPA is extended by adding a compression model parameter, e.g., ARM.-)

 

. . .

. . . ARM

 

1. "base model" for background properties/statistics;

 

2. param for frequency of copies,

 

change- & indel-params for fidelity of copies, and

 

param for length of copies

 

(more frequent, more faithful, longer => more compression).

 

Similarly for 'reverse-complementary' repeats, & can augment to model 'longer but less frequent' repeats, say.

 

. . .

. . . ARM & an information theory interpretation

 

 

as in local alignment (but here against self) an optimal path is a hypothesis,

. . .

. . . ARM

 

can search for an optimal one of these hypothesis, but

 

any two such hypotheses are exclusive so,

 

as in alignment, we can sum all their probabilities,

 

in O( |s|² )-time.

 

For  l o n g  seqs., ∃ a faster approximation algorithm (& also see the [XM]).

. . .

. . . ARM

 

[example-R] is [random], |s|=100,

 

base-line = 200^* bits (2 b/sym)

 

order_0 Markov Model,

hypothesis (H) = 8.2, data (D|H) = 197.4, total = 205.6 bits (2.06 b/sym)

 

order_1 Markov Model,

H = 21.1, D|H = 191.0 (exc. H), total = 212.1 bits (2.12 b/sym)

 

ARM,

H = 31.6, D|H = 191.1, total = 222.7 bits (2.23 b/sym)

. . .

. . . ARM

 

[example-NR] is [non-random], |s|=128,

 

base-line = 256 bits (2 b/sym)

 

order_0 Markov Model,

H = 10, D|H = 211, total = 221 bits (1.73 b/sym)

 

order_1 Markov Model,

H = 30, D|H = 152.1, total = 182.2 bits (1.42 b/sym)

 

ARM,

hypothesis (H) = 49.5, data (D|H) = 128.5, total = 178.0^* bits (1.39 b/sym)

The eXpert Model (XM) [CDA07]

 

A blend of "expert" opinions:

 

Markov expert(s) for background "local" stats.,

 

copy experts,

 

reverse complementary copy experts.

 

Bayesian blending is based on ests. of posterior probs.

 

. . .

. . . expert model

 

the key parts of the algorithm:

 

1. the kinds of individual "experts",
   
   
2. blending the expert opinions,
   
   
3. proposing and selecting (good) copy experts
   
    

   crucial to algorithmic efficiency,

   too many => quadratic complexity,

   too few => poor compression.

. . . XM on DNA (bits/sym), e.g.,

 

	BioC	GenC	DNAC	DNAP	CDNA	ARM	XM
HUMHBB	1.88	1.82	1.79	1.78	1.77	1.73	1.75

 

and XM on a proteome (bits/sym), e.g.,

 

	CP	ProtComp	LZ-CTW	XM
SC, Sacharomyces Cerevisiae	4.15	3.94	3.95	3.89

 

more . . .

Contexts and difference plots [DPA07]

 

info(S | cntxt1) - info(S | cntx2),   --per element,

 

shows what new information cntx2 gives about S, and where;

ignores "background" already known from S or cntxt1.

 

Requires a fast compression alg., such as XM,

 

1-D plots take linear space, feasible for large genomes,

 

smoothing, zoom, difference, threshhold, take linear-time, feasible for large genomes,

 

examples . . .

 

. . . a small example, hepatitis B [HBV], xm --hs=2

1.98 b/sym   human;

1.36 b/sym   human | woollyMonkey;

1.84 b/sym   human | woodChuck;

1.96 b/sym   human | duck;

<----720 pixels---->

0-900; smoothed w=21; top human HBV; blue=saving|w.monkey; brown=saving|woodchuck; green=saving|duck [larger]; note 200-300

800-1600

1600-2400

2400-end (~3200)

. . ., e.g., [HBV]

<----1600 pixels---->

0-900; smoothed w=21; top human HBV; blue=saving|w.monkey; brown=saving|woodchuck; green=saving|duck; note 200-300.

[Larger 800-1600, 1600-2400, and 2400-end [here].]

Thanks, in αβ-ical order to

 

Julie Bernal, Minh Duc Cao, Trevor Dix, Tim Edgoose, Samira Jaeger, Chris Mears, David Powell, Linda Stern, Chris Wallace, and Chut N. Yee.

 

 

References

 

[AZM02] D. Adjeroh, Y. Zhang, A. Mukherjee, M. Powell, T. Bell, DNA sequence compression using the Burrows-Wheeler transform,

IEEE Computer Soc. Conf. on Bioinformatics, pp.303, 2002.

[AED98] L. Allison, T. Edgoose, T. I. Dix, Compression of Strings with Approximate Repeats,

Intelligent Systems in Molec. Biol. (ISMB'98), pp.8-16, June 1998 [more]

"... a repeated substring can be an approximate match to the original substring; this is close to the situation of DNA ... a faster approximation alg. is also given. The model is further extended to include approximate reverse complementary repeats when analyzing DNA strings."

[ASE00] L. Allison, L. Stern, T. Edgoose, T. I. Dix, Sequence complexity for biological sequence analysis,

Comp. Biol. & Chem (was Comp. & Chem.), 24(1), pp.43-55, 2000, doi:10.1016/S0097-8485(00)80006-6 [more].

A model which relates directly to biological concepts and knowledge, and gives good compression of DNA sequences.

[AL00] A. Apostolico, S. Lonardi, Compression of biological sequences by greedy off-line textual substitution,

Proc. IEEE Data Compression Conf., pp.143-152, 2000.

[BF05] B. Behzadi, F. L. Fessant, DNA compression challenge revisited: A dynamic programming approach,

CPM, pp.190-200, 2005.

[BW69] D. M. Boulton, C. S. Wallace, The information content of a multistate distribution,

J. Theor. Biol., 23, pp.269-278, 1969, doi:10.1016/0022-5193(69)90041-1.

(i) Cleared up a long running misconception about the information-content of a sequence of symbols, and (ii) showed that if a code based on estimates of symbol-probabilities is used, those estimates must also be encoded at optimum precision.

[CDA07] M. D. Cao, T. I. Dix, L. Allison, C. Mears, A simple statistical algorithm for biological sequence compression,

IEEE Data Compression Conf. (DCC07), pp.43-52, March 2007, doi:10.1109/DCC.2007.7 [more].

A "panel of experts model" (XM) achieves good compression of DNA and of protein sequences.

[CKL00] X. Chen, S. Kwong, M. Li, A compression algorithm for DNA sequences and its applications in genome comparison,

RECOMB, pp.107, 2000.

[CLM02] X. Chen, M. Li, B. Ma, T. John, DNACompress: Fast and effective DNA sequence compression,

Bioinformatics, 18(2), pp.1696-1698, Dec. 2002.

[CW84] J. G. Cleary, I. H. Witten, Data compression using adaptive coding and partial string matching,

IEEE Trans. on Communications, 32(4), pp.396-402, 1984.

Variable-length matching of the recent past context with the previously transmitted sequence gives predictors for the next symbol. Compresses English text at ~2.2 bits/character. (PPM = Prediction by Partial Matching.)

[DPA07] T. I. Dix, D. R. Powell, L. Allison, J. Bernal, S. Jaeger, L. Stern,

Comparative analysis of long DNA sequences by per element information content using different contexts,

BMC Bioinformatics, 8(S2):S10, May 2007, doi:10.1186/1471-2105-8-S2-S10 [more].

Calculating the information content, per symbol, in different contexts, and taking difference plots, shows what information a context gives about a sequence. These quantities can be computed efficiently for very long sequences, even whole genomes.

[GT93] S. Grumbach, F. Tahi, Compression of DNA sequences,

IEEE Data Compression Conf., pp.340-350, 1993.

[GT94] S. Grumbach, F. Tahi, A new challenge for compression algorithms: Genetic sequences,

J. of Information Proc. and Management, 30(6), pp.875-866, 1994.

[HT04] A. Hategan, I. Tabus, Protein is compressible,

Proc. 6th Nordic Signal Processing Symp. (NORSIG), Espoo, Finland, pp.192-195, June 2004.

Not sure about one of the results, but rekindled interest in compression of protein sequences, and has a catchy title -- see [MW99].

[KT05] G. Korodi, I. Tabus, An efficient normalized maximum likelihood algorithm for DNA sequence compression,

ACM Trans. on Inf. Syst., 23(1), pp.3-34, 2005.

[Lan84] G. G. Langdon, An introduction to arithmetic coding,

IBM J. Res. & Dev., 28(2), pp.135-149, 1984, @ibm.

Arithmetic coding (compression) can get arbitrarily close to the lower limit (the entropy of the data) in bits per symbol -- provided it is given a good model of the data.

[LZ76] A. Lempel, J. Ziv, On the complexity of finite sequences,

IEEE Trans. Inf. Theory, IT-22, pp.783-795, Nov. 1976.

Represents repeated substrings as words in a dictionary. And... "Roughly speaking, the complexity of a finite fully specified sequence is a measure of the extent to which the given sequence resembles a random one." --p.75. Also see [ZL77].

[LY96] D. M. Loewenstern, P. N. Yianilos, Significantly lower entropy estimates for natural DNA sequences,

IEEE Data Compression Conf. (DCC97), pp.151-160, 1997, doi:10.1109/DCC.1997.581998.

Took a text compression algorithm (PPM±) and modified it to allow some mismatches with previous contexts and to form a weighted average of such predictors.

[MR04] G. Manzini, M. Rastero, A simple and fast DNA compressor,

Software Practice and Experience, 34(14), pp.1397-1411, 2004.

[MSI00] T. Matsumoto, K. Sadakane, H. Imai, Biological sequence compression algorithms,

Genome Informatics, 11, pp.43-52, 2000.

[MW99] C. G. Nevill-Manning, I. H. Witten, Protein is incompressible,

IEEE Data Compression Conf., pp.257-266, March 1999, doi:10.1109/DCC.1999.755675.

Put a damper on protein compression for while by suggesting that any compression is due to the "skew" in the use of the alphabet, i.e. a 0-order Markov model does best. (If you search for a copy of their data-set on the web, make sure that you get a valid one.) Also see [HT04] and [CDA07].

[RDD96] E. Rivals, J.-P. Delahaye, M. Dauchet, O. Delgrange, A guaranteed compression scheme for repetitive DNA sequences,

Data Compression Conf., pp.453, 1996.

[Sha48] C. E. Shannon, A mathematical theory of communication,

Bell Syst. Technical Jrnl., 27, pp.379-423 & pp.623-656, 1948.

Foundational work on communication and information theory.

[TKR03] I. Tabus, G. Korodi, J. Rissanen, DNA sequence compression using the normalized maximum likelihood model for discrete regression,

IEEE Data Compression Conf., pp.253, 2003.

[ZL77] J. Ziv, A. Lempel, A universal algorithm for sequential data compression,

IEEE Trans. Inf. Theory, IT-23, pp.337-343, May 1977.

"... encoding future segments of the source-output via maximum-length copying from a buffer containing the recent past output. The transmitted codeword consists of the buffer address [a pointer] and the length of the copied segment. ..." Also see [LZ76].

---

© Lloyd Allison Faculty of Information Technology (Clayton), Monash University, Australia 3800.

Created with "vi (Linux & Solaris)",   charset=iso-8859-1

---