バイオインフォマティクスⅠ

Size: px

Start display at page:

Download "バイオインフォマティクスⅠ"

ときあきくぼ
5 years ago
Views:

1 バイオインフォマティクス ( 第 6 回 ) 慶應義塾大学生命情報学科榊原康文

2 入力ベクトル階層クラスタリングの解 : [1] [2] [3] : B: C: D: D 系統樹距離行列 : B: C: B: C: D: B C

3 データベース検索 1 データベースの高速検索問い合わせ配列に類似した配列をデータベースより見出す作業遺伝子配列のデータベースの大きさは膨大であるため, アライメントなどの動的計画法に基づく方法では時間がかかりすぎる 2 FST と BLST 相同な配列では, きわめて短い領域ではあるが非常に類似度の高い ( ギャップのない ) 領域語が保存されている語を単位とするヒットに基づく局所的な比較により類似配列を検索する

4 データベース検索 BLST によるデータベース検索膨大なゲノムデータベースからの検索には高速化が必須入力配列 DN 配列アミノ酸配列類似遺伝子アノテーションゲノムデータベース

5 BLST FSTのテーブル照合を, 有限オートマトンを用いた検索方法 (ho-corasickアルゴリズム) により改良 ( 高速で柔軟な語の検索が可能 ) Basic Local lignment Search Tool の略 1 データベース中に, 問い合わせ配列に含まれる領域と非常に類似度の高い領域を見つける ( 有限オートマトン ) 2 見つけた領域を伸張する (HSP 領域 ) 3 上位にランクされた配列と問い合わせ配列の ( ギャップなし ) アライメントを報告する

6 BLST 1 問い合わせ配列を語 ( ワード ) に分割し, さらに各語に類似した語のリストを生成する語とは, 配列中の固定長 ( アミノ酸の場合は 3 残基 ) の連続したアミノ酸配列問い合わせ配列を N 末端から C 末端まで走査し, 語を切り出し, それに類似した語もすべてリストに加える類似の定義は, スコア行列および閾値 T を用いて,T を超えるスコアを持つ語同士はすべて類似と見なすデータベースの配列の中に, リストに蓄えられた語と一致するすべての箇所 ( ヒット ) を, 有限オートマトンを用いて検索する ho-corasick アルゴリズム

7 BLST 1 問い合わせ配列を語 ( ワード ) に分割し, さらに各語に類似した語のリスト L を生成する問い合わせ配列 : DDVIILKE 語に分割 : 類似語 : DDV,DVI,VII,IIL,ILK,LKE DEV,DII,VVI,VIL,VLK,IKE, EDV,DIV,VIV,VVL,VIK,LKD, EEV,DVV,...

8 BLST 1 データベースの配列 : リスト L の語を部分にもつ配列を検索 (ho-corasick のアルゴリズム )

9 BLST 2 3 検出されたヒット ( 語 ) を起点として, その N 末端,C 末端に向けて, 問い合わせ配列とデータベース中の配列との残基間対応を拡張し, ギャップを入れないアライメントを構築するアライメントスコアが増大する限り拡張を続けるアライメントスコアが閾値を超えた場合,HSP 領域 (Highscoring Segment Pair) として報告する最後に HSP を連結して最終的アライメントとして出力する問い合わせ配列 : マッチした部分を伸ばす配列データベース

10 ho-corasick 法 ho-corasick の文字列照合オートマトン : 検索対象配列 X 中に語のリスト L={w 1,w 2,,w k } のどれかが出現するか否かを調べるアルゴリズム L={ B, BC } 有限オートマトンを作成 : B,C 次の遷移語の照合途中の遷移 0 1 B 2 C B B,C C B C 3 4 受理状態

11 L={ B, BC } ho-corasick 法 X = CBBBCCCCBBBBCCC B,C 0 1 B 2 C B B,C C B C 3 4

12 L={ B, BC } ho-corasick 法 X = CBBBCCCCBBBBCCC B,C ヒット! 0 1 B 2 C B B,C C B C 3 4

13 L={ B, BC } ho-corasick 法 X = CBBBCCCCBBBBCCC B,C 2 回目ヒット! 0 1 B 2 C B B,C C B C 3 4

14 L={ B, BC } ho-corasick 法 X = CBBBCCCCBBBBCCC B,C 3 回目ヒット! 0 1 B 2 C B B,C B C 3 4 C

15 L={ B, BC } ho-corasick 法 X = CBBBCCCCBBBBCCC B,C 0 1 B 2 C B B,C C B C 回目ヒット!

16 ho-corasick 法定理リスト L 中の文字の総計を m, データベースの配列 X の長さを n とする. オートマトンの生成に O(m) 時間, 文字列照合するのに O(n) 時間かかる. 参考文献 lfred V. ho, Margaret J. Corasick: Efficient String Matching: n id to Bibliographic Search. CCM 18(6): (1975)

17 検索のスコア値配列類似性の統計的評価 : BLST の最大の特徴は, ギャップなし局所アライメントの統計学的考察に基づく配列類似性についての評価の組み込みにある E-value Score E Sequences producing significant alignments: (bits) Value gi sp P04637 P53_HUMN Cellular tumor antigen p53 (T gi sp P13481 P53_CERE Cellular tumor antigen p53 (T gi sp P56424 P53_MCMU Cellular tumor antigen p53 ( gi sp P56423 P53_MCF Cellular tumor antigen p53 ( gi sp Q9TT1 P53_TUPGB Cellular tumor antigen p gi sp O36006 P53_MRMO Cellular tumor antigen p e-175 gi sp Q95330 P53_RBIT Cellular tumor antigen p53 ( e-175

18 1 ランダム配列モデル : ランダム配列モデルアミノ酸 20 種類の組成 P 1, P 2,, P 20 が与えられたとき, 配列中の各位置におけるアミノ酸の出現確率はこの組成のみに依存し, お互いに独立であるモデルランダムな配列同士の比較が行われるとき, アライメントのスコアがどのような分布になるのかを解析した (Karlin & ltschul, 90) 互いに関係がないのにも関わらずスコアの高いアライメントが偶然にヒットするという可能性を考える

19 2 極値分布 : ランダム配列モデル ( 関連性のない )2 つのランダム配列のアライメントのスコアの分布は極値分布に従う (Gumbel) 極値分布 : f ( x) = exp[ x e x ] 特徴 : 高スコア領域に裾が歪んでいる ( 参考 ) 正規分布 : f ( x) = 1 exp[ x ] 特徴 : 左右対称の釣鐘型 3 ランダム配列のスコアとの比を取ることにより, 類似度の判定を高い精度で行うことができる

20 ランダム配列のスコア分布タンパク質の配列長に対するスコア分布ランダム配列スコアの極値分布スコア頻度偶然性が高い偶然性は低いタンパク質の長さ配列長ごとに正規化したスコアの分布

21 3 E-Value: ランダム配列モデル ( 関連性のない ) ランダムな 2 つの配列 ( 長さ m と n) が, スコア S 以上のアライメントとして出現する回数の期待値 E - value = E( S) = Kmn exp( S) = mn K exp( S) = mn P - value m は問い合わせ配列長,n はデータベースのサイズそのデータベースに対して偶然そのスコア以上の値が出るヒット数 (false positive) の期待値経験的には0.0001から0.01ぐらいの閾値が用いられる検索結果のE-valueが低い値であるほど, その結果は偶然でない確かな一致であるとみなすことができ, 統計的に優位であると言える E-value は, 配列長とデータベースの大きさに比例

22 進化系統樹とは約 40 億年前ころ ( 明確な証拠はない ) に最初の生命が誕生系統 (phylogeny): 地球上のすべての生物は共通の祖先から進化したと考えたときの, 種間の進化的な関係進化系統樹 (phylogenetic tree) で表現生物学的な分類体系 ( 参考 ): 生物を形質 ( 形態, 機能, 成分 ) が似たもの同士に分けて体系づける界 ( かい ) 門 ( もん ) 綱 ( こう ) 目 ( もく ) 科 ( か ) 属 ( ぞく ) 種 ( しゅ ) 近年では, 伝統的な分類体系を系統学の知見を反映させた体系に組替える

23 分子 ( 配列 ) 進化系統 : 分子進化系統樹すべての配列がある共通祖先の共通遺伝子から受け継がれたと考えたときの, 配列間の進化的な関係注意点 : ( 形態学的な ) 生物種の進化系統と配列に基づく分子進化系統は常に一致するとは限らないどの配列 ( タンパク質,RN 配列など ) を基にするかによっても得られる分子進化系統樹は異なる祖先の配列は手に入らない進化のモデル仮説が必要コンピュータと数学統計が主な解析ツールとなる

24 生命の系統樹をつくるためには rrn またはミトコンドリアの配列が用いられるすべての生物に普遍的に存在充分な配列変異の存在, 変異の安定性水平伝播があるために, 進化系統樹は編目状になる

25 系統樹に関する用語節点 (node), 枝 (edge), 枝長 ( 進化の程度 ), 根 (root), 葉 (leaf) 有根系統樹 (rooted), 無根系統樹 (unrooted) 基本的に二分木有根系統樹無根系統樹

26 無根系統樹, 有根系統樹無根系統樹数学的にアルゴリズム的に扱いやすい Chicken を外群とした時の有根系統樹生物的進化に関連した分岐を表す

27 時間進化系統の簡単なモデル T G C CG T CT C CG T C G C C C C C G C T C G C C T C 共通祖先の配列進化系統樹枝に沿って変異節点で種分化

28 進化系統樹の ( 再 ) 構築問題 T G C CG T C T C CG T C G C C 系統樹は?

29 (Doolittle, 2000) 16S rrn に基づく生命の進化系統樹

30 進化系統樹の ( 再 ) 構築問題系統樹に沿って進化したと考えられる生体分子のアライメントが与えられたときに, 進化系統樹を構築 ( 発見 ) する問題 Human fqtpmviilqaimgsatlamtliift Chimp fqtpmiiifqaimgsatlaltliift Gorilla lqtpmviifqaimgsatlamtliift Seal fqlpmviifqaiiggatlalafitft Cow fqtpmviifqaiiggatlalalitft Fin Whale lqtfmviifqaimgettlalafitft Blue Whale lqtfmviifqaimgettlvlaiitft Rat fqismiiifqaimggatlvlatitfi Mouse fqismiiifqaimggatlvlatitfi Chicken pqismiaffqaimggatlfaatitfi? Chicken Blue Whale Fin Whale Seal Cow Mouse Rat Chimp Human Gorilla 問題のステップ : 1. 系統樹 Tのトポロジー ( 構造 ) の決定 2. 系統樹 Tにおける枝の長さの決定 3. 系統樹 Tにおける根の位置の決定 root

31 系統樹の推定手法距離に基づく手法 : UPGM 法, 近隣結合法分子時計を仮定, 加法性を利用して少しずつ構築系統樹の評価に基づく手法 : 最節約法, 最尤法まず, 系統樹の評価方法を決めておく最節約法 : 祖先配列から葉までの置換数が小さい最尤法 : 尤度 ( 系統樹からデータ配列を得る確率 ) が高い評価が最良になるような系統樹を求める数え上げ : 可能な系統樹から最も評価の良いものを選ぶメトロポリス法 : 現在の系統樹をちょっとずつ改良してゆくなどなど

32 最 ( 大 ) 節約法全ての可能なトポロジーの ( 無根 ) 系統樹について計算を行う一般に計算量が膨大になるトポロジー : 葉に与えられた配列を割り当て, 系統樹の形を一つ定めたもの各トポロジーに対して, 最小の置換数で説明できる祖先節点の配列を決定するすべてのトポロジーの中から, 最小の置換数で説明できる系統樹を選ぶアライメントによって並べられた ( 縦の ) カラム全てについて解析を行う

33 最節約法祖先節点の決定 : 系統樹全体の置換数の和が最小になるように決定各カラムは独立に計算可能入力 :4 つの DN 配列 G GG G

34 距離に基づく手法配列 : CGCGTTGGGCGTGGCC 配列 B: CGCGTTGGGCGCGGTT 配列 C: CGCTTGTGTGTT 配列 D: CCTTGGTGTTT B 間の塩基置換の数距離テーブル : B C D B 6 7 C 3 D

35 UPGM 法 (unweighted pair group method using arithmetic averages) 1. アライメントから初期の距離テーブルを計算する 2. 距離が一番近いものを近隣ペアとする 3. クラスタ間距離 = 配列同士の距離の平均 4. ペアを一つのノードとして, 距離テーブルを再構築する基本的に, 群間平均法 ( クラスタ間の平均距離 ) を用いた階層クラスタリング分子時計を仮定 UPGM 法の発展形が,NJ 法 ( 近隣結合法 )

36 具体例の計算初期距離テーブル B C D E B C D 10 E DE を近隣ペアとする B C D E B C D 10 E 新しい距離テーブル B C DE B C 19 DE D と E の平均. 12 B E C 4 D

37 UPGM 法 (unweighted pair group method using arithmetic averages) 1. 各配列のみからなるクラスタを作る 2. 距離 d ij が最小のペアを x i, x j 求める 3. クラスタ x i, x j を融合して x k を作る 4. クラスタ間距離を再計算 5. 親節点 x k を高さ d ij / 2 の位置に追加 6. クラスタが2 個だけになったら, 根を高さ d ij / 2 に置いて終了

39 外群有根系統樹の根の位置の特定調べてる配列よりも遠縁である特定の配列系統樹外群ある系統樹について, 根の位置を限定する助けとなる外群を使うときに気をつけること配列的に似ていて, かつ, 充分な違いが必要あまりに遠縁すぎるとランダムな要素を含んでしまう

40 Hybridization( 雑種形成 ) Hybridization は, 異なる種の間の交配によって, 染色体を組み合わせることにより起こる Hybridization は, 一般に植物, 魚, カエルに限定される水あさ (water hemp) 雑種ブタ草 pigs weed

41 遺伝子の水平伝播バクテリアでは, 遺伝子を交換するいくつかのメカニズムが知られている Transformation( 形質転換 ) Conjugation( 接合 ) Transduction( 形質導入 ) ( 例 ) 大腸菌と O157 株 ( ベロ毒素 )

42 網状進化 (Reticulate Evolution) の簡単なモデル b 1 a h c b 3 P Q 祖先ゲノム

43 今後の講義の予定 5 月 28 日 : 佐藤健吾先生 ( 第 1 回 ) 6 月 4 日 : 休講 ( 慶早戦あるなしに関わらず ) 6 月 11 日 : 医学部放射線科学 ( 診断 ) 橋本正弘講師講演 6 月 18 日 : 佐藤健吾先生 ( 第 2 回 ) 6 月 25 日 : 佐藤健吾先生 ( 第 3 回 ) 7 月 2 日 : 佐藤健吾先生 ( 第 4 回 ) 7 月 9 日 : 休講 ( 学会出張のため ) 7 月 16 日 ( 海の日 ): 授業内期末試験

44 6 月 11 日 ( 月 ) の授業は慶應義塾大学医学部放射線科学 ( 診断 ) 講師橋本正弘先生特別講演 : 6 月 11 日の講演の予告講演タイトルは未定ですが, 人工知能の CT 検査画像解析などへの応用 ( 出席とります!)

45 7 月 16 日授業内期末試験について試験会場 : 厚生棟大会議室 ( 会場がいつもの教室と異なるので注意!) 試験の要領は通常通り : すべて持ち込み不可遅刻は開始 30 分 ( すなわち,15 時 15 分 ) まで学生証を提示

46 文字列照合の演習問題学籍番号 : 名前 : 例題に示すように,ho-Corasick 文字列照合オートマトンを用いて, 文字列上を探索して, ヒットする位置 ( 受理状態の位置 ) を列挙しなさい. また, 途中の状態遷移も示しなさい.

生命情報学

生命情報学 34 進化系統樹推定阿久津達也京都大学化学研究所バイオインフォマティクスセンター進化系統樹進化系統樹種間もしくは遺伝子間の進化の関係を表す木以前は形態的特徴をもとに構成現在は配列情報をもとに構成有根系統樹と無根系統樹有根系統樹 : 根共通の祖先に対応がある系統樹無根系統樹 : 根のない系統樹いずれも葉にのみラベル種に対応がつく有根系統樹無根系統樹