5日目資料(2006/08/30)

Table of Contents 今日の流れ
生物情報科学実験Ⅰ
∼ショットガンアセンブリ∼ Day5
„
ゲノムアセンブリにおける
マルチプルアラインメント
{
{
„
簡易マルチプルアラインメント
詳細マルチプルアラインメント
課題提出方法
東京大学大学院 新領域創成科学研究科 特任助手
笠原 雅弘
([email protected])
Contig の先頭リードを求める
„
各パスの先頭のリードを求める
{
{
Contig の先頭リードを求める
„
全てのリードを先頭のリードとしてマーク
各リードに対して、ベストオーバーラップ先の
リードのマークを消去→先頭のみが残る
各パスの先頭のリードを求める
{
{
全てのリードを先頭のリードとしてマーク
各リードに対して、ベストオーバーラップ先の
リードのマークを消去→先頭のみが残る
ゲノム配列
先頭リード
ゲノム配列
先頭リード
リード
ベストオーバーラップ
リード
ベストオーバーラップ
複数コンティグの存在に注意
„
先頭のリードは一般に複数存在する
{
{
ゲノム配列が完全に覆われていない時
環状ゲノム配列が完全に覆われたときには先頭リードがなく
なってしまうことにも留意
„
コンティグ毎に（簡易）
マルチプルアラインメント
„
精度の良いマルチプルアラインメントは計
算時間が長い
{
今回実験でショットガンシークエンシングしたのは環状プラスミド
であるからこの可能性はあり得るが、実際にはギャップが存在し
ているので、それを仮定してプログラミングして構わない
{
ゲノム配列
必須課題では簡易的に計算する
実際においても簡易マルチプルアラインメン
トを計算し、結果を徐々に改善していく方法
が採られる
先頭リード
コンティグ(contig)
ギャップ
コンティグ(contig)
簡易マルチプルアラインメント１
„
先頭リードを並べ、仮のコンセンサス配列
とする
簡易マルチプルアラインメント２
„
仮のコンセンサス配列と次のリードの
オーバーラップアラインメントを計算する
仮のコンセンサス配列
仮のコンセンサス配列
先頭リード
先頭リード
オーバーラップアラインメントを計算
先頭リード
次のリード
簡易マルチプルアラインメント３
オーバーラップアラインメントではみ出た
部分を仮のコンセンサス配列に追加
„
簡易マルチプルアラインメント４
„
仮のコンセンサス配列と次のリードの
オーバーラップアラインメントを計算する
仮のコンセンサス配列
仮のコンセンサス配列
先頭リード
先頭リード
オーバーラップアラインメントを計算
オーバーラップアラインメントを計算
次のリード
簡易マルチプルアラインメント５
„
以下同様に計算を行う
{
最後のリードに達したときにできあがったコン
センサス配列はだいたい正しい
„
相補鎖 Contig を考慮する
„
アセンブルする前に、リード群に対して相補配
列群を生成し、加えたのでそれを考慮
{
片方を出力したらもう片方は出力しない
毎リードについて、追加した部分に間違った塩基
があれば、コンセンサス配列も間違ったままにな
ることに注意する
ゲノム配列Ｇ
コンセンサス配列
ゲノム配列Ｇの相補配列
先頭リード
同じ色のリードは相補配列の関係
必須課題 5-1
今日の課題
„
必須課題 5-2
„
MultipleAlignment.java と Assemble.java
を実装し、ソースファイルを提出
リードをアセンブルしたコンティグの配列を提
出せよ
{
{
作成したContigが正しいことを確かめよ
{
Smith-Watermanアラインメントを計算し、標
的配列と作成したContigの対応関係（何番
目の塩基と何番目の塩基が対応している
か）を調べレポートに記せ
„
課題 Webページ上に標的配列を掲載した
{
{
„
課題 5-2 の注意
„
注意点
{
Hirschberg の領域節約法を実装していない
場合メモリーが足りないというエラーがでる
かもしれない
„
„
JavaVM はデフォルトで 64Mbytes までのメモ
リーしか扱えない。–Xmx オプションを与える等
して使えるメモリー量を増やしておくこと
やり方の詳細は３日目資料を参照
作成した Contig と100%一致するとは限らない
標的配列は環状の配列である
作成した Contig にシークエンシングエラーがあ
れば、その位置をレポートに記せ
簡易マルチプルアラインメントの
問題点
„
リードにシークエンシングエラーがあるとそのミ
スがコンセンサス配列に含まれてしまう
コンセンサス配列
先頭リード
この場合はエラーが残らない
コンセンサス配列
先頭リード
エラーが伝播する
シークエンシングエラー
コンセンサス配列の再評価
Master-Slave alignment
„
コンセンサス配列に再度リードをアラインメント
(Master-Slave alignment)、その後多数決
コンセンサスと異なる配列が多かった塩
基を多数決で修正
„
コンセンサス配列
ミスが伝播する
先頭リード
コンセンサス配列
リードをコンセンサスに再アラインメント
コンセンサス配列修正
コンセンサス配列
コンセンサス配列
再アラインメントでコンセンサス配列と
異っていた塩基
反復が必要となる場合もある
„
先に確定させたコンセンサスに対して
真のコンセンサス配列が長い場合
修正によってコンセンサス
配列とは不一致するように
なっている
応用課題 5-3
„
反復アルゴリズムを用いた
マルチプルアラインメントを実装せよ
{
ACCGCCTATATTAGTCTTGACG
CTTATACTAGTCATGACGTTC TCT
CTATACTTGTCTTGACGTTCATTCTAGCATGC
AGTCTTGACGTTC TTCTAGAATGCACATACG
CTTAACGTT ATTCTAGAATGCACATGCGACT
このように並べるために
は２回の反復が必要
再アラインメントでコンセンサス配列と
異っていた塩基
{
プログラムソースを提出
簡易マルチプルアラインメントでは上手くマル
チプルアラインメントできない例を与えて実行
し、結果が改善していることを示せ
他プログラムの
アラインメントアルゴリズム
„
Phrap (P. Green, et al.)
{
リード配列の QV が高い部分を
継ぎ接ぎしてコンセンサスを作る
„
{
各塩基のＱＶ合計が最も高くなるように
QV(Quality Value) はベースコーラーが
出力する、塩基の精度を表す値
課題提出について
„
URL
{
„
„
report5 として提出すること
必須課題〆切
{
„
９月４日１０時００分
応用課題〆切
{
„
http://mlab.cb.k.u-tokyo.ac.jp/~mkasa/upbsb2006/
９月８日１９時００分
提出方法は基礎(Java)コースと同じ
{
分からない場合には質問