\documentclass[12pt, epsf]{article}
\usepackage[finnish]{babel}   %% suomalainen tavutus
\usepackage[latin1]{inputenc} %% 8-bittiset tiedostot
\usepackage[T1]{fontenc}      %% 8-bittiset fontit
\usepackage[dvips]{epsfig}
\textheight 22cm
\textwidth 16cm
\headheight -1.7 cm
%\footheight 0.1cm
\oddsidemargin 3mm
\topskip 1mm
\parskip 0.5cm
\parindent 1cm
\baselineskip 6mm
\begin{document}
%\input epsf
\noindent
{\large Tik-61,181: Bioinformatics} \hfill Kaski,Mannila,Nikkilä\\ 
{\large Exercises 1, Autumn 2000}

In essay type answers try to answer briefly and concentrate on
relevant issues. It is assumed that the assistant will need only
reasonable amount of time when decoding the answers. If the opposite
occurs, it may affect your grade.

The maximum length of an answer to one question is one page. If you make
some proofs or simulations they can be included as appendixes.  Every
answer will be evaluated with the scale \{0:failed, 3:accepted,
5:accepted with distinction\}. In order to pass the course you need at 
least grade 3 for 60\% of the exercises. In order to pass with
distinction you need to return 95\% of the exercises, and to get the
grade 5 for most of them.

The deadline of the exercises is 31.1.2001.


\begin{itemize}
\item[a)] Explain in detail how you would align the following
  sequences with pair HMM:s and with non-probabilistic methods:\\ AAAG\\
  ACG\\ (DEKM ch.2 and ch.4, S\&M ch.3)
\item[b)] Analyze briefly the relation of the probabilistic approach and
  the non-probabilistic approach for sequence alignment.  \\(DEKM ch.2 and
  ch.4, S\&M ch.3)
\item[c)] Give an example of the possible uses of the MC-model and HMMs in
  bioinformatics. Outline briefly the main differences between the two models.
  \\(DEKM ch.3)
\item[d)] Relax. You are buying a drink from the notorious crazy coke
  machine while absent-mindedly solving some exercises. The machine can be
  in either of two states: cola preferring state (CP) and mineral
  water (WP) preferring state. When you put in a coin, the output of the
  machine can be described with the following probability matrix:\\
\begin{tabular}{c|ccc}
&cola&mineral water&lemonade\\
\hline
CP&0.6&0.1&0.3\\
WP&0.1&0.7&0.2
\end{tabular}\\
Draw the state model graph with transition probabilities $P(CP\rightarrow WP)=0.3$
and $P(WP\rightarrow CP)=0.5$ and calculate the probability of seeing the output
sequence \{cola,lemonade\} if the machine always starts off in the WP
state. What kind of behaviour would make this HMM to a (visible)
Markov model?  \\(for example DEKM ch.3)
\item[e)] Do the exercise 3.3 in DEKM and explain its result briefly
  in the bioinformatics framework.
\item[f)] Compare briefly the FSAs and pairwise HMMs in searching.
  \\(DEKM ch.4)
\item[g)] Analyze the relation of the profile HMMs, HMMs, and PSSMs.
\item[h)] Exercise 6.1 in DEKM.
\item[i)] Explain briefly the pros, cons, and the most useful
  applications of the different progressive alignment methods and
  profile HMMs in multiple alignment.  \\(DEKM ch.6)
\item[j)] Explain the reasons why there are methods for fragment
  assembly and physical mapping.
  \\(S\&M: ch.4 and ch.5)
\item[k)] Exercise 1 in ch.4 in S\&M.
\item[l)] Exercise 5 in ch.5 in S\&M.
\item[m)] Exercise 6 in ch.6 in S\&M.
\item[n)] Exercise 8.2 in DEKM. Explain also the concept of multiplicativity here.
\item[o)] Exercise 8.7 in DEKM
\end{itemize}
\end{document}