(DNA) Sequence Complexity and Alignment.

Bioinformatics Seminar: room B/C, Walter & Eliza Hall Inst. (WEHI), Parkville, 11am Tuesday 13 February 2001

Debts, in alphabetical order, to: Trevor Dix, David Dowe, Tim Edgoose, Dave Powell, Linda Stern, Chris Wallace, Chut N. Yee.

Lloyd Allison, Computer Science and Software Engineering, Monash University, Victoria, Australia 3168

http://www.csse.monash.edu.au/~lloyd/tildeStrings/

This document is online at www.csse.monash.edu.au/~lloyd/Seminars/2001-WEHI/index.shtml and contains hyper-links to more detailed notes on certain topics and to some of the references.

Also see Modelling v. Shuffling.

<< [02] >>

The story...

(Probabilistic) Finite State Automata (PFSA)
= Hidden Markov Models (HMM)
Model complexity
Alignment Algorithms
Cost functions (gaps)
Compression
Alignment and Compression.

<< [03] >>

Probabilistic Finite State Automaton PFSA c1983, AKA Hidden Markov Model HMM, TR32

A very (!) old problem:

Learn a language.

Babies do it.
Gaines 1976:
CAAAB/ BBAAB/ CAAB/ BBAB/ CAB/ BBB/ CB
Wallace & Georgeff 1983:
PFSA (right)
Model complexity v. fit

<< [04] >>

Model Complexity:

Bayes (1763)
- P(H|D) = P(H) . P(D|H) / P(D)
Fisher
- [Fisher Information]: sensitivity of P(D|H) to (continuous) parameters
Shannon (c1948)
- msgLen(E) = -log₂(P(E)) in optimal code, so . . .
- msgLen(H&D)= msgLen(H) + msgLen(D|H)
  = msgLen(D) +msgLen(H|D)
- msgLen(H)= model complexity
- msgLen(D|H) = data complexity | H

<< [05] >>
Alignment, [c1990]:

Mutation Machine

Mutation instructions: copy, change, insert, delete.

<< [06] >>

Equivalent Generation Machine:

Probabilistic Finite State Automaton PFSA generation machine c1990, AKA Pair Hidden Markov Model PHMM

Generation instructions: match, mismatch, insert₁, insert₂.
(A.K.A. Pair Hidden Markov Models (PHMM).)

<< [07] >>
What matters most is the "control box" (model):

e.g. 3-state machine ~ [linear gap costs]:
e.g. 5-state machine (more complex) ~ piece-wise linear gap costs, etc.

<< [08] >>
A twist: Sum over all Alignments, fwd+back, alignment density:

Sequence Alignment Probability Density Plot, cf Pair Hidden Markov Model PHMM HMM, of chicken hemoglobin alpha and beta chains CHKHBAM and CHKHBBM as in Waterman(1984, p484)

<< [09] >>

Compression ~ Sequence Complexity:

Compression Machine Probabilistic Finite State Automaton PFSA c2000, AKA Hidden Markov Model HMM

(Also reverse-complementary approximate repeats.)

<< [10] >>

What matters most is the control box, e.g.

Probabilistic Compression Approximate Repeats Control Machine c1998, AKA Hidden Markov Model HMM

<< [11] >>
2-D Plot from Compression Algorithm.

2D Compression Approximate Repeats Probability Density Plot, n.b. not a DOTTER style dot-plot matrix, also see 1-D plot

p.falciparum, chr2, 0.95Mbp

[Zoom 30-70K]

[colour]

[b+w]

[1-D plot] bits/b.p.

NB. Same twist - sum over all explanations. But not enough space for fwd+rev for long Seq'.

<< [12] >>

Compression and Alignment.

A sequence is compressible if you can predict (to some extent) what is coming next.
Two sequences are related if one gives you useful information about the other.
When aligning non-random sequences we have two sources of information:
- A sequence tells about itself and
- one seq' tells about the other.
- Must combine the sources.

<< [13] >>

	. . .	S1[i]
S e q 2 .
. . .	. (mis)match . . .	`\| \| \| insert \| \| v`
S2[j]	`-------> delete`	?
. . .

<< [14] >>

To combine the sources of information, e.g. can: (a) build "direct product" of sub-models, Powell et al (1998), or; (b) say, use this approximation: . . .

Instruction probabilities (costs = -log₂( . )):

P(match) . ( P(S1[i] | S1[1 .. i-1]) + P(S1[i] | S2[1 .. j-1]) )/2
P(mismatch) . ( P(S1[i] & S2[j] | S1[1 .. i-1] & S2[1 .. j-1] & S1[i]!=S2[j])
P(insert) . P(S2[j] | S2[1 .. j-1])
P(delete) . P(S1[i] | S1[1 .. i-1])

See [Comp. Jrnl. (1999)]

<< [15]

Results:

Few false positives.
Few false negatives (e.g. "features").
A natural significance test.
"[Modelling is more versatile than shuffling.]"

Some References

Allison L., Wallace C. S. & Yee C. N. (1992). Finite-State Models in the Alignment of Macro-Molecules. J. Molec. Evol. 35(1), pp.77-89. (Also see [TR90/148].)
Allison L., Edgoose T. & Dix T. I. (1998). Compression of Strings with Approximate Repeats. Intelligent Systems in Molecular Biology (ISMB'98), pp.8-16, Montreal [HTML].
Allison L., Powell D. & Dix T. I. (1999) Compression and approximate matching. Computer Jrnl. 42(1), pp.1-10.
Allison L., Stern L., Edgoose T. & Dix T. I. (2000). Sequence Complexity for Biological Sequence Analysis. Computers and Chemistry 24(1), pp.43-55.
Powell D., Allison L., Dix T. I., & Dowe D. L. (1998). Alignment of low information sequences. Proc. 4th Australasian Comp. Sci. Theory Symp., CATS98, Perth, pp.215-229, Springer.
Uptodate: [http://www.csse.monash.edu.au/~lloyd/tildeStrings/]. Also see [Modelling-Alignment], pp.203-214, AI2004.

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