[Dynamite] (no subject)

[Ewan Birney]

On Mon, 24 Jul 2000, Guy Slater wrote:


[nb -moved this onto dynamite so it gets archived]

> On Mon, 24 Jul 2000, Ewan Birney wrote:
> 
> > On Mon, 24 Jul 2000, Ian Holmes wrote:
> > 
> > > incidentally i think you're absolutely right to do explicit memory first,
> > > and we should do telegraph that way (leaving divide-and-conquer as a nice
> > > modular task that is compatible with our test suite)
> > 
> > Indeed. 
> > 
> > > 
> > > i propose that getting genewise working in telegraph is a higher priority
> > > than doing linear-space algorithms; this will also ensure that development
> > > of the training code keeps pace with the full implementation, since the
> > > forward-backward algorithm either uses explicit memory or relies on Lars
> > > Arvestad's PhD thesis, of which i have a copy but would rather not have
> > > to re-read before ISMB. Deal? ;-)
> > > 
> > 
> > 
> > As soon as we have genewise we will want linear space algorithms ;)
> 
> I was assuming we were going to do something like:
> 
>     find_score_only() --> find_end_points() --> global_traceback()


This is indeed the case of how I imagine it. Actually - miss out score
only part - go straight to find_end_points. 

with special states (not sure what the telegraph equivalent is) an
important optimisation is to find the set of special state start/end
points in one sweep followed by "local" global alignments.

 > 
> ... so I would have thought we could get some way
> before global_traceback() _had_ to go linear space,
> ( or resort to the 8Gb sanger boxes ).
> 
> I am keen on Ian's idea of starting with runs_like_a_pig_viterbi()
> for tests, using loads of space and time, but being v.paranoid and v.robust.
> 

Makes sense to me.

> I think code generation can save us
> from a lot the intricacies of the more tricky dp stuff.
> 

Indeed. But the code generation and the run-time solution are similar
complexity.


> Guy.
> --
> 

-----------------------------------------------------------------
Ewan Birney. Mobile: +44 (0)7970 151230, Work: +44 1223 494420
<birney@ebi.ac.uk>. 
-----------------------------------------------------------------