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

(1)

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

（第６回）

慶應義塾大学生命情報学科

榊原康文

(2)

階層クラスタリングの解：

[1] [2] [3] A: 0 0 0 B: 1 1 1 C: 2 1 2 D: 3 3 3 A: B: C: B: 1.732 C: 3.000 1.414 D: 5.196 3.464 2.449 入力ベクトル A B C D 系統樹距離行列

(3)

データベース検索

①

データベースの高速検索

◆ 問い合わせ配列に類似した配列をデータベースより見出す作業 ◆ 遺伝子配列のデータベースの大きさは膨大であるため，アライメントなどの動的計画法に基づく方法では時間がかかりすぎる

②

_{FASTA と BLAST}

◆ 相同な配列では，きわめて短い領域ではあるが非常に類似度の高い（ギャップのない）領域「語」が保存されている ◆ 「語」を単位とするヒットに基づく局所的な比較により類似配列を検索する

(4)

データベース検索

◆

BLASTによるデータベース検索

⚫

膨大なゲノムデータベースからの検索には高速

化が必須

ゲノムデータベース入力配列 ■DNA配列 ■アミノ酸配列類似遺伝子アノテーション

(5)

BLAST

◆ FASTAのテーブル照合を，有限オートマトンを用いた検索方

法（Aho-Corasickアルゴリズム）により改良（高速で柔軟な語

の検索が可能）

◆ Basic Local Alignment Search Tool の略

① データベース中に，問い合わせ配列に含まれる領域と非常

に類似度の高い領域を見つける（有限オートマトン）

② 見つけた領域を伸張する（HSP領域）

③ 上位にランクされた配列と問い合わせ配列の（ギャップな

(6)

BLAST ①

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

(7)

BLAST ①

◆ 問い合わせ配列を語（ワード）に分割し，さらに各語に類 似した語のリスト L を生成する

問い合わせ配列：

_DDVIILKE

語に分割：

_{DDV,DVI,VII,IIL,ILK,LKE}

類似語：

_{DEV,DII,VVI,VIL,VLK,IKE,}

EDV,DIV,VIV,VVL,VIK,LKD,

EEV,DVV,．．．

(8)

BLAST ①

リスト L の語を部分にもつ配列を検索

(Aho-Corasickのアルゴリズム)

(9)

BLAST ② ③

配列データベースマッチした部分を伸ばす ◆ 検出されたヒット（語）を起点として，そのN末端，C末端に向けて，問い合わせ配列とデータベース中の配列との残基間対応を拡張し，ギャップを入れないアライメントを構築する ◆ アライメントスコアが増大する限り拡張を続ける ◆ アライメントスコアが閾値を超えた場合，HSP領域

（High-scoring Segment Pair）として報告する

◆ 最後にHSPを連結して最終的アライメントとして出力する

(10)

参考文献

Alfred V. Aho, Margaret J. Corasick:

Efficient String Matching: An Aid to Bibliographic Search. CACM 18(6): 333-340 (1975)

「定理」

リスト L 中の文字の総計を m,

データベースの配列 X の長さを n とする．

オートマトンの生成に O(m) 時間，

文字列照合するのに O(n) 時間かかる．

(17)

検索のスコア値

◼

配列類似性の統計的評価：

⚫ ＢＬＡＳＴの最大の特徴は，ギャップなし局所アライメントの統計学的考察に基づく配列類似性についての評価の組み込みにある ⚫ E-value Score E Sequences producing significant alignments: (bits) Value

gi|129369|sp|P04637|P53_HUMAN Cellular tumor antigen p53 (T... 703 0.0

gi|129367|sp|P13481|P53_CERAE Cellular tumor antigen p53 (T... 679 0.0

gi|3024332|sp|P56424|P53_MACMU Cellular tumor antigen p53 (... 679 0.0

gi|3024331|sp|P56423|P53_MACFA Cellular tumor antigen p53 (... 677 0.0

gi|10720194|sp|Q9TTA1|P53_TUPGB Cellular tumor antigen p53 ... 654 0.0

gi|10720190|sp|O36006|P53_MARMO Cellular tumor antigen p53 ... 612 e-175

(18)

ランダム配列モデル

①

ランダム配列モデル：

⚫ アミノ酸２０種類の組成 P₁_{, P}₂, …, P₂₀が与えられたとき，配列中の各位置におけるアミノ酸の出現確率はこの組成のみに依存し，お互いに独立であるモデル ⚫ ランダムな配列同士の比較が行われるとき，アライメントのスコアがどのような分布になるのかを解析した（Karlin & Altschul, 90）

⚫ 互いに関係がないのにも関わらずスコアの高いアライメ

(19)

ランダム配列モデル

②

極値分布：

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

(20)

ランダム配列のスコア分布

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

(21)

ランダム配列モデル

③

E-Value：

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

value

-P

)

exp(

)

exp(

)

(

value

-E



=

−



=

−

=

mn

S

K

mn

S

Kmn

S

E

分子（配列）進化系統：

◼ すべての配列がある共通祖先の共通遺伝子から受け継がれたと考えたときの，配列間の進化的な関係 ◆

注意点：

◼ （形態学的な）生物種の進化系統と配列に基づく分子進化系統は常に一致するとは限らない ◼ どの配列（タンパク質，RNA配列など）を基にするかによっても得られる分子進化系統樹は異なる ◆

祖先の配列は手に入らない

◼ 進化のモデル・仮説が必要 ◼ コンピュータと数学・統計が主な解析ツールとなる

(24)

生命の系統樹をつくるためには

◆

rRNAまたはミトコンドリアの配列が用いられる

◼ すべての生物に普遍的に存在

◼ 充分な配列変異の存在，変異の安定性

(25)

系統樹に関する用語

– 節点（node），枝（edge），枝長（進化の程度），根

（root），葉（leaf）

– 有根系統樹(rooted)，無根系統樹(unrooted)

– 基本的に二分木

有根系統樹無根系統樹

(26)

無根系統樹，有根系統樹

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

(27)

進化系統樹

進化系統の簡単なモデル

A C ACG C C T A C AC C C A G C T A C ACT C CG A T AAC GCC C A G C T TA CG A C 共通祖先の配列時間 ◆枝に沿って変異 ◆節点で種分化

(28)

進化系統樹の（再）構築問題

A C AC T C CG A T AAC GCC C A G C T TA CG 系統樹は？

(29)

16S rRNA に基づく生命の進化系統樹

(30)

進化系統樹の（再）構築問題

Human fqtpmviilqaimgsatlamtliift Chimp fqtpmiiifqaimgsatlaltliift Gorilla lqtpmviifqaimgsatlamtliift Seal fqlpmviifqaiiggatlalafitft Cow fqtpmviifqaiiggatlalalitft

Fin Whale lqtfmviifqaimgettlalafitft Blue Whale lqtfmviifqaimgettlvlaiitft Rat fqismiiifqaimggatlvlatitfi Mouse fqismiiifqaimggatlvlatitfi Chicken pqismiaffqaimggatlfaatitfi Cow root Chicken Seal Fin Whale

Blue Whale _Mouse Rat ChimpHuman Gorilla

?

系統樹に沿って進化したと考えられる生体分子のアライメントが与えられたときに，進化系統樹を構築（発見）する問題問題のステップ： 1. 系統樹Tのトポロジー（構造）の決定 2. 系統樹Tにおける枝の長さの決定 3. 系統樹Tにおける根の位置の決定

(31)

系統樹の推定手法

◆

距離に基づく手法：

– UPGMA法，近隣結合法 • 分子時計を仮定，加法性を利用して少しずつ構築 ◆

系統樹の評価に基づく手法：

– 最節約法，最尤法 • まず，系統樹の評価方法を決めておく – 最節約法：祖先配列から葉までの置換数が小さい – 最尤法：尤度（系統樹からデータ配列を得る確率）が高い • 評価が最良になるような系統樹を求める – 数え上げ：可能な系統樹から最も評価の良いものを選ぶ – メトロポリス法：現在の系統樹をちょっとずつ改良してゆく – などなど

(32)

最（大）節約法

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

(33)

最節約法

入力：４つのDNA配列

AAG

AAA

GGA

AGA

◆祖先節点の決定：系統樹全体の置換数の和が最小になるように決定 ◆各カラムは独立に計算可能

_A

_T

_AA

_T

配列 D：

_AC

_A

_C

_A

_TTG

_A

_G

_T

_GA

_T

_AA

_T

_AAT

A

B

C

D

A

3

7

8 B

6

7 C

3 D

AB間の塩基置換の数

(35)

UPGMA法

（unweighted pair group method using

arithmetic averages）

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

(36)

A B C D E A 22 39 39 41 B 41 41 43 C 18 20 D 10 E

具体例の計算

DEを近隣ペアとする新しい距離テーブル A B C DE A 22 39 40 B 41 42 C 19 DE AD と AE の平均. 初期距離テーブル A B C D E A 22 39 39 41 B 41 41 43 C 18 20 D 10 E A B C D E 10 12 20 9 4 6 5

(37)

UPGMA法

（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. クラスタが２個だけになったら，根を高さ d_ij/ 2 に置いて終了

(38)

(39)

有根系統樹の根の位置の特定

◆

外群

◼ 調べてる配列よりも遠縁である特定の配列 ◆

外群を使うときに気をつけること

◼ 配列的に似ていて，かつ，充分な違いが必要 ◼ あまりに遠縁すぎるとランダムな要素を含んでしまう系統樹外群ある系統樹について，根の位置を限定する助けとなる

(40)

Hybridization（雑種形成）

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

(41)

遺伝子の水平伝播

◆

バクテリアでは，遺伝子を交換するいくつかのメカニ

ズムが知られている

– Transformation（形質転換） – Conjugation（接合） – Transduction（形質導入） http://www.pitt.edu/~heh1/research.html （例）大腸菌とO157株（ベロ毒素）

(42)

網状進化（Reticulate Evolution）の簡単なモデル

a b₁ _h c b₃ P Q 祖先ゲノム

(43)

今後の講義の予定

◆

５月２８日：佐藤健吾先生（第１回）

◆

６月４日：休講（慶早戦あるなしに関わらず）

◆

６月１１日：医学部放射線科学（診断）

６月１１日（月）の授業は

慶應義塾大学医学部放射線科学（診断）講師

橋本正弘先生

特別講演：

「講演タイトルは未定ですが，人工知能のCT検査画像

解析などへの応用」

（出席とります！）

６月１１日の講演の予告

(45)

７月１６日授業内期末試験について

試験会場：厚生棟大会議室（会場がいつもの

教室と異なるので注意！）

試験の要領は通常通り：

◆

すべて持ち込み不可

◆

遅刻は開始３０分（すなわち，１５時１５分）まで

◆

学生証を提示

(46)

文字列照合の演習問題

学籍番号：名前：

例題に示すように，Aho-Corasick 文字列照合オートマトンを用いて，文字列上を探索して，ヒットする位置（受理状態の位置）を列挙しなさい．また，途中の状態遷移も示しなさい．