5/11 課題1(個人)　

DNA配列を0と1からなるビット列に符号化することを試みる．DNA配列は a t c g の4つの文字のシーケンスとして表現される．a, t, c, gの出現頻度には偏り があるので，出現頻度に応じて異なるビット長に符号化すると，より短いビット 列で符号化することが可能になる(教科書30ページ)．

本来は，出現頻度に関するモデルを作成して，それに合わせて符号化の方法を決 定し，その後で具体的なデータに対して符号化をおこなうというのが筋だが，この 演習では，具体的なデータに合わせて，それをなるべく短く表現できる符号化の方 法を決めることを試みる．

具体的なデータとして，以下の配列を対象にする． 

acaaaatccatcgacagataagcatgagcaagattctgttttttcttcatcggtcacctt
tgtattaatcttaatcctttcgttccttttcgttctcgattccttgttatcctttttcga
cgcactcaactccaaagacaacattggttccgtccttcaattgcaggttatcgcgatttc
tcttcttttctttctctattcggtattaggtctcatgacccgcttgaaaagttcttttca
tttaccttcaccgatcctcaatttgctttgcctcttcgcttttgctgaggaatttttgtt
gttttatcttcaaaggaaagacccaagtggagttgaaaatcgttactataatctcttgct
tgtgcctattgctatttgtgcattttgttcatttctagaattgaaaaatcccaaatcaaa
ttacactagattaggacgtgggattgggttaatcttgcaagggacgtggactcttcaaat
ggggtttgcttttttctccgatttgattgcacagggatgctatttacatc
この配列に対して， 
a : 00
t : 01
c : 10
g : 11
のように，それぞれの文字を2ビットで符号化すると，全体のビット長は1060ビットとなる．

この配列に対して，

  1. a, t, c, g のそれぞれの出現頻度を求め
  2. a, t, c, g のそれぞれの符号化を決め
  3. 符号化した結果のビット長を1060ビットよりも小さくする．
ことを試みて，それぞれにどのような符号を割り当てて，ビット長がいくつになったかをまとめ なさい。また，この場合の平均符号長(教科書44ページ)を求め，平均情報量(教科書42ページ)と 比較しなさい．平均情報量を求める際の対数の底はeではなくて2であることに注意して欲しい．
提出はテキストファイルの形式でレポートを作成し，cfiveを使って5/11演習課題1提出ページを選択して提出すること．期限内なら， 何度も提出できる． 「テキストファイル」としては，「15.1 エディタとは何か」にある「プレーンテキストファイル」を想定している．ただ，数式を綺麗に表示したい などの理由がある場合は，WORD形式，pdf形式のファイルを送っても良い．

ヒント(1)

WWWブラウザ上で実験できるように， を用意しました．WWWブラウザ上でのコピー & ペーストができれば，使えると思い ます．なお，これらのページはJavaScriptを使っているのでSafariユーザで， 「環境設定」 -> 「セキュリティ」-> 「JavaScriptを有効にする」がチェックさ れていない場合は動きません．

ヒント(2)

適当に符号化しても最適な符号は構成できると思いますが，理論的に最適な符号としては， ハフマン符号 が知られているので，それを使うのが良いでしょう．

ヒント(3)

塩基配列中の a, t, c, gの出現頻度はあまり偏りがないので，それほど短くはならないはずです．

ヒント(4)

平均情報量の計算には，対数計算が必要になるので，iMac端末の電卓プログラムでは計算できない． 表計算ソフトを使ったり，数式処理ソフトを使って求めることができる．