バイオインフォマティクス
（第３回）
慶應義塾大学生命情報学科
榊原康文
アセンブリの演習問題 （解）
CGTCCGT--- --TCCGTAT--- ---GTATC--- ---ATCCAT-- ---CATCG
===============
CGTCCGTATCCATCG
1 4
2 3
CGTCCGT
TCCGTAT
ATCCAT
GTATC
4
2 5
CATCG
2 3
1 3 2
5
2 1
1
1
配列解析（ペアワイズアライメント）
① ペアワイズアライメント
② 最長共通部分配列（ LCS ）
③ 大域アライメント，局所アライメント
④ スコア行列（置換行列）
相同性検索（アライメント）の威力
サル肉腫ウイルスのがん遺伝子シス（sis
）とヒトの血小板 由来増殖因子（PDGF
）のアミノ酸配列が一致している（そっくりである）ことが発見された （１９８３）
（「がん遺伝子の発見」，中公新書）
sis : simian sarcoma virus
この発見は２つの意味において驚きをもって迎えられた①
がん遺伝子が正常な細胞の増殖・分化や個体発生を 司る遺伝子とほとんど同じものであることが初めて具体 的に明らかにされた （がん遺伝子と増殖因子が結び ついた）②
その発見が試験管の中の実験ではなく，コンピュータに よるホモロジー検索の結果得られた相同性検索
Doolittle によるがん遺伝子の発見
Doolittle がそれまでに構築してきたデータベース
相同性検索プログラム
総当りの仕事もいとわないコンピュータ
BLAST によるデータベース検索
ゲノムデータベース
入力配列
■
DNA
配列■アミノ酸配列
類似遺伝子 アノテーション
相同性検索（アライメント）の威力（２）
Ｐ１６タンパク質遺伝子：①
サイクリン依存性キナーゼ４（CDK4
，細胞増殖促進）の阻害因子
②
実は，がん抑制遺伝子の一つ③
発見の過程において，GENBANK
と相同性検索が威力 を発揮 （１９９４）①
（ミリアッド・ジェネティクス社のカムは）メラノーマと呼ばれ る皮膚がんの組織から，ある遺伝子を実験によって同定 していた②
しかし，その遺伝子の正体がわからなかったために，頻 繁にGENBANK
上で相同性検索を行う③
ある日，GENBANK
に最近登録されたｐ１６遺伝子と皮膚 がん遺伝子の相同性が非常に高いことを検索から発見 し，その正体を突き止めた（「がん遺伝子を追う」，朝日新聞社）
アライメントからわかること
①
配列と配列がもつ情報との関係が十分に解明されていない ため，１本の配列だけから生物学的な情報を抽出することは 困難 ⇒ 配列を比較する②
生物配列は進化によりダイナミックに変化する：
点突然変異（置換，挿入，欠失）③
未知の遺伝子配列に類似である，機能が既知の遺伝子を検 索する ⇒ 遺伝子機能の推定④
ゲノム配列中に既知の遺伝子配列と相同な領域を発見する⇒ ゲノム配列からの遺伝子の発見
⑤
生物種間の共通遺伝子の配列をアライメントにより比べるこ とにより，配列間の進化的な関係を計算⇒ 分子進化系統の推定
最適なアライメントを求める
① 与えられたスコア（置換度）に関して，最適なア ライメントを求める高速なアルゴリズム
＋
② 数学的に最適なアライメントが，生物的に真に 最適なアライメントになるためのスコア行列
生物的に最適な配列 数学的に最適な配列
問い合わせ配列 高速なアルゴリズム
スコア行列
配列のアライメント
2
つのDNA
配列に対して，適切な位置にギャップ記号を挿入 することで，配列中の同じ位置に同じ塩基（あるいは性質が 良く似た塩基）が並ぶようにする操作GAGGTTATCAAAAGCTACTAGTCCA GAGGATAACAAGGCTACTATCACA
入力：
GAGGTTATCAA-AA-GCTACTAGTC-CA GAGG--AT-AACAAGGCTACTA-TCACA
**** ** ** ** ******* ** **
出力：
MVHLTPEEKSAVTALWGKVNVDEVGGEALGRLLVVYPWTQRFFESFGDLSTPDAVMGNPKVKAHGKKVLG MVHLTPEEKSAVTALWGKVNVDEVGGEALGRLLVVYPWTQRFFESFGDLSTPDAVMGNPKVKAHGKKVLG
**********************************************************************
タンパク質のアライメントの例
ヘモグロビンのアミノ酸配列のアラメント：
AFSDGLAHLDNLKGTFATLSELHCDKLHVDPENF-RLLGNVLVCVLAHHFGKEFTPPVQAAYQKVVAGVA AFSDGLAHLDNLKGTFATLSELHCDKLHVDPENFK-LLGNVLVCVLAHHFGKEFTPPVQAAYQKVVAGVA
********************************** **********************************
NALAHKYH NALAHKYH
********
MV-HL--TPEEK-SAV-TALW-GKVN--VDEVGGEALGRLLVVYPWTQRFF-ESFGDLS-TP-DAVMGNP -VQ-LSG--EEKA-AVL-ALWD-KVNEE--EVGGEALGRLLVVYPWTQRFFD-SFGDLSN-PG-AVMGNP
* * *** ** *** *** ********************* ****** * ******
KVKAHGKKVL---G-AFSDG--LAHLDNLKGTF-ATLSELHCDKLHVDPENFRLLGNVL-VCVLA-HHFG KVKAHGKKVLHSFGE----GVH--HLDNLKGTFAA-LSELHCDKLHVDPENFRLLGNVLVV-VLAR-HFG
********** * * ********* * *********************** * *** ***
K-EFTP--PVQA-AYQKVVAGVANALAHKYH KD-FTPEL--QAS-YQKVVAGVANALAHKYH
* *** ** *****************
ヒトと馬：
ヒトとゴリラ：
大域アライメント計算の例題
２つの例題配列：AGCGTAG ， GTCAGA
置換度（置換スコア）とギャップスコア：
アライメント：AG-C-GTAG -GTCAG-A-
* * * *
スコア：
0+1+0+1+0+1+0+1+0 = 4
AGCGTAG- GTC--AGA
* **
スコア：
(-1)+(-1)+1+0+0+1+1+0 = 1
AGCGTAG GTCAGA-
* *
スコア：
(-1)+(-1)+1+(-1)+(-1)+1+0 = -2
大域アライメントの数
最長共通部分配列（ＬＣＳ）：
２本の配列に共通な部分配列で最長のもの
大域アライメントの数（ギャップ挿入の場合）：長さ
n
の２本の配列に対して：n n n
n n
n
n 2
2)
! )(
! (
)!
2 2 (
GAGGTTATCAAAAG
GAGGATAACAAGGC G
・G ・ T ・ T ・ C ・ A ・ G
G
・A
・A
・T
・A
・C
・A
k
個取ってくるk n
C
k n
C
n n n
k
k n k
n
C C
2C
1
動的計画法（アルゴリズム）
動的計画法（ dynamic programming, DP ）は，
計算機による配列解析の中核である
どのような場合に，ＤＰは適用できるか？
① Optimal substructure:
全体の問題に対する最適解は，その中に部分問題に対する 最適解を含んでいる② Overlapping subproblems:
部分問題の空間が十分小さい
異なる部分問題の数は，入力サイズの多項式くらいの大きさ
ＤＰは，各部分問題を一度だけ解き，テーブルに確保して，必要になった時に参照する
大域アライメントアルゴリズム
①
（Needleman-Wunsch
）アルゴリズムの基本的アイデア：より小さな部分配列の最適アライメントを一つ前の解として，
最適なアライメントを次々と組み上げていく
② Optimal substructure of LCS:
とする の
と を
を入力列
LCS
,
2 1
2 1 2
1
Y X
z z
z Z
y y
y Y
x x
x X
k
n m
LCS
(1) x
m y
n ならば，z
k x
m y
n であり，かつZ
k1はX
m1とY
n1のLCS
(2) x
m y
n ならば，z
k x
m のとき，Z
はX
m1とY
のLCS
(3) x
m y
n ならば，z
k y
n のとき，Z
はX
とY
n1 の動的計画法の例題：石取りゲーム
ｎ個の石の山
ゲームのルール：
① プレイヤーは二人で，交互に山から石をとる
② 片方の山から1つ，もしくは両方の山から1つずつ石を 取ることができる
③ 最後に石を取った方が勝ち
ｍ個の石の山
動的計画法の例題：石取りゲーム
0 1 2 3 4 5 6 7 8 9 10
0 W
1 W W
2 3 4 5 6 7 8 9 10
W
：先手が勝つL
：先手が負ける ｍ：石の数ｎ：石の数
大域アライメントアルゴリズム
①
を と の最適アライメントのスコア②
初期化：③
再帰式：④
が と の最適アライメントの値⑤
アライメントを求めるには， から に至ったパス を からトレースバック) , ( i j
F x
1x
2 x
iy
1y
2 y
jd j j
F d i i
F
F ( 0 , 0 ) 0 , ( , 0 ) , ( 0 , )
d
はギャップペナルティ
d j
i F
d j
i F
y x s j
i F j
i F
j i
) 1 ,
(
) , 1 (
) , ( )
1 ,
1 ( max
) , (
) , ( m n
F X Y
) , ( m n F
) 0 , 0 ( F
)
,
( m n
F
i 0 1 2 3 4 5 6
j G T C A G A
0
1 A
2 G
3 C
4 G
5 T
6 A
7 G
0 0 0 0 0 0 0
0 0 0 1 1 1
1 1 1 1 2 2
1 1 2 2 2 2
1 1 2 2 3
0 0 0 0 0 0 0
3
1 2 2 2 3 3
1 2 2 3 3 4
1 2 2 3 4 4
置換スコア： ギャップスコア
i 0 1 2 3 4 5 6
j G T C A G A
0 0 0 0 0 0 0 0
1 A 0 0 0 0 1 1 1
2 G 0 1 1 1 1 2 2
3 C 0 1 1 2 2 2 2
4 G 0 1 1 2 2 3 3
5 T 0 1 2 2 2 3 3
6 A 0 1 2 2 3 3 4
7 G 0 1 2 2 3 4 4
G
G
G
G
C
C
A
A
-GTCAG-A-
AG-C-GTAG
局所アライメントアルゴリズム
①
と の部分配列間の最適なアライメント②
共通のドメインの発見など③ Smith-Waterman
アルゴリズム④
初期化：⑤
再帰式：⑥
最大スコア を行列中から探索し，そこから0
が格納 されたセルに到達するまでトレースバック0 ) , 0 ( , 0 ) 0 , ( , 0 ) 0 , 0
( F i F j
F
d j
i F
d j
i F
y x s j
i j F
i
F
i j) 1 ,
(
) , 1 (
) , ( )
1 ,
1 ( 0 max )
, (
X Y
)
,
( i j
F
局所アライメントアルゴリズム
参考：大域アライメントアルゴリズム
スコア行列
① スコア行列（置換行列）の精度は，アライメントの 精度に影響
アミノ酸配列の場合，進化過程における相対的な置換 のしやすさを反映
塩基（DNA)
配列の場合，マッチ＋１，アンマッチ０と いった簡単なスコア② 信頼できる既存のアライメントから統計的手法に よりスコア行列を導出
PAM 行列（ Dayhoff のアミノ酸置換行列）
BLOSUM 行列（ブロックアミノ酸置換行列）
スコア行列
① PAM
行列（Dayhoff
のアミノ酸置換行列）
先祖の共通のタンパク質ファミリから多数のタンパク質を集め，置換 の頻度を調べて分子進化学的に求めた．アミノ酸配列で100
残基あ たり1
個の突然変異が起きるという進化上の時間の単位PAM
を導入．1PAM
の間にアミノ酸i
がアミノ酸j
に置換される頻度を求める．② BLOSUM
行列（ブロックアミノ酸置換行列）
より新しいデータのアライメントからアミノ酸変異の統計データを獲得． BLOSUM50, BLOSUM62, BLOSUM80,
など．
小さい数字の行列は進化的に遠縁の配列の比較に，大きい数字の 行列は近縁の配列の比較に，不明の場合にはBLOSUM62
を推奨 BLOSUM50
はギャップあり，BLOSUM62
はギャップなしで利用 BLAST
などで利用．CLUSTALW に おける
BLOSUM スコア
行列
参考： BLOSUM50 スコア行列
スコア行列の導出
① 頻度の比の対数をスコアとする
b a
ab
q q b p
a
s ( , ) log
：文字
a
が独立に起こる確率（頻度）q
a：文字
a
とb
がアラインされたペアとして起こる確率（
a
とb
が共通の祖先から分岐してきた確率と考える）p
aba b
文字のペアa
とb
が，偶然に“対”になるのに比べて，どれだけ 本当に“対”になる確率が大きいかを示したもの
対数を取ることにより，加法性をもつスコアリングシステムを得るスコア行列の導出
② BLOSUM“L” 行列の求め方：
–
既存の多くの配列のアライメントを求め，ギャップ無しの領 域（ブロック）を集める–
残基がL
％ 以上一致しているものを同一クラスタに集める–
あるクラスタの残基a
が別のクラスタの残基b
にアライメントされる確率
p
ab を計算 （ただし，各クラスタの大きさで 割った重みをつける）–
ある残基a
が独立に起こる確率q
a を計算– s
（a,b)=log(p
ab/q
aq
b)
を計算して，スケーリングして，近傍の 整数値に丸めるBLOSUM “75” の導出
①
タンパク質ファミリごとのマルチプルアライメントから ブロックを取り出す–
ブロックとは，良く保存されたギャップを含まないアライメント の領域②
ブロック内の配列の偏りを取り除くために，一致度が75%
以上の配列をひとつにまとめるblock 1 block 2
BABA BABC AACC
CBB CBB ABC AAC
１クラスタ
BLOSUM75 の導出
③
ブロックからアミノ酸残基の出現確率（頻度）を数えるアミノ酸 出現確率
q a
A
B
C 17
2 / 11 17
2 4 3
17 5 17
2 1 8
17 2 / 13 17
2 5 3
block 1 block 2
BABA BABC AACC
CBB
CBB
ABC
AAC
BLOSUM75 の導出
④
ブロックからアライメントされたアミノ酸残基ペアの出現確率と その２つの残基が独立に同時に出現する確率を計算する残基ペア ペア出現確率
A to A A to B A to C B to B B to C C to C
13 2 / 3
13 3 13
1
13 2 2 / 1
13 2 / 5
13 3
3 3 3 4 2
13 2
block 1 block 2
BABA BABC AACC
CBB CBB ABC AAC
独立同時確率
17 2 / 11 17
2 / 11
17 2 / 11 17
2 5
17 5 17
5
17 2 / 11 17
2 / 2 13
17 5 17
2 / 2 13
17 2 / 13 17
2 / 13
A B
B A
対になる
２通りの場合
p ab q a q b
BLOSUM75 の導出
⑤
対数尤度を計算し，さらにスケーリング（ここでは，２倍して ハーフビットに）して，近傍の整数値に丸める残基ペア ペア確率
A to A A to B A to C B to B B to C C to C
13 2 / 3
13 3 13
1 13
2 / 5
13 3 13
2
同時確率
289 4 / 121
289 55 289
25 289
2 / 143
289 65 289
4 / 169
log
2
2同時確率 ペアの出現頻度
スコア行列28 . 0
56 . 0
34 . 0
73 . 0
07 . 0
15 . 0
0 1 0 1 0 0
アライメントに対するスコアの考え方
アミノ酸配列のアライメントスコアの問題点：
①
それぞれのアミノ酸のペアに対する出現頻度の比の対数 の考え方は問題なし②
進化的にまったく類縁関係にないアミノ酸配列のペアに対 してもスコア（正の値）は計算される（例えば，ランダム配列 のアライメントスコアは，平均５０～６０位の値になる）③
このスコアは，位置特異的なスコアでない④
アライメントのスコアは，長さに依存する傾向（より長い配 列ほどアライメントのスコアは高くなる傾向）があるi 0 1 2 3 4 5 6 7 8 j
0 1 2 3 4 5 6 7
局所アライメント演習問題 学籍番号： 名前：
局所アライメント：
