Microsoft PowerPoint pptx

(1)

生物情報科学第９回 2010.12.02

アラインメント

学術情報基盤センター升屋正人

(2)

本日の内容

• アラインメント • スコア行列 • PAM • _BLOSUM • 配列アラインメント • Needleman-Wunsch • _{Smith-Waterman} • FASTA/BLAST • 配列-構造アラインメント（3D-1D） • データベース（配列・構造）

(3)

バイオインフォマティクス？でまず行うこと

•

DNA(cDNA=mRNA)塩基配列をタンパク質アミ

ノ酸配列に翻訳

• 文字の多様性が５倍 • 類似パターンを見出しやすい • 有意な一致が少なくなる • ゲノム（DNA）に機能はない • FASTA/BLASTなどには翻訳プログラムが付属 • 「タンパク質で検索する」オプションがある •

結局

アミノ酸配列

（タンパク質）のデータベース

検索（

アラインメント

）を行うことになる

(4)

Sensitivityとselectivity

• Sensitivity(検出感度) • 問い合わせ配列が含まれるタンパク質ファミリーをどれだけ多く見つけられるか • Selectivity(選択感度) • 他のファミリーの既知のメンバーをどれだけ偽陽性として見つけないか • 両方が高いことが望ましい • 当然、一方を高くすれば他方が低くなる

(5)

検出感度と選択感度の両方を高く

• Hamming距離 • 文字が一致しない位置の個数 • 同じ長さの配列の場合のみ • Levenshtein距離 • 一方の文字列を他方に変換するために必要な編集操作の数 • 一文字づつの削除、挿入、置換を１とカウント • 異なる長さの文字列でも可能 • どちらも、「どのくらい違うか」を示す値であり、「どのくらい似ているか」ではない • 似ているものほど、値は小さい • 検出感度は高いが偽陽性が多く選択感度が低い • →スコア行列をうまく選ぶ

(6)

スコア行列

• アミノ酸置換パターンによる得点表 • ALA->VALならＸ点、ALA-GLYならＹ点、…など。 • よく似たもの同士の置換得点を高くすることで選択感度を高く • PAMとBLOSUMが代表的 • ギャップペナルティも工夫 • ギャップの挿入に関わるスコア • リニアギャップペナルティ・アフィンギャップペナルティ

(7)

PAM

• M.O. Dayhoff, 1978. Survey of new data and computer

methods of analysis. In M. O. Dayhoff, ed., Atlas of

Protein Sequence and Structure, vol. 5, supp. 3, pp. 29,

National Biomedical Research Foundation, Silver Springs, Maryland.

• まず、PAM1置換行列を作る

• Percent Accepted Mutation（PAM）が1

• PAM＝100アミノ酸残基あたり１個の変異が起きる(固定される)進化上の時間の単位 • タンパク質によって異なる（ヘモグロビン５００万年、ルトルビンβ鎖３０億年） • _{1PAMの間にアミノ酸残基iがアミノ酸残基jに置換される頻度を表にする} • 累乗してPAM行列を作る • よく使われるPAM250は100アミノ酸残基あたり250個の変異 • 配列の一致度20% • _{遠縁のタンパク質をアラインメントできる（高いスコアを得る）}

(8)

Atlas of Protein Sequence and Structure

•

1965-1978

…PIR→UniProtに発展 •

最古の配列データベー

ス

• 最初の配列データベースはゲノムではなくタンパク質 •

アミノ酸の１文字コー

ドを作ったのは

Dayhoff

(9)

BLOSUM

• 既存のデータベースに基づき、遠い類縁関係を見つけられるように工夫した行列 • BLOSUM62がよく用いられる • 「62」はアミノ酸が62%以上一致している配列を平均化するなどして一つの配列とみなして、マトリックスを求めたもの • PAMにとって代わり、現在では主流 • FASTAのデフォルトはBLOSUM50 • アルゴリズムがBLASTとは異なるため経験的にこちら

(10)

スコア行列の選び方

• PAMもBLOSUMも批判は多い • 分子中の部位によってアミノ酸の置換頻度が異なることが反映されていない…など • 経験的に選択 • BLASTでは問い合わせ配列長によって異なる置換行列を用いる • 35以下: PAM30 • _{30∼40: PAM70} • _{50∼85: BLOSUM80} • 85以上: BLOSUM62

(11)

配列アラインメントのアルゴリズム

• ドットマトリックス法 • 一致したら１，不一致なら０ • Needleman-Wunsch • 1970年 • グローバルアラインメント（配列全体） • ２つのアミノ酸配列の類似性を明らかにするため • Smith-Waterman • 1981年 • ローカルアラインメント（スコア最大の部分配列）

(12)

(13)

手計算で行うNeedleman-Wunsch

• スコア行列に基づき初期テーブル（m+1

× n+1）作成

• 左上から右方向に、以下の３つ場合のスコ

アを計算し、スコアが最大になるものを新

テーブルに記入

• 記入の際に、最大になるスコアを与えたセルから矢印

• 右下から左上にトレースバックしてアライ

ンメント

(14)

初期テーブルの作成(N-W)

• スコア行列に基づき初期テーブル（m+1

× n+1）作成

•

左上は０

•

最上行と最左列にはギャップペナルティに基づ

く値をあらかじめ記入する

•

スコア行列は以下を用いることにする

一致：2、不一致：0、ギャップ：-2

(15)

初期テーブル

スコア行列＝一致：2、不一致：0、ギャップ：-2

-

A

T

C

A

G

A

G

T

C

-

0 -2

-4

-6

-8

-10 -12 -14 -16 -18

T

-2

0

2

0

2

0 T

-4

0

2

0

2

0 C

-6

0

2

0

2 A

-8

2

0

2

0

2

0

0 G

-10

0

2

0

2

0

0 T

-12

0

2

0

2

0 C

-14

0

2

0

2

(16)

スコアの計算(N-W)

• 左上から右方向に、以下の３つ場合のスコアを計算し、スコアが最大になるものを新テーブルに記入 • ギャップなし • 左上のセルと注目するセルの値の和 • 列方向(縦においた配列)にギャップ • 左のセルの値 − ギャップペナルティ • 行方向(横においた配列)にギャップ • 上のセルの値 − ギャップペナルティ • 記入の際に、最大になるスコアを与えたセルから矢印 • ギャップなしなら左上、列方向なら左、行方向なら上 • 一度計算した値を使うから「DP」

(17)

アライメント中

A

T

C

A

G

A

G

T

C

0 -2

-4

-6

-8

-10 -12 -14 -16 -18

T

-2

0

0 -2

-4

-6

-8

-10 -12 -14

T

-4

-2

2

0 -2

-4

-6

-8

-10

C

-6

-4

0

2

0

2 A

-8

2

0

2

0

2

0

0 G

-10

0

2

0

2

0

0 T

-12

0

2

0

2

0 C

-14

0

2

0

2

(18)

結果

-

A

T

C

A

G

A

G

T

C

-

0 -2

-4

-6

-8

-10 -12 -14 -16 -18

T

-2

0

0 -2

-4

-6

-8

-10 -12 -14

T

-4

-2

2

0 -2

-4

-6

-8

-10

C

-6

-4

0

4

2

0 -2

-4

-6

A

-8

-4

-2

2

6

4

2

0 -2

-4

G

-10

-6

-4

0

4

8

6

4

2

0 T

-12

-8

-4

-2

2

6

8

6

4 C

-14

-10

-6

-2

0

4

6

8

6

8

(19)

トレースバック

• 右下から矢印を左上に向かって逆にたどる • 経路がアラインメントになる

(20)

トレースバック

-

A

T

C

A

G

A

G

T

C

-

0 -2

-4

-6

-8

-10 -12 -14 -16 -18

T

-2

0

0 -2

-4

-6

-8

-10 -12 -14

T

-4

-2

2

0 -2

-4

-6

-8

-10

C

-6

-4

0

4

2

0 -2

-4

-6

A

-8

-4

-2

2

6

4

2

0 -2

-4

G

-10

-6

-4

0

4

8

6

4

2

0 T

-12

-8

-4

-2

2

6

8

6

4 C

-14

-10

-6

-2

0

4

6

8

6

8

(21)

アラインメント結果

• ATCAGAGTC score 8 • TTC--AGTC • ATCAGAGTC score 8 • TTCA--GTC • ATCAGAGTC score 8 • TTCAG--TC • スコアは最後のセルに入っている値に等しい

(22)

Needleman-Wunschその２

スコア行列 = 一致:2、不一致:-1、ギャップ: -2

G

A

T

C

G

A

T

A

(23)

初期テーブル

G

A

T

C

0 -2

-4

-6

-8

-10

-12

G

-2

2 -1

-1

A

-4

-1

2

2 -1

-1

T

-6

-1

2

2 -1

T

-8

-1

2

2 -1

A

-10

-1

2

2 -1

-1

(24)

結果

G

A

T

C

0 -2

-4

-6

-8

-10

-12

G

-2

2

0 -2

-4

-6

-8

A

-4

0

4

2

0 -2

-4

T

-6

-2

2

3

4

2

0 T

-8

-7

0

1

5

6

4 A

-10

-9

-2

2

3

4

5

(25)

トレースバック

G

A

T

C

0 -2

-4

-6

-8

-10

-12

G

-2

2

0 -2

-4

-6

-8

A

-4

0

4

2

0 -2

-4

T

-6

-2

2

3

4

2

0 T

-8

-7

0

1

5

6

4 A

-10

-9

-2

2

3

4

5

(26)

アラインメント結果

• GAATTC score 5

• G-ATTA 4x2 – 1 - 2

• GAATTC score 5

(27)

Smith-Watermann

• スコア行列に基づき初期テーブル（m+1 × n+1）作成 • 左上は０ • 最上行と最左列にはギャップペナルティに基づく値をあらかじめ記入可能 • 左上から右方向に、以下の３つ場合のスコアを計算し、スコアが最大になるものを新テーブルに記入 • ギャップなし • ２つのセルの値の和 • 列方向(縦においた配列)にギャップ • 左のセルの値ーギャップペナルティ • 行方向(横においた配列)にギャップ • _{上のセルの値ーギャップペナルティ} • 最大のスコアが負の数の場合「０」を記入 • 負の数になったら新たにアラインメントを開始 • 記入の際に、最大になるスコアを与えたセルから矢印 • 負になった時は矢印不要 • 最大からたどって「０」で終わるようトレースバックしてアラインメント

(28)

練習問題

スコア行列 = 一致:2、不一致:-1、ギャップ: -2

G

A

T

C

G

A

T

A

(29)

SW初期テーブル

G

A

T

C

0

0 G

0

2 -1

-1

A

0 -1

2

2 -1

-1

T

0 -1

-1

2

2 -1

T

0 -1

-1

2

2 -1

A

0 -1

2

2 -1

-1

(30)

SW結果

G

A

T

C

0

0 G

0

2

0

0 A

0

4

2

0

0 T

0

2

3

4

2

0 T

0

1

5

6

4 A

0

2

3

4

5

(31)

SWトレースバック

G

A

T

C

0

0 G

0

2

0

0 A

0

4

2

0

0 T

0

2

3

4

2

0 T

0

1

5

6

4 A

0

2

3

4

5

(32)

SWアラインメント結果

• GAATT score 6 • GA-TT • GAATT score 6 • G-ATT • ATT score 6 • ATT

(33)

FASTA

• ２つの配列のそれぞれの残基は比較しない！ • ①問い合わせ配列とデータベース配列をそれぞれ横軸と縦軸においたマトリックスを生成 • ②連続するk個の断片「k-tuple」の一致を探す • ハッシングにより高速探索 • 長さkのすべてのワードの位置を示す参照表を各配列に対して作成 • 相対位置を計算 • kはDNAでは4∼6、タンパク質では1∼2 • ③対角線方向に長く連なっている部分上位１０カ所を探しスコアを計算、最高スコアをINIT1 • ④ギャップありで領域をつないで③。より高いスコアINITNを得る。 • ⑤INITN付近でS-W。スコアがOPT。ギャップが大きいとINITNより小さくなる • ⑥OPTに対して、偏差値Zスコアと偶然一致の期待値Eを求める • Zは5以上で有意 • E<=0.02でおそらく相同、E>1なら偶然 • E値は偽陽性の数を示す

(34)

FASTAの例

•

ACNGTSCHQEと

GCHCLSAGQD

• 共通のoffsetは0, -3, -5 • ３つのアラインメント候補 • 32以内の一致領域を組み入れる（この例では短いので関係なし） • 共通の密度が高い場所 (offset 0)でスコアを計算、INIT1と置く。 S T

(35)

FASTAのプログラム

•

FASTA

• 問い合わせタンパク質 vs タンパク質データベース • 問い合わせDNA vs DNAデータベース •

TFASTA

• DNAを６通りの読み枠で翻訳し、問い合わせタンパク質 vs DNAデータベース •

FASTX/FASTY

• 問い合わせDNAを翻訳し、vs タンパク質データベース • XとYの違いは、Yのみコドン中の置換・フレームシフトを許可

(36)

BLAST

• ①問い合わせ配列を長さkの短い断片（ワード）に区切り（アミノ酸k=3、塩基配列k=11,12）、スコア行列（アミノ酸配列はBLOSUM62、塩基配列は5/-4など）を使って、このワードとしきい値以上のスコアでマッチするワード群を求めてリストを作成する。 • しきい値次第でリストの数は調整できる。アミノ酸の場合は最大でしきい値なしの場合の20の3乗(8000)となるが、50程度まで絞る。 • ②データベース配列に対して、作成したリストとギャップなしで一致するワードを探索する。 • ③一致したワードを両方向にのばし、HSP（high score segment pair）を求める • BLAST：スコア値が最大になるまで両方向にのばす • BLAST2：ギャップを考慮して両方向にのばす • ④一定のしきい値以上のスコアを持つHSPを選ぶ • ⑤有意なHSPを持つ配列をデータベースから選び、S-Wでアラインメント

(37)

BLASTのプログラム

•

BLASTP

• タンパク vs タンパク、ギャップあり •

BLASTN

• 核酸 vs 核酸、ギャップアリ •

BLASTX

• 核酸の翻訳 vs タンパク、ギャップあり •

TBLASTN

• タンパク vs 核酸の翻訳、ギャップアリ •

TBLASTX

• 核酸の翻訳 vs 核酸の翻訳、ギャップなし

(38)

FASTA, BLAST, S-W

• 速度 • BLAST > FASTA > S-W • 精度 • S-W > FASTA > BLAST • FASTA,BLASTはヒューリスティック • Heuristic:経験則に基づき、必要でないと思われる計算を省く方法。必要なものを省いてしまう場合もあるため、その解は正解とは限らない。 • 発見的方法とも。試行錯誤により答えを探す。 • 計算機の高速化によりSmith-Watermanの利用が拡大 • プログラムはFASTAのおまけSSEARCH • 類似度が低い場合でも検出可能 • 遠縁の遺伝子を探索できる • 「ベイズブロックアライナー」というのもある

(39)

アラインメントの有意性の確認法

• 二つの配列の一方を乱数で変更してもう一方とアラインメントし、スコアを計算 • Zスコア • （得られたスコア-平均スコア）／標準偏差 • ０ならランダムと変わらない • ５以上なら有意 • P値 • ランダムと変わりない確率 • Zスコアに比べてスコアの分布を考慮できる • P<=10-100で厳密に一致、10-100<P<=10-50は対立遺伝子やSNPなどでほとんど一致、10 -50_<P<=10-10_{は近縁の配列で相同であることが確実、10}-5_<P<=10-1_{は遠縁の可能性あり、P>10} -1_{は有意でない} • E値 • オリジナルと同じか、それ以上のZスコアを与える配列の個数 • P値×母集団のサイズ • E<=0.02でおそらく相同、0.02<E<=1で相同性がないとは言い切れない、E>1で一致は偶然 • 一致度(similarity) • 45%以上なら共通もしくは類似構造を持つかも • 25%以上なら全体的な構造が似ているかも • 18∼25%はトワイライトゾーン（Doolittle） • 18%以下だと何もわからない

(40)

一次構造からタンパク質の立体構造を予

測する

• 分子進化の経験的知識 • 同じファミリー・スーパーファミリーに属するタンパク質に有意なホモロジーがあれば立体構造もよく似ている • ホモロジー検索 • 立体構造データベースのアミノ酸配列に対して配列がよく似ているタンパク質を検索し、検索結果をもとに立体構造モデルを作成 • ホモロジーモデリング(homology modeling) • 【参考】Ab initio法 • 物理の法則のみを使って立体構造予測 • 「力場」パラメータが問題

(41)

ホモロジーモデリング

• データベースを検索して有意な類似性を示すタンパク質を得る • 各アミノ酸残基の対応をアラインメントにより確定する • 構造上よく保存されている領域(SCR: Structurally Conserved Region)と変化の大きいそうでない領域 (SVR: Structurally Variable Region)に分ける

• SCRについてデータベースから検索されたタンパク質の

構造をそのまま当てはめる。SVRについては構造ライブラリーなどから適当に決める

• 側鎖のコンフォメーションを確定する

(42)

ホモロジーモデリングの限界

• 配列の類似度が低い場合は予測不可能 • トワイライトゾーンの存在 • 配列の一致度が18∼25% • _{類似性があるともないとも言い切れない} • 配列の類似性がないのに似た構造を持つタンパク質の存在 • (case 1)進化的に非常に遠い関係 • _{(case 2)Convergent evolution}

(43)

3D-1D法の登場

• 「立体構造(3D)」と「配列(1D)」をアラインメント • (1) 立体構造ライブラリ(=配列データベース)を作成 • (2) アラインメント時の評価関数を作成 • (3) アラインメント • アミノ酸配列の類似度が低くても検出可能

(44)

起源①

• Bowie et al.,

Proteins

, 7, 257-264, 1990. • 構造と配列を「アラインメント」 • アラインメント：類似度比較のため配列どうしや構造どうしを並べること • ギャップを考慮 • アラインメント後にスコア(類似度)を計算 • 「構造」と「配列」といった異なるものをアラインメントする方法を提案

(45)

Bowie et al.(1990)の方法

1. アミノ酸配列を、疎水性を反映した文字列に変換 2. 構造を、タンパク質内部への埋もれ度を反映した文字列に変換 3. 文字列同士の「スコア表」を使って両者をアラインメント • アラインメントにはDPを利用 • スコア表は関数の形で表現

(46)

起源②

• Gribskov et al.,

PNAS

, 84, 4355-4358, 1987.

• Eisenberg Group (UCLA)

• プロファイル法(Profile Method)

• 配列同士のホモロジー検索にProfileを利用 • Profileは立体構造を元に定められたスコア表

(47)

3D-1D法の登場と発展

•

Bowie et al.,

Science

, 253, 164-170, 1991.

• スコア表に3D Profileを利用

• サイト周りの環境のみに依存する関数

•

経験的なエネルギー関数

• Sippl,

JMB

, 213, 859-883, 1990. • ペアワイズ形式

•

Jones et al.,

Nature

, 358, 86-89, 1992.

• Sipplの関数にDP法を適用

(48)

3D-1D法の基本

1. 既知の構造データベース(PDBなど)から構造と配列の適合性関数を作成 2. 3D-1Dアラインメントを行う • 欠損・置換の考慮が問題 • 構造を3D Profile(スコア表)に変換し、DPでアラインメント • PAM250, BIOSUMなどを使う場合と同じなので既存のホモロジー検索プログラムを利用できる

(49)

適合性関数の作成

• 立体構造中でアミノ酸が置かれている環境を１８のクラスに分類 • 主鎖３状態 • 側鎖６状態 • 各アミノ酸が各クラスに存在する頻度を調べマトリックス(3D-1Dスコア)を定義 • 3D-1Dスコアを元に3D Profileライブラリを作成

(50)

3D-1D法の問題

• すべての構造が既知でないと予測不可能 • 立体構造解析の進展により多くの構造が既知に • フォールドのパターンは数千 • Chothia, Nature, 357, 543-544, 1992. • 構造ライブラリの完成は間近？ • 1D-1D(ホモロジー検索)はスーパーファミリーまで、 3D-1Dはフォールドの類似性まで検出できる • 例外的なフォールドを無視してよいのか？ • フォールドはおおざっぱな構造にすぎず、これがわかっても機能はわからない • 局所立体構造の精密な予測 • 相互作用予測技術の開発→ドッキング

(51)

タンパク質の構造

• 一次構造(primary structure) • アミノ酸配列 • 二次構造(secondary structure) • αへリックス・βシート・ターン・ループ • 超二次構造(supersecondary structure) • 二次構造要素の組み合わせ • 三次構造(tertiary structure) • 立体構造 • 四次構造(quaternary structure) • 複数のポリペプチド鎖の立体配置

(52)

一次構造とデータベース

• 一次構造＝mRNA上のコドン配列を鋳型にしてリボソー

ム上で合成されたポリペプチド鎖に含まれるアミノ酸の並び

• データベースはUniProt(Universal Protein Resource)

• http://www.uniprot.org/

• Swiss-Prot(SBI), TrEMBL(EBI), PIR(Georgetown Univ.)が

(53)

UniProt(http://www.uniprot.org)

• 最新リリースは2010.11.2のRelease 2010_11 • UniProtKB/Swiss-Prot release 2010_11 • 522,019の配列 • _{Annotation(注釈)は手動、reviewされる} • UniProtKB/TrEMBLE release 2010_11 • 12,347,303の配列 • _{Annotationは自動、reviewなし} • オンライン検索＆ファイルダウンロード • 様々なデータベースとcross-reference • 遺伝子→EMBL • 立体構造→PDB • Wikipediaへのリンクがあるタンパク質も

(54)

立体構造のデータベース

• PDB(Protein Data Bank)

• X線結晶解析・NMRにより決定された原子の位置座標データ

• 「PDB形式」は様々なソフトウェアが対応

• Brookhaven National Laboratoryのデータベースから

RCSB(Research Collaboratory for Structural Bioinformatics)→wwPDB

• http://www.wwpdb.org/

• RCSB PDB, MSD-EBI, PDBj, BMRB

(55)

立体構造可視化ソフトウェア(無償)

• おすすめ（簡単・便利・きれい）

• Discovery Studio Visualizer(Windows)

• http://accelrys.com/products/discovery-studio/visualization.html

• Molegro Molecular Viewer(Windows, Mac OS X, Linux)

• http://www.molegro.com/ • ↑はPDBから直接ダウンロードする機能あり • おすすめしない • Open RasMol ‒ きれいでない • PyMol ‒ めんどうくさい • iMol ‒ 古い • Raster3D/Molscript ‒ とってもめんどうくさい