[Dynamite] Is this working now then?

[Ian Holmes]

On Mon, 6 Mar 2000, Guy Slater wrote:

> > (NB I think all alignment algorithms should be global at the minute. Doing
> > local alignment is effectively an optimisation step, equivalent to saying
> > that some cells are zero throughout the matrix)
> 
> No!  I'm v.against implementing everything as global and hacking in
> local alignments later.  Something like that needs to work from the start.

What I meant was that a local alignment model can just be considered to be
a global alignment with two flanking states, i.e. the following (trivial)
local model for ungapped matches

     /\
   +--------+
   |XY match|      (where '/\' denotes a self-loop)
   +--------+

can be considered equivalent to the following global model

     /\          /\          /\          /\          /\
   +--------+  +--------+  +--------+  +--------+  +--------+
   |X-insert|->|Y-insert|->|XY-match|->|X-insert|->|Y-insert|
   +--------+  +--------+  +--------+  +--------+  +--------+

...IF you are looking at log-odds scores AND the insert states are exactly
the same as the null model (because THEN the log-odds score for these
states will always be zero).

I did not necessarily mean that we should implement everything as global
alignments & hack in locals later. What I meant was that it's relatively
easy for an algorithm to auto-detect the lower kind of model and say "Aha,
this model has padding states and so must be a local alignment model"; so
we don't have to put in an explicit global/local switch into the API.

> 
> You will be stuffed by the matrix-edge constraints
> when you try to implement semi-local aligments.
> 

i have always thought of semi-local alignments as just being

     /\         /\         /\
  +--------+  +--------+  +--------+
  |X-insert|->|XY-match|->|X-insert|
  +--------+  +--------+  +--------+

(i.e. global in Y, local in X) or whatever.

> Also, these sort of distinctions need to be very clear
> in the object model for some optimisation strategies.

I can see your point, but here is the problem.

We have to consider how local alignment can fit into the probabilistic
worldview. Essentially the question is:

	"How does the local model explain the unaligned sequence?"

The most obvious answer is "It just says that it was created by the null
'background' model". It's always seemed to me that the simplest way to
factor this in is to add padding states.

In which case, if there is no fundamental distinction between local &
global at the model descriptor level, then that distinction should only be
made lower down at the optimisation level.

Alternatively, if you WANT to provide different APIs for local & global
alignment, this is fine, but I think that it should all fit within this
framework, i.e. "local alignment" should explicitly always be defined as
"global with padding states".

Ian

> 
> Guy.
> --
> 
>