�

2016年度「バイオインフォマティクス」
講義予定表
1. 配列アライメント（五斗）
2. データベースサーチ（五斗）
3. 機能・構造予測（五斗）
4. 配列モチーフ・隠れマルコフモデル（五斗）
5. アセンブリとマッピング（Blanc-Mathieu）
6. 分子進化（緒方）7. 分子系統解析（緒方）8. 分子系統解析【演習】（Blanc-Mathieu）
9. 遺伝子予測（緒方）
10. 機能アノテーション・比較ゲノム（緒方）11. システムズバイオロジー（五斗）
12. メタゲノム解析（緒方）13. メタゲノム解析（緒方）http://goto.kuicr.kyoto-u.ac.jp/lecture/bioinfo.html

1

配列アライメント ‒ 今日のトピック" スコアマトリックス（アミノ酸置換行列）・ギャップペナルティ（Score Matrix, GapPenalty）" ホモロジーサーチ１" ハッシュテーブルを用いた高速検索（FASTA）" ホモロジーサーチ２" オートマトンを用いた高速検索（BLAST）

2アミノ酸の構造と類似度• 疎水性、親水性• 電荷の有無• 残基のサイズ• コドン使用パターン• 進化的に変異を許容する置換と、そうでない置換がある。
• アライメントでは置換の頻度を考慮する必要がある。
3アミノ酸置換行列
Ala 1!
Arg -5 7!
BLOSUM50
Asn -5 -1 7!
BLOck SUbstitution Matrices
Asp -5 -2 2 8!
Cys -5 -4 -2 -4 13!
参考：AAindexデータベース
Gln -5 1 0 0 -3 7!
http://www.genome.jp/dbget/aaindex.html
Glu -5 0 0 2 -3 2 6!
Gly -5 -3 0 -1 -3 -2 -3 8!
His -5 0 1 -1 -3 1 0 -2 10!
Ile -5 -4 -3 -4 -2 -3 -4 -4 -4 5!
Leu -5 -3 -4 -4 -2 -2 -3 -4 -3 2 5!
Lys -5 3 0 -1 -3 2 1 -2 0 -3 -3 6!
Met -5 -2 -2 -4 -2 0 -2 -3 -1 2 3 -2 7!
Phe -5 -3 -4 -5 -2 -4 -3 -4 -1 0 1 -4 0 8!
Pro -5 -3 -2 -1 -4 -1 -1 -2 -2 -3 -4 -1 -3 -4 10!
Ser -5 -1 1 0 -1 0 -1 0 -1 -3 -3 0 -2 -3 -1 5!
Thr -5 -1 0 -1 -1 -1 -1 -2 -2 -1 -1 -1 -1 -2 -1 2 5!
Trp -5 -3 -4 -5 -5 -1 -3 -3 -3 -3 -2 -3 -1 1 -4 -4 -3 15!
Tyr -5 -1 -2 -3 -3 -1 -2 -3 2 -1 -1 -2 0 4 -3 -2 -2 2 8!
Val -5 -3 -3 -4 -1 -3 -3 -4 -4 4 1 -3 1 -1 -3 -2 0 -3 -1 5!
A R N D C Q E G H I L K M F P S T W Y V!
4

PAM (Accepted Point Mutations)" デイホフらによる定式化（1978年）
71 グループの配列：類似度が 85% 以上
n 1,572 の置換をカウント
n 各アミノ酸置換の確率を1,572 の置換の割合で求める
n 対数尤度（Log odds） 比で表現
w log10(qij/pipj) に比例したスコア
w pi はその文字の出現率、qijは同時出現率n PAM 1n PAM 250 は PAM 1 を250 回掛け合わせたもの
nw 20 % の類似度に相当する
5

BLOSUM (BLOck SUbstitution Matrices)" ヘニコフらによる定式化（1992年）
ギャップなしのローカルアライメントのデータベース（ブロック）から計算
n すべての置換頻度と非置換頻度（すべてのアミノ酸ペア 20x19/2 = 210 パターン）をカウント
n 対数尤度（Log odds） 比を使うのはPAMと同じ
w log (qij/pipj) に比例したスコア
w pi はその文字の出現率、qijは同時出現率
n 70% 一致、60% 一致など配列一致度ごとに作成したブロックを用いてそれぞれの置換行列を計算
n26

演習問題 2-1

7

ギャップペナルティの種類
Di-1,j-1

Di,j-1" 線形スコア
長さ g のギャップペナルティn γ(g) = -gdn

" Aﬃne スコア

ws(i),t(j)Di-1,jdd

Di,j長さ g のギャップペナルティn γ(g) = -d - (g - 1)eDi,j = max (n d : gap open penalty
Di-1,j-1 + ws(i),t(j),n e : gap extension penalty
Di-1,j + d,n 通常は d > e
Di,j-1 + d)n8

アフィンスコアを使った DP

Di-1,j-1

Di,j-1３種類の Di,j を用意する

e

Di-1,j(2)�
Di,jws(i),t(j)e(3)�
Di,j(1)�
Di,j9配列アライメント ‒ 今日のトピック" スコアマトリックス（アミノ酸置換行列）・
ギャップペナルティ（Score Matrix, GapPenalty）" ホモロジーサーチ１" ハッシュテーブルを用いた高速検索（FASTA）" ホモロジーサーチ２" オートマトンを用いた高速検索（BLAST）

10

データベースサーチ：ホモロジー検索" ホモロジー (Homology)：相同性n

共通の祖先に由来する相同関係
w 同一の機能や構造を持つ関係
w ホモログ（Homolog）は相同関係にある遺伝子のこと

n

一般には配列の類似関係として使われる言葉" ホモロジー検索
問合せ配列に類似した配列をデータベースから検索すること
n 問合せ配列をデータベース中の配列１本づつとペアワイズアライメントする
n11

ホモロジー検索の高速化" 並列処理による高速化
nDP法を使用する際に工夫w アルゴリズムの並列化
w データベースの分割" アルゴリズムの高速化
n

最適解は得られない可能性があるが、実用上は問題ない程度の結果が得られる別のアルゴリズムを使う
w FASTAアルゴリズム
w BLASTアルゴリズム

12

FASTA アルゴリズム" ハッシュを用いて問合せ配列と一致する領域を大雑把に探し出す

ハッシュ：問合せ配列を部分配列として切り出してきたとき、それぞれがどこに出現しているかを保存しておくテーブル
n ドットマトリックス法で対角線成分を抽出することに対応n" 抽出された対角線領域の近傍のみでDP法を適用する

13

ハッシュ問合せ配列 ATATGCCTT
インデックス� 123456789
１文字のハッシュ

２文字のハッシュ

A 1,3!
T 2,4,8,9!
G 5!
C 6,7!

AA!
GA!
AT 1,3! GT!
AG!
GG !
AC!
GC 5!
TA 2! CA!
TT 8! CT 7!
TG 4! CG!
TC !
CC 6!

４パターン

１６パターン（アミノ酸の場合は）２０パターン
４００パターン

３文字のハッシュ

６４パターンk 文字

k４ パターン
k８０００パターン ２０ パターン14

ドットマトリックスの作成
２文字のハッシュ
問合せ配列

T2A
3

T
4

G
5●!

●!

C6●!

C7T
8T!
9!

● !

�AA!
GA!
A
AT 1,3! GT!
1AG!
GG !
AC!
GC 5! A !
デ A !
TA 2! CA! ー
TT 8! CT 7! タ G
CTG 4! CG! ベーTC !
CC 6! ス C
配 T
列 G!
T!

データベース配列をハッシュと比較して、対応するインデックスの場所にドットを打つと、同じ文字が並ぶ場所に対角線ができる。
15

対角線の近傍でDP

問合せ配列

データベース
配列

16

演習問題 2-2

17

DPを用いたホモロジー検索" 最適アライメントがとれる配列を検索するにはダイナミックプログラミング（DP）法がベストn

SSEARCHプログラム" DP法を単純に使用すると検索効率が悪い
nDP法によるペアワイズアライメントはO(n2)w n：一つの遺伝子の配列長n問合せ配列が103 塩基、塩基配列データベースに同じぐらいの長さの配列が 108 個程度登録されているとすると、1014の演算が必要になる
18

DPの計算量
９文字8
文
字

A T A T G C C T T!
0 -1 -2 -3 -4 -5 -6 -7 -8 -9!
A -1 1 0 -1 -2 -3 -4 -5 -6 -7 !
A -2 0 1 1 0 -1 -2 -3 -4 -5!
G -3 -1 0 1 1 1 0 -1 -2 -3!
C -4 -2 -1 0 1 1 2 1 0 -1!
C -5 -3 -2 -1 0 1 2 3 2 1 !
T -6 -4 -2 -2 0 0 1 2 4 3!
G -7 -5 -4 -2 -1 1 0 1 3 4 !
T -8 -6 -4 -3 -1 0 1 0 2 4 !

演算の回数：9 + 8 + 9 x 8
配列の長さを、それぞれ m と n とすると m + n + m x nm n とすると 2n + n2 → O(n2)：n2 のオーダー�
19

データベースのサイズ
エントリーの数

塩基配列データベース
GenBank, EMBL
アミノ酸配列SWISS-PROT, PIR, PRF
遺伝子
KEGG GENES
立体構造
PDB

塩基配列の増加は約５年で１０倍のペース！
NGS データの増加によりその速度は更に増している！
20

配列アライメント ‒ 今日のトピック" スコアマトリックス（アミノ酸置換行列）・
ギャップペナルティ（Score Matrix, GapPenalty）" ホモロジーサーチ１" ハッシュテーブルを用いた高速検索（FASTA）" ホモロジーサーチ２" オートマトンを用いた高速検索（BLAST）

21

BLASTアルゴリズム" Basic Local Alignment Search Tool
" 二つの配列中の共通の文字パターンを探し、そこをコアにしてアライメントを両側に伸長" 手順n

問合せ配列からの類似単語の作成

n

有限オートマトンを用いた複数パターン検索n

共通パターンからギャップを入れずに両側に伸長→ HSP (High-scoring Segment Pair)" 統計的評価を用いた有意な HSP の選択" BLAST2 ではギャップも考慮するようになった (Two-hit method)

22

HSP (High-scoring Segment Pair)
問合せ配列…EKAAFDMFDADGGGDISVKEL …

MFD,FME,MFN,!
MYD,MYE,MYN,!
LFD, …!

類似ワードのリスト

ワード検索

問合せ配列
ＤＢ配列

… EKAAFDMFDADGGGDISVKEL …
… FKEAFSLFDKDGDGTITTKEL …

前後に伸ばしながら比較し、ギャップなしで高いスコアを与える断片対（HSP）を抽出
23

類似単語の検索にはオートマトンを使う
終止コドン（TAA, TAG, TGA）を探すオートマトン�
A,C,G
C
A,C,GT
0TA
TA

1C

2G5GTC,G43A
6T

24

演習問題 2-325ホモロジー検索結果の統計的有意性" Z-score: Z = S - μσ
S : 二つの配列のアライメントによるホモロジースコア
μ : それぞれの配列をランダムに並べ替えて n 回アライメントを行った場合のスコアの平均値
データベース検索の場合：a + b ln nσ : 標準偏差" E-value: E = Knmexp(-λS)
極値分布に従ったデータベース配列に対するスコア分布からどの程度有意かを判断する基準
n n, m: アライメントした配列の長さ。
n 極値分布：exp(-x-exp(-x))
n26

Low complexity region のフィルタリング" SEG / DUST
ヒットしても統計的に有意と認められない領域を予めフィルタリングしておき検索対象から除いておく。
n DUST: blastn プログラム
n SEG: blastn 以外の blast プログラムn27

ホモロジー検索用ウェブサイト

" SSEARCH
http://www.ebi.ac.uk/Tools/sss/fasta/n http://www.kegg.jp/kegg/ssdb/
n" FASTAn

http://www.genome.jp/tools/fasta/" BLASTn

http://www.genome.jp/tools/blast/28

BLAST を使ってみよう④ Compute ボタンをクリック�
① FASTA 形式の配列を入力する�

② プログラムとデータベースを選択する
KEGG GENES: ゲノムが決定された生物種のゲノム
KEGG MGENES: メタゲノム
nr-aa: 複数のデータベースをマージして重複を除去したもの�

http://www.genome.jp/tools/blast/③ ページの下の方でスコアマトリックスなどの選択ができる�
29

FASTA 形式の配列> で始まる１行目はコメント
２行目以降がアミノ酸（塩基）配列で途中に改行を入れても良い�

http://www.genome.jp/dbget-bin/www̲bget?-f+-n+a+eco:b3919

30

質問配列とデータベースの関係

データベース

質問配列塩基配列アミノ酸配列

塩基

BLASTN

BLASTX

アミノ酸

TBLASTNBLASTP

31

BLAST の検索結果ヒットした遺伝子（タンパク質）がスコア（bit スコアと E-value）の高い順にリストされる。
Show alignment をクリックするとアライメントに飛ぶ�32

FASTA で UniProt データベースを検索した場合

33

FASTA のスコア分布図

34

参考文献
"SSEARCHn"

FASTAnn"

Smith, T. F. and Waterman, M. S.: Identiﬁcation of common
molecular subsequences. J. Mol. Biol., 147:195-197 (1981).

Wilbur, W. J. and Lipman, D. J.: Rapid similarity searches of nucleic
acid and protein data banks. Proc. Natl. Acad. Sci. USA,30:726-730 (1983).
Lipman, D. J. and Pearson, W. R.: Rapid and sensitive protein
similarity searches. Science, 227:1435-1441 (1985).

BLAST
nn

Altschul, S. F., Gish, W., Miller, W., Myers, E. W. and Lipman, D. J.:
Basic local alignment search tool. J. Mol. Biol., 215:403-410 (1990).
Altschul, S. F., Madden, T. L., Schaeﬀer, A. A., Zhang, J., Zhang, Z.,
Miller, W. and Lipman, D. J.: Gapped BLAST and PSI-BLAST: a newgeneration of protein database search programs. Nucleic AcidsRes., 25:3389-3402 (1997)
35

より高速な検索" RAPSearch / GhostXSuﬃx Array を用いてデータベースをインデクシングし、シードの高速検索を実現
n データベース中の類似配列をマージする GhostZも開発されている
n"RAPSearchn"Zhao, Y., Tang, H. and Ye, Y.: RAPSearch2: a fast and memoryeﬃcient protein similarity search tool for next-generation
sequencing data. Bioinformatics, 28:125-126 (2011).

GhostX / GhostZ
nnSuzuki, S., Kakuta, M., Ishida, T. and Akiyama, Y.: GHOSTX: An
improved sequence homology search algorithm using a query suﬃx
array and a database suﬃx array. PLoS ONE, 9:e103833 (2014).
Suzuki, S., Kakuta, M., Ishida, T. and Akiyama, Y.: Faster sequencehomology searches by clustering subseqeunces. Bioinformatics,
31:1183-1190 (2015).
36