[Biojava-l] Mixing order of models

[Matthew Pocock]

Thomas Down wrote:

> On Thu, Oct 11, 2001 at 01:01:20PM +1300, Mark Schreiber wrote:
> 
>>Hi -
>>
>>A while ago I asked a question about mixing the order of Markov Models.
>>The reason I want to do this is that some regions contain enough sequence
>>to make 2nd order models other regions can easily make 5th order models. I
>>seem to remember someone suggesting the use of redundant hexamers to mimic
>>trimers (or something), how would this work??
>>
> 
> Well, it's certainly possible to mix orders of models, by using
> distributions which are high-order, but where some (or all)
> of the conditioning symbols are ignored.  I guess that's equivalent
> to what you say about redundant hexamers.
> 
> Training such a distribution might be a little more interesting,
> but it should be possible to write a DistributionTrainer which
> picks an appropriate order of distribution, based on the amount
> of supporting evidence.  In a nice, Bayesian world, this should
> just be a question of using a sensible prior.  (Matthew: am I
> missing something here).
> 


You are correct. In a perfect world, you would chose a prior over order 
(something like an exponential decay, for example), and estimate what 
order could be supported by regions of the model. You could for a single 
state mix 1st order through to n'th order probabilities using
an estimation of a mixing function (mixed with the prior to make it 
sensible) and an estimation of the individual distributions guessed from 
the training data. You should be able to convince it to collapse down to 
a single order (or even take the maximum likelihood estimate of order 
for a state). Yuck. It wouldn't require the DP package to be changed in 
any way - you'd just have to write some Distribution instances.

Ultimately, you would want to use some integration over all state 
machines over all emission orders symultaneously, and learn a 
probability distribution over these machines that makes your data look 
likely. This is way beyond my maths, but with suitable training routines 
ends up collapsing back into the finite state machine world.

The quick and dirty solution (if you know already which regions of a 
model are what order) is to define the entire model in the highest order 
necisary, and then make the lower order distributions degenerate. You 
can save on time/memory by writing a small Distribution implementation 
that delegates onto an underlying Distribution after trimming the 
cross-product symbol appropreately. Don't forget to register two 
trainers, one for the delegate distribution, and one for your 
implementation that forwards on the counts for the trimmed symbols.

Here is some code that won't compile, but will give you strong hints. 
You may wish to check the trimming distribution code into BioJava once 
it works.

Matthew

ChoppingDistribution implements Distribution {
   private Distribution targetDist;

   private FiniteAlphabet alpha;
   private int order;

   private FiniteAlphabet targetAlpha;
   private int targetOrder;

   /* "cast" a symbol from the distribution alphabet to the
   * target alphabet
   *
   * ps should we be taking the first or last symbols?
   * check NthOrderDistribution to make it the same.
   */
   private AtomicSymbol downCast(AtomicSymbol s)
   throws IllegalSymbolException {
     return targetAlpha.getSymbol(
       s.getSymbols().subList(0, targetOrder)
     );
   }

   public double getWeight(AtomicSymbol as)
   throws IllegalSymbolException {
     return targetDist.getWeigth(as, downcast(as));
   }
}