GENSCAN - Gene finding software for vertebrates, HMM

http://genes.mit.edu/GENSCANinfo.html
http://genes.mit.edu/GENSCAN.html


http://www.cs.ubc.ca/~irmtraud/cs_545/web_material/genscan_paper.pdf

http://lib.bioinfo.pl/courses/view/685

This server provides access to the program Genscan for predicting the locations and exon-intron structures of genes in genomic sequences from a variety of organisms.

HMM - given a list of nucleotide sequence, find which nucleotides correspond to an exon, similar to the biased casino problem where the die rolled can be biased or not (hidden state), has transition and emission probabilities obtained from the training data

Viterbi algorithm uses dynamic programming techniques to minimize the cost of calculating sub-optimal paths by for the maximum values for the previous state only
The algorithm makes a number of assumptions:

- First, both the observed events and hidden events must be in a sequence. The sequence is often temporal, i.e. in time order of occurrence.
- Second, these two sequences need to be aligned: an instance of an observed event needs to correspond to exactly one instance of a hidden event.
- Third, computing the most likely hidden sequence (which leads to a particular state) up to a certain point t must depend only on the observed event at point t, and the most likely sequence which leads to that state at point t − 1.


http://en.wikipedia.org/wiki/Trellis_diagram#Trellis_diagram