情報基礎実験（浅井担当）とゲノム配列解析論Ⅱについて

浅井担当分の演習問題

情報基礎実験の資料を参照しながら取り組むと良いでしょう。

課題１　隠れ状態列推定（提出締め切り 10/30)
(1) HMMのViterbiアルゴリズムを実装して、ソースコードを提出せよ。
(2) 実装したプログラムを用いて、サンプル配列の隠れ状態列を推定して提出せよ。

ゲノム配列解析論Ⅰの第3回講義資料を参考にせよ。
対数を取って計算しないと、確率の値が小さくなりすぎて計算できないので注意せよ。

開始状態をs0とし、s0からの記号出力はないものとする。
下記の形式で与えられるHMMのパラメータファイル(%以下はコメントである）と、fasta形式で与えられる配列ファイルを読み込み、推定された隠れ状態列を出力するようにすること。ソースコードにパラメータファイルや配列ファイルの内容を直接書き込まないように。
アルファベットサイズ、アルファベット、状態数は可変であることに注意せよ。

%% HMMのパラメータファイル
4 %アルファベットサイズ
a c g u %アルファベット。
5 %状態数
0.0 0.25 0.25 0.25 0.25 %状態遷移行列 a00 a01 a02 a03 a04
0.0 0.75 0.05 0.1 0.1 %状態遷移行列 a10 a11 a12 a13 a14
0.0 0.05 0.75 0.1 0.1 %状態遷移行列 a20 a21 a22 a23 a24
0.0 0.1 0.1 0.75 0.05 %状態遷移行列 a30 a31 a32 a33 a34
0.0 0.1 0.1 0.05 0.75 %状態遷移行列 a40 a41 a42 a43 a44
0.4 0.1 0.1 0.4 %出力確率 e(1,a) e(1,c) e(1,g) e(1,u)
0.1 0.4 0.4 0.1 %出力確率 e(2,a) e(2,c) e(2,g) e(2,u)
0.4 0.4 0.1 0.1 %出力確率 e(3,a) e(3,c) e(3,g) e(3,u)
0.1 0.1 0.4 0.4 %出力確率 e(4,a) e(4,c) e(4,g) e(4,u)
%% HMMのパラメータファイル終わり

sample-RNA
gagaguccuauacaaacuccaaaacacugagaccauacaaguaaaaccagucgagaaaau
agucaacagcacccccguugcguauccugcggagaaugccucgcuaucuguccucacgau
uggucuaaccgcucggcucaggcgugugggccugaaauccgggcagcaaacuacgguaag
uuuucgcguaucaaaaauacauugaugaauguucgcuauuagccgggucgacguuuugau
ggugacuaggagcgaaagugauuuuuuugugagcggugucauagcaggggaucaucugag
gugaacuauggacgggucagucgcccucauuggguuuguuacucagauacgugacacacg
uaaggucgcacggcaguagugauccacgagaaucggcacucuuacgagcaagucuauagc
gacguggcuugcuauuaagacaguaauggacucggacagcuaguacgcgacuaaucauuu
ucgcacgccaucacacuuucaacccaggagcuuacaguguuccaggggccaggcuugggg
cagccucuguggaagugcgagggcugcgcuaguguacauuagccgacccucagacgugaa
auaaagagaugcugcugguugcacagugagcaacguucacucggcaacccgucggauacc

課題２　パラメータ推定（提出締め切り 10/30）
（１）　HMMのforward-backwardアルゴリズムとBaum-Welchアルゴリズムを実装してソースコードを提出せよ。
（２）以下の配列を使ってモデルを学習し、かつ、学習したモデルを用いて、これらの配列に対応する隠れ状態列をViterbiアルゴリズムを用いて推定し、その結果を提出せよ。
tRNA-sequences
forward-backwardアルゴリズムでは、対数を取って計算しても足し算だけにならない。
logとexpを交互に計算すると計算が遅くなるので、scalingを推奨する。
ゲノム配列解析論Ⅰの第3回講義資料の末尾の２ページを参考にせよ。

課題３　周辺化カーネル（提出締め切り 10/30)
(1) forward-backwardアルゴリズムを用いて、marginalized count kernel(MCK)を計算するプログラムを実装してソースコードを提出せよ。
(2) 作成したプログラムと、課題2で学習したパラメータをを用いて、課題３で用いた配列全てのペアに対するMCKを求め、ヒートマップなど見やすい形で可視化せよ。
marginalized count kernelについては、この資料を参照せよ。