Compression and Analysis of Biological Sequences. Why and How.

On work with Julie Bernal, Minh Duc Cao, Samira Jaeger, Chris Mears, David Powell, Tim Edgoose, Linda Stern^*, Trevor Dix, and others at Monash U., .au., and ^*Melbourne U..

Compression of DNA.

Compression of protein.

Uses of information content in sequence analysis.

Relating 2 or more (non-random) sequences.

-- Lloyd Allison
users.monash.edu.au/~lloyd/Seminars/2007-BioCompression/index.shtml

Abstract

Compression can be rather addictive. It has an obvious ``figure of merit'' -- the compressed size of some standard data-set, and it is natural to strive to beat your competitors on this measure. Biological sequences are hard to compress; the more compression the better but there is usually limited value in fighting over the third significant digit. Other properties of a compression method can be just as important or more important. This talk gives some reasons why it is challenging, interesting and useful to compress biological sequences. It also presents two simple models for compressing biological sequences (a possible sub-addiction in compression is to complicated models, but simple is often good); we get good results for DNA and protein.

Why Compress Biological Sequences?

Not to save time or space! (Not yet.)

For analysis.

Good model <=> good compression

  ( compression = modelling + coding )

Note, "masking-out" implies that low-information content = zero information. Not true!

Desirable features of a model:

(Good compression.)

Based on biological knowledge.

Simple, few parameters.

Can give per-symbol information content.

Efficient algorithm.

DNA

Alphabet = {A, C, G, T}.

Various kinds of repeat.

Usually approximate.

Reverse complementary repeats.

Protein

Amino acids.

|Alphabet| = 20.   (log₂20 = 4.3)

Very hard to compress.

1. Approximate repeats model (ARM) for DNA:

<--end copy--<
base part			copy editing part
>--start copy-->

Repeat Graph - all explanations under ARM.

2-D Probability Plot

Plasmodium falciparum, chromosome 2, subtelomeric regions.

1-D Information Content Sequence

P. falciparum, all of chromosome 2, (947,102 bp).

2. A Browser

Cyanidioschyzon merolae, chromosome 1 (422,393 bp), smoothing window 1000,
[small] [med] [big]

Differencing

C. merolae chromosome 4 (513,790 bp), [med] [big], and . . .

. . . its difference from chromosome 4 given 18, smoothing window 1000,  I(c4) - I(c4 | c18),  [med] [big]

Two or more sequences

Using reversal

P. falciparum,  I(chr2) - rev( I( rev(complement(chr2))))

3. Experts model (XM)

A blend (weighted average) of:

 

  A global background expert, e.g., a low-order MM.

 

  A local context expert, e.g., a "windowed" MM.

 

  Forward copy experts (offset, prob. copy v. change).

 

  Reverse complement copy experts (ditto).

 

Good compression, simple, information per-symbol, fast.

XM on DNA, e.g.,

XM on protein, e.g.,

4. Low-information substrings and alignment

Low-information ~ repetitive ~ compressible.

 

Cause false +ve matches for standard software, so . . .

 

  (i) sometimes "masked-out" (discarded), and/or

 

  (ii) significance test: shuffle & re-align (PRSS program).

The M-alignment solution:

Build a sequence-model into the alignment algorithm.

 

  Fewer false +ves, and false -ves, than PRSS and Blast on

  real and artificial test data.

 

  Time-complexity unchanged (but worse constant).

. . .

 

Gives a natural significance test for given propulation model(s).

 

Changes rank-order of alignments cf. "uniform" model, as it should

 

(rather than est. significance of a bad alignment!).

 

model_i can be almost any model, e.g., ARM, or XM.

. . . ROC curves

blue: S-W raw score, green: PRSS p-value, red: M-align (MM 1), purple: M-align (blend mdl), NB. bottom right is good

Conclusions

Calculating information carefully, using it, not discarding it, gives accurate results, few false +ves or -ves.

Information content sequences are 1-D, linear-space. Many operations on them take linear-time. Feasible for millions of bases.

Also see