[Biojava-l] single and double headed HMM's

[Ewan Birney]

On Mon, 22 Jan 2001, Thomas Down wrote:

> On Mon, Jan 22, 2001 at 02:24:44PM +1300, Mark Schreiber wrote:
> > Hi,
> > 
> > I am fairly familiar with HMM's but I am not shure what is meant by the
> > term double headed. Can someone explain??
> 
> Not absolutely sure where the terminology originates but it
> refers to the number of sequences emitted by the model:
> 
>   - Single-head models emit a single sequence.  The dp toolkit
>     can be used to align and score a sequence against the model.
>     Profile HMMs for recognising protein families would be a
>     classic application.  In biojava, these models generally
>     emit over simple alphabets (eg DNA or protein).
> 
>   - Two-head models emit a pair of sequences.  They can be used
>     to align and score two sequences against one another.  Alignment
>     algorithms such as Smith-Waterman can be implemented as
>     a two-head HMM.  They always emit over cross-product alphabets
>     (e.g. DNA x DNA).

The "standard" (durbin, eddy, krogh, holmes ... myself...) way to
call this is a "Pair HMM"

There is no real counterpart outside of bioinformatics. In grammar theory
there are things called two-tape grammars, but that term gets abused
between people who mean you need two tapes to handle the grammar and 
"transducing" grammars which turn one tape into another tape. 


The pair-hmm is closest to the two tape "transducing" grammar.

> 
> One day, it would be nice to upgrade the toolkit so that it
> can dynamically generate arbitrary-headed DP algorithms (i.e.
> for alighning three or more sequences).
> 

computationaly this does not behave well... ;)


> Hope this clarifies matters,
> 
>     Thomas.
> _______________________________________________
> Biojava-l mailing list  -  Biojava-l@biojava.org
> http://biojava.org/mailman/listinfo/biojava-l
> 

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