\documentclass[12pt]{article}
\usepackage{graphicx}
\usepackage{mathtools}
\usepackage{url}
\topmargin -0.5in
\oddsidemargin -0.0in
\evensidemargin -0.0in
\textheight 9in
\textwidth 6.5in
\begin{document}
%\pagestyle{empty}

\title{Lab \#7 - Viterbi algorithm}
\author{}
\date{}

\maketitle


In this lab, each student is to develop code to execute the Viterbi
algorithm.
The code can be developed in MATLAB, C, or any high level language.
The exercise is based on the Viterbi algorithm example
posted at the web site.
The output should be a table of max probabilities at each data index
similar to slide 9 in the example, and the most probable path
similar to slide 10 in the example.

The problem consists of two states, labeled H and L in the example,
which can be given numerical values of 0 and 1.
The prior probabilties are $\{0.5,0.5\}$.
The state transition probabilties are $\{0.5,0.5\}$ for state 0 and
$\{0.4,0.6\}$ for state 1.
Each state observes a discrete value that takes on one of four
values $\{A,C,G,T\}$ that can be given numerical values $\{0,1,2,3\}$.
The emission probabilities of these values are
$\{0.2,0.3,0.3,0.2\}$ for state 0 and
$\{0.3,0.2,0.2,0.3\}$ for state 1.

Because the input sequences to be tested are short,
Viterbi calculations can be done using either products of probabilities
or sums of the log$_2$ of probabilities.

The algorithm should be run twice.  On the first run, the input
should be the same as given in the example:  GGCACTGAA.
The results can be compared to the table and most probable path
given on slides 9 and 10.  They should match exactly.
Note that the second to last line on slide 8 has a typo and should
read = -2.322 + max (-2.737 - 1, 3.322 - 0.737).
On the second run, the input should be:  TCAGCGGCT.
For both runs, provide the table of max probabilities at each data index
and the most probable path.

You must submit your report to Canvas.  This report is due by midnight
of the due date.

\end{document}



