3日目資料(2006/08/25)

配列・文字列の Origin
生物情報科学実験Ⅰ
„
∼ショットガンアセンブリ∼ Day3
1-origin
{
„
0-origin
{
([email protected])
„
Java VM に対してオプションを与える
{
-Xmx オプション。Java VM が使用してよい
メモリー量の最大値を設定する
„
„
最初の要素を 0 番目と定義する
（コンピューターで良く使うのはこちら）
0123456789
CCTATGCTAG
東京大学大学院 新領域創成科学研究科 特任助手
笠原 雅弘
Java で大量のメモリーを使う方法
最初の要素を 1 番目と定義する
（日常生活で良く使うのはこちら）
0-origin で数えると２文字目
0-origin で数えると０文字目
Eclipse で javaVMに
オプションを与える方法
„
Run する時に
VM arguments
に書き込む
例）512Mバイト使用許可してHelloWorldクラス
を起動
java -Xmx512m HelloWorld
例）2Gバイト使用許可してHelloWorldクラスを起
動
java -Xmx2G HelloWorld
1
Table of Contents 今日の流れ
訂正
„
１日目資料スライド５２で、後藤のアルゴリズム
の解説で Ix と Iy が逆になっていました。
{
{
„
Ix[i][j] S2 にギャップが入って終わるアラインメント
の最適スコア
Ix[i][j] S1 にギャップが入って終わるアラインメント
の最適スコア
„
„
アフィンギャップスコア
„
„
n個の連続ギャップに対して スコア e(n-1)+d
ギャップを伸張(extension)するスコアは e を使うことが多
い
動的計画法の問題点
配列サイズが大きくなると破綻する
{
„
„
シーディング
ハッシュテーブルとは
ハッシュテーブルの構築法
課題提出方法
１日目資料スライド５０のd と e も逆です
{
„
„
動的計画法に対する考察
„
データベース配列 D の長さを m, 問い合わ
せ配列 Q の長さを n とすると計算時間は
mn に比例する
データベース配列や問い合わせ配列の
量が多い場合には計算時間を短縮する
必要がある
観察：たいていのアラインメント問題は
「よく保存されている部分」を持っている
{
„
例）現在実験対象の遺伝子配列をシークエンスした。
ゲノム配列と照らし合わせて遺伝子構造を決定した
い。このとき、シークエンスの先頭と末尾付近は
シークエンスエラーに富むが内部はゲノム配列に
100%近くマッチする
事実：「よく保存されている部分」は速く検索し
見つけ出すことができる
{
100%近くマッチする文字列は、k-mer 整数を使った
比較や、ハッシュテーブル（後述）、接尾辞配列（こ
の実験では触れない）などで高速に見つけ出すこと
ができる
2
シーディング(Seeding)
„
連続k-merシード
シード(Seed)を使って動的計画法の計算
領域を狭める
配列1
„
連続(consecutive)な k-mer をシードとする
{
{
„
シード
DP空間
ハッシュテーブル(Hash table)
連続 k-merの位置を格納し素早く呼び出せるようにした
記憶構造
{
Overlapping/non-overlapping k-mer のどちらを記憶するかは
用途によって一長一短だが、この演習ではoverlapping k-mer を
記憶する
AAA
AAC
索引 AAG
：
：
：
想定する塩基一致率(Identity)が高い場合長く
低い場合短く
ACCGCCTATACTAGTCTTGACGATCTTCT
|||||X||||||||||X|||||X||||||
ACCACTTATACTAGTCATGACGTTCTTCT
配列2
„
11-merがお手頃でよく使われる
長さは通常 7-∼32-mer の範囲
配列 S3 の 154 文字目
配列 S5 の 23 文字目
配列 S5 の 541 文字目
：
：
配列 S0 の 71 文字目
：
：
：
概念図
連続10-mer マッチのシード
配列中の位置を表す
SequencePosition クラス
„
k-mer の存在位置を配列の番号と先頭からの位置を
セットで保存
{
以下の例では k=3 としている
S0:CCTATGCTAGTC
S1:CACGACAGCTTATCTA
S2:TTCCAGGCTGTACTACGAC
S3:ATCGTGATGTTAATCGGA
（0, 0）
（2, 3）
※全配列を連結し、先頭からの位置のみを記録する方法も提案され
ているが、ここでは扱わない。
3
ハッシュテーブルの構造
索引配列
ハッシュテーブルの引きかた
„
位置格納配列
k-mer 整数 位置格納配列上での開始位置
0
0
1
2
14
31
：
：
：
(3,154)
1
(5, 23)
2
(5, 541)
索引配列
開始位置
14
(0, 71)
15
(4, 18)
16
(18, 251)
TACCT
：
791
142716
792
142719
：
：
k-mer整数 0 が出現する回数
k-mer整数 0,1 が出現する回数
k-mer整数 0,1,2 が出現する回数
142716
(23, 434)
142717
(71,48)
142718
(121,145)
142719
(11,130)
142720
(81, 132)
TACCT
の存在
する位置
ハッシュテーブルの作り方（2/3）
„
索引Ｉを作る手順
{
常にゼロ
次のk-mer
の開始位置
793
{
索引配列 Ｉ
0
14
31
59
位置格納配列
：
まず、索引配列 I を作ることを考えよう
0
1
2
3
下記の例は “TACCT” (k-mer 整数で 791) を引く場合
{
0
ハッシュテーブルの作り方（1/3）
„
引きたい k-mer の k-mer整数を i とすると、索引配列
の i 番目が指す先から i + 1 番目が指す先の直前
各 k-mer の出現頻度をカウントし、配列Ｆとする
Ｆの partial sum 配列を Ｉ とする
出現頻度配列 F
0
1
2
3
：
14
17
28
：
：
索引配列 Ｉ
0
1
2
3
0
14
31
59
：
4
ハッシュテーブルの作り方（3/3）
„
索引Ｉを作るときの注意
{
位置格納配列が分かった
„
索引Ｉは 4k+1個の要素を持たせる
TT・・・・TTを引くときを例外扱いする必要を無くす為
„
位置格納配列Ｐ
索引配列 Ｉ
0
1
TTTTTTTTTTTT
：
16777215
16777216
索引配列Ｉ
0
1412154
：
1326864321
1326852189
格納中ポインタを作り
位置格納配列を作成する
„
観察
手順
{
{
索引Ｉが完成すると、各k-merに対応する
SequencePositionをどこに格納すれば良い
かが分かる
„
格納位置配列Ｔを作り、索引Ｉから要素をコピーする
データベース配列を前からスキャンし、現れた kmer について、ポインタを進める
„
格納位置配列Ｐが完成したときにＴは、
各 k-mer に対応する SequencePositionブロックの最
後（正確にはブロック最後の次の要素）を表している
一列ずらしてしまえば索引配列 Ｉ とほとんど同じ
位置格納配列Ｐ
位置格納配列Ｐ
格納中ポインタ配列Ｔ
格納中ポインタ配列Ｔ
格納する
（234, 2457)
１つ進める
5
メモリーを節約する
格納中ポインタ配列Ｔを
„
通常とは逆順でＰを作ればＴは不要
{
{
ブロックの最後＋１を指す索引配列を先に作る
データベースをスキャンし、現れた k-mer について
„
位置格納配列Ｐ
ハッシュテーブルへの改良
„
„
HashTable.java を実装せよ
{
索引を１減らし、位置格納配列に位置を書き込む
索引配列Ｉ
„
必須課題3-1
{
{
ひな形プログラムは実験２日目のプロジェク
トに含まれている
メモリー節約法を使用すること
ソースプログラム HashTable.java 及び動
作していることが分かる簡単な実行例を提
出せよ
リピート配列のマスク
配列中に特に頻出の配列は検索の役に立たな
いことが多く、位置格納配列Ｐから除外しておく
と検索高速化の役に立つことが多い
リピート配列のマスク
非連続シード
CGTACGTT
CGTACGTA
CGTACGTC
CGTACGTG
CGTACGTT
CGTACTAA
CGTACTAC
CGTACTAG
6
7
7
185
7
4
7
CGTACGTT
T回以上出現する頻出k-merをマスクする
(Ｔは時と場合に応じて上手く設定する)
6
非連続シード
„
連続していない k 文字をシードとする
{
{
必須課題3-2
„
n 文字, 1文字分の隙間, n 文字のパターンを
シードとする方式を 1-mid-spaced-seed と呼ぶ
隙間を除いたシードの文字数をシードの「重み(weight)」と呼
ぶ。1-mid-spaced-seed の重みは 2n である
1-mid-spaced-seedについて以下の問いに答えよ
{
{
„
{
1-mid-spaced-seed （例）
{
ACCGCCTATACTAGTCTTGACATCTTCTAG
||||X|||||X|||||X||||X||||||X|
ACCAACTATAGTAGTCATGACTTCTTCTCG
{
{
„
連続10-mer シードの代わりに重み10の
1-mid-spaced seed を使ったハッシュ
テーブルを作成せよ
{
„
細かな条件は必須課題3-1と同様とする
更に、ユーザーが与えるスレッショルド値
Ｔに対して、Ｔ回以上現れるシードをハッ
シュテーブルに格納しないプログラムを
作成せよ
議論を簡単にするために挿入欠失は全くなかったものとする
S1, S2 の間に最小で何塩基の変異が導入されると 10-mer 連
続シードが残っていない状態となるか
S1, S2 の間に最小で何塩基の変異が導入されると重み 10 の
1-mid-spaced seed が残っていない状態となるか
1-mid-spaced seed を使うことの利害得失について論ぜよ
注意：プログラムを作成する必要はない
ACCGCCTATACTAGTCTTGACATCTTCTAG
||||X|||||X|||||X||||X||||||X|
ACCAACTATAGTAGTCATGACTTCTTCTCG
利点）連続シードと比べて長い k をシードとすること
ができる
応用課題3-3
ゲノム配列中に 100-mer の配列S1があり、太古の昔に重複
して配列 S2 が登場した
数百万年の間に S1, S2 に変異が蓄積した
チャレンジ課題3-4
„
任意の形の隙間を入れた重み６のシードの中
について以下の問いに答えよ
{
{
ゲノム配列中に 60-mer の配列S1があり、太古の
昔に重複して配列 S2 が登場した
数百万年の間に S1, S2 に変異が蓄積した
„
„
{
各塩基はこの間に確率 p で変異すると仮定する
議論を簡単にするために挿入欠失は全くなかったものとす
る
どのような形のシードを使えば、重み６のシードが
残っている確率が最大となるか調べよ
„
必要ならそれを証明するプログラムを書き、実行すること
7
課題提出について
„
URL
„
„
report3 として提出すること
必須課題〆切
„
応用課題〆切
„
チャレンジ課題〆切
„
提出方法は基礎(Java)コースと同じ
{
{
{
{
{
http://mlab.cb.k.u-tokyo.ac.jp/~mkasa/upbsb2006/
８月３０日１４時４５分
９月６日１０時００分
９月１８日１０時００分
分からない場合には質問
8