バイオインフォマティクス ( 第 3 回 ) 慶應義塾大学生命情報学科 榊原康文
アセンブリの演習問題 ( 解 ) CGTCCGT CATCG 5 3 4 ATCCAT TCCGTAT 5 3 3 4 GTATC CGTCCGT-------- --TCCGTAT------ -----GTATC----- -------ATCCAT-- ----------CATCG =============== CGTCCGTATCCATCG
配列解析 ( ペアワイズアライメント ) ペアワイズアライメント 最長共通部分配列 (LCS) 3 大域アライメント, 局所アライメント 4 スコア行列 ( 置換行列 )
相同性検索 ( アライメント ) の威力 サル肉腫ウイルスのがん遺伝子シス (sis) とヒトの血小板 由来増殖因子 (PDGF) のアミノ酸配列が一致している ( そっくりである ) ことが発見された (983) ( がん遺伝子の発見, 中公新書 ) sis : simian sarcoma virus この発見は つの意味において驚きをもって迎えられた がん遺伝子が正常な細胞の増殖 分化や個体発生を司る遺伝子とほとんど同じものであることが初めて具体的に明らかにされた ( がん遺伝子と増殖因子が結びついた ) その発見が試験管の中の実験ではなく, コンピュータに よるホモロジー検索の結果得られた
相同性検索 Doolittleによるがん遺伝子の発見 Doolittleがそれまでに構築してきたデータベース 相同性検索プログラム 総当りの仕事もいとわないコンピュータ BLASTによるデータベース検索 入力配列 DNA 配列 アミノ酸配列 類似遺伝子アノテーション ゲノムデータベース
相同性検索 ( アライメント ) の威力 () P6 タンパク質遺伝子 : サイクリン依存性キナーゼ 4(CDK4, 細胞増殖促進 ) の阻害因子 3 実は, がん抑制遺伝子の一つ 発見の過程において,GENBANK と相同性検索が威力を発揮 (994) ( ミリアッド ジェネティクス社のカムは ) メラノーマと呼ばれる皮膚がんの組織から, ある遺伝子を実験によって同定していた しかし, その遺伝子の正体がわからなかったために, 頻繁に GENBANK 上で相同性検索を行う 3 ある日,GENBANK に最近登録された p6 遺伝子と皮膚がん遺伝子の相同性が非常に高いことを検索から発見し, その正体を突き止めた ( がん遺伝子を追う, 朝日新聞社 )
アライメントからわかること 配列と配列がもつ情報との関係が十分に解明されていないため, 本の配列だけから生物学的な情報を抽出することは困難 配列を比較する 生物配列は進化によりダイナミックに変化する : 点突然変異 ( 置換, 挿入, 欠失 ) 3 4 5 未知の遺伝子配列に類似である, 機能が既知の遺伝子を検索する 遺伝子機能の推定 ゲノム配列中に既知の遺伝子配列と相同な領域を発見する ゲノム配列からの遺伝子の発見 生物種間の共通遺伝子の配列をアライメントにより比べることにより, 配列間の進化的な関係を計算 分子進化系統の推定
最適なアライメントを求める 与えられたスコア ( 置換度 ) に関して, 最適なアライメントを求める高速なアルゴリズム + 数学的に最適なアライメントが, 生物的に真に最適なアライメントになるためのスコア行列 問い合わせ配列 高速なアルゴリズム スコア行列 数学的に最適な配列 生物的に最適な配列
配列のアライメント つの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 置換度 ( 置換スコア ) とギャップスコア : アライメント : AGCGTAG GTCAGA- * * AG-C-GTAG -GTCAG-A- * * * * AGCGTAG- GTC--AGA * ** スコア : (-)+(-)++(-)+(-)++ = - スコア : ++++++++ = 4 スコア : (-)+(-)++++++ =
大域アライメントの数 最長共通部分配列 (LCS): 本の配列に共通な部分配列で最長のもの 大域アライメントの数 ( ギャップ挿入の場合 ): 長さ n の 本の配列に対して : GAGGTTATCAAAAG G G T T C A G k 個取ってくる G A A T A C A n C k C n k n k nckn Ck n C n GAGGATAACAAGGC n n (n)! ( n!)( n!) n n
動的計画法 ( アルゴリズム ) 動的計画法 (dynamic programming, DP) は, 計算機による配列解析の中核である どのような場合に,DPは適用できるか? Optimal substructure: 全体の問題に対する最適解は, その中に部分問題に対する 最適解を含んでいる Overlapping subproblems: 部分問題の空間が十分小さい 異なる部分問題の数は, 入力サイズの多項式くらいの大きさ DP は, 各部分問題を一度だけ解き, テーブルに確保して, 必要になった時に参照する
大域アライメントアルゴリズム (Needleman-Wunsch) アルゴリズムの基本的アイデア : より小さな部分配列の最適アライメントを一つ前の解として, 最適なアライメントを次々と組み上げていく Optimal substructure of LCS: とするのとをを入力列 LCS, Y X z z z Z y y y Y x x x X k n m LCS () のとはであり, かつならば, n m k n m k n m Y X Z y x z y x () の LCS とはのとき, ならば, Y X Z x z y x m m k n m (3) の LCS とはのとき, ならば, n n k n m Y X Z y z y x
動的計画法の例題 : 石取りゲーム n 個の石の山 m 個の石の山 ゲームのルール : プレイヤーは二人で, 交互に山から石をとる 片方の山からつ, もしくは両方の山からつずつ石を取ることができる 3 最後に石を取った方が勝ち
n: 石の数 動的計画法の例題 : 石取りゲーム W: 先手が勝つ L: 先手が負ける m: 石の数 3 4 5 6 7 8 9 W W W 3 4 5 6 7 8 9
大域アライメントアルゴリズム を x x x と y y y の最適アライメントのスコア F( i, j) 初期化 : 3 再帰式 : F( i, j) i j (, ), F( i, ) i d, F(, j) j d F max d はギャップペナルティ F( i, F( i, F( i, j ) s( x, j) d j ) d i y j ) 4 がとの最適アライメントの値 F( m, n) X Y 5 アライメントを求めるには, からに至ったパス を F( m, n) からトレースバック F(, ) F( m, n)
i 3 4 5 6 j G T C A G A A G 3 C 4 G 3 3 5 T 3 3 6 A 7 G 3 3 4 3 4 4 置換スコア : ギャップスコア
i 3 4 5 6 j G T C A G A A G G C 3 C G 4 G 3 3 5 T 3 3 A 6 A 3 3 4 7 G 3 4 4 -GTCAG-A- AG-C-GTAG
局所アライメントアルゴリズム との部分配列間の最適なアライメント X Y 共通のドメインの発見など 3 Smith-Waterman アルゴリズム 4 初期化 : 5 再帰式 : F(, ), F( i, ), F(, j) F( i, j) max F( i, j ) s( x F( i, j) d F( i, j ) d 6 最大スコアを行列中から探索し, そこから が格納 F( i, j) されたセルに到達するまでトレースバック i, y j )
局所アライメントアルゴリズム
参考 : 大域アライメントアルゴリズム
スコア行列 スコア行列 ( 置換行列 ) の精度は, アライメントの精度に影響 アミノ酸配列の場合, 進化過程における相対的な置換のしやすさを反映 塩基 (DNA) 配列の場合, マッチ+, アンマッチといった簡単なスコア 信頼できる既存のアライメントから統計的手法によりスコア行列を導出 PAM 行列 (Dayhoffのアミノ酸置換行列) BLOSUM 行列 ( ブロックアミノ酸置換行列 )
スコア行列 PAM 行列 (Dayhoff のアミノ酸置換行列 ) 先祖の共通のタンパク質ファミリから多数のタンパク質を集め, 置換 の頻度を調べて分子進化学的に求めた. アミノ酸配列で 残基あ たり 個の突然変異が起きるという進化上の時間の単位 PAM を導入. PAM の間にアミノ酸 i がアミノ酸 j に置換される頻度を求める. BLOSUM 行列 ( ブロックアミノ酸置換行列 ) より新しいデータのアライメントからアミノ酸変異の統計データを獲得. BLOSUM5, BLOSUM6, BLOSUM8, など. 小さい数字の行列は進化的に遠縁の配列の比較に, 大きい数字の行列は近縁の配列の比較に, 不明の場合には BLOSUM6 を推奨 BLOSUM5 はギャップあり,BLOSUM6 はギャップなしで利用 BLAST などで利用.
CLUSTALW における BLOSUM スコア行列
参考 :BLOSUM5 スコア行列
スコア行列の導出 頻度の比の対数をスコアとする pab s ( a, b) log qaq b q a p ab : 文字 a が独立に起こる確率 ( 頻度 ) : 文字 a と b がアラインされたペアとして起こる確率 (a と b が共通の祖先から分岐してきた確率と考える ) a b 文字のペア a と b が, 偶然に 対 になるのに比べて, どれだけ本当に 対 になる確率が大きいかを示したもの 対数を取ることにより, 加法性をもつスコアリングシステムを得る
スコア行列の導出 BLOSUM L 行列の求め方 : 既存の多くの配列のアライメントを求め, ギャップ無しの領域 ( ブロック ) を集める 残基が L % 以上一致しているものを同一クラスタに集める あるクラスタの残基 a が別のクラスタの残基 b にアライメントされる確率 p ab を計算 ( ただし, 各クラスタの大きさで割った重みをつける ) ある残基 a が独立に起こる確率 q a を計算 s(a,b)=log(p ab /q a q b ) を計算して, スケーリングして, 近傍の整数値に丸める
BLOSUM 75 の導出 タンパク質ファミリごとのマルチプルアライメントから ブロックを取り出す ブロックとは, 良く保存されたギャップを含まないアライメントの領域 ブロック内の配列の偏りを取り除くために, 一致度が 75% 以上の配列をひとつにまとめる block block BABA BABC AACC CBB CBB ABC AAC クラスタ
BLOSUM75 の導出 3 ブロックからアミノ酸残基の出現確率 ( 頻度 ) を数える block block アミノ酸 出現確率 q a BABA BABC AACC CBB CBB ABC AAC A B C 3 5 7 8 7 3 4 7 3/ 7 5 7 / 7
4 BLOSUM75 の導出 ブロックからアライメントされたアミノ酸残基ペアの出現確率とその つの残基が独立に同時に出現する確率を計算する block block BABA BABC AACC A B 対になる B A 通りの場合 CBB CBB ABC AAC 残基ペア A to A A to B A to C B to B B to C C to C 3 ペア出現確率 5 / 3 4 3 3 3 p ab 3 3 / 3 3 3 3 3/ 3 独立同時確率 q a q b 3/ 3/ 7 7 3/ 5 7 7 3/ / 7 7 5 5 7 7 5 / 7 7 / / 7 7
5 BLOSUM75 の導出 対数尤度を計算し, さらにスケーリング ( ここでは, 倍してハーフビットに ) して, 近傍の整数値に丸める 残基ペア ペア確率 同時確率 log ペアの出現頻度同時確率 スコア行列 A to A A to B A to C B to B B to C C to C 3 3 3 5 / 3 3 3 3 3/ 3 69/ 4 89 65 89 43/ 89 5 89 55 89 / 4 89.5.7.73.34.56.8
アライメントに対するスコアの考え方 アミノ酸配列のアライメントスコアの問題点 : それぞれのアミノ酸のペアに対する出現頻度の比の対数の考え方は問題なし 進化的にまったく類縁関係にないアミノ酸配列のペアに対してもスコア ( 正の値 ) は計算される ( 例えば, ランダム配列のアライメントスコアは, 平均 5~6 位の値になる ) 3 このスコアは, 位置特異的なスコアでない 4 アライメントのスコアは, 長さに依存する傾向 ( より長い配列ほどアライメントのスコアは高くなる傾向 ) がある
局所アライメント演習問題学籍番号 : 名前 : j i 3 4 5 6 7 8 3 4 5 6 7 局所アライメント :