応用生命科学・情報生命学
授業目的
本日（３時限目）の内容
情報科学と生命科学の融合領域である生命情報学（バイ
バイオインフォマティクス概観
オインフォマティクス）の基本的なトピックを解説する
日程
３時限目
４時限目
７月2日（木）
配列解析入門
（加藤）
RNA配列情報解析
（加藤）
７月１6日（木）
ゲノム配列決定とトランスクリ
プトーム（大島）
新型シーケンサーを利用した
転写制御機構の解析（大島）
７月２日（木）３時限目
７月23日（木）
システムバイオロジー基礎I
（佐藤）
システムバイオロジー基礎II
（佐藤）
加藤 有己
７月30日（木）
京都大学 iPS細胞研究所
講義資料
全ゲノム解析概説
（小野）
代謝シミュレーション概説
（小野）
成績評価
第１回: 配列解析入門
ペアワイズアラインメント
ホモロジー検索
レポートおよび講義中に適宜行う小テストにより評価する
http://tcs.cira.kyoto‐u.ac.jp/~ykato/lecture/bioinfo15‐1/
2
3
バイオインフォマティクス（生命情報学）
Bioinformatician の仕事
Crickの分子生物学のセントラルドグマ
生物学と情報学の学際領域の学問分野
データベース構築
遺伝情報伝達の基本原理
Exon Intron Exon
実験解析により得られた大量のデータを整備
目的
アルゴリズム開発
生物データに対する情報解析技術の開発
生物学の実験技術の革新→
mRNA
析するアルゴリズムを開発
Translation
データ解析
大量のデータ
Protein
既存のソフトウェアを使ってデータを網羅的に解析し、
Fold
生物学的知識を発見
巨大な問題（情報）を上手に処理するための情報学
Exon
Transcription
数理的・情報科学的手法を駆使して、生物データを解
情報解析技術を利用した新たな生物学的知識の発見
Intron
DNA
の役割は極めて重要
Function
4
現代の分子生物学のセントラルドグマ
生物配列（biological sequence）
遺伝情報伝達の基本原理
DNA配列
ゲノム
分子生物学データベース
４種類の塩基A, C, G, Tからなる文字列
DNA塩基配列
例: ACTAGCATGAACGCATCATTAGATCTACACATGTA
エピゲノム
トランスクリプトーム
DNAのメチル化、ヒストンの修飾
クロマチン構造
RNA配列
mRNA, non‐coding RNA
6
5
種類
名称
URL
核酸配列
NCBI
http://www.ncbi.nlm.nih.gov/
核酸配列
ENA
http://www.ebi.ac.uk/ena
核酸配列
DDBJ
http://www.ddbj.nig.ac.jp/
http://www.ncbi.nlm.nih.gov/sra/
配列リード
SRA
４種類の塩基A, C, G, Uからなる文字列
RNAファミリー
Rfam
http://rfam.sanger.ac.uk/
例: GACUCGCUUGACUGUUCACCUCCCCGUGGUGCGAG
代謝ネットワーク
KEGG
http://www.genome.jp/kegg/
アミノ酸配列（タンパク質配列）
プロテオーム
２０種類のアミノ酸A, C, D, E, F, G, H, I, K, L, M, N, P, Q, R, タンパク質
S, T, V, W, Yからなる文字列
メタボローム、フェノーム
例: TPDCVTGKVEYTKYNDDDTFTVKVGDKELFTNRWN
代謝物、表現型
（注）各文字はそれぞれ化学構造を持つ
7
8
9
配列解析の諸問題
分子生物学の問題
情報科学の手法
類似性検索
最適化法
動的計画法
整数計画法
ペアワイズアラインメント
ホモロジー検索
マルチプルアラインメント
進化系統樹解析
リードマッピング
構造・機能予測
配列アラインメント
バイオインフォマティクス概観
配列が似ていれば機能も似ている
ペアワイズアラインメント
配列アラインメント
ホモロジー検索
与えられた複数の配列において文字間の対応付
文字列解析
RNA２次構造予測
タンパク質立体構造予測
配列モチーフ抽出
機能部位予測
細胞内局在部位予測
遺伝子領域予測
膜貫通領域予測
分類
本日（３時限目）の内容
けをとること（またはその計算結果）
並べて比較する
アラインメント
GCGTCGT
GCG-TCGTCGATCCTC
-CGATCCTC
パターン認識・機械学習
判別分析
ニューラルネットワーク
隠れマルコフモデル
サポートベクトルマシン
細胞分類
フォールド分類
２本の配列→ペアワイズアラインメント
クラスタリング
３本以上の配列→マルチプルアラインメント
10
11
12
表記法
ペアワイズアラインメント
最適アラインメント
∑: アルファベット（文字の有限集合）
DNAの場合: ∑ = {A, C, G, T}
タンパク質の場合: ∑ = {A, C, D, E, F, G, H, I, K,
L, M, N, P, Q, R, S, T, V, W, Y}
配列 s, r ∑* に対するグローバルアラインメント
アラインメントをスコアで定量化
各配列にギャップ記号”-”を挿入して同じ長さにそ
スコア関数
ろえた配列の組 (s’, r’)
s = s1s2…sn ∑*: 文字列（配列）
w(x, y) = w(y, x) for all x, y ∑
入力
アラインメント
w(x, -) = w(-, y) = -d (d > 0) for all x, y ∑
s: A A C G T
r: A C T C T A
s’: A A C - G T r’: - A C T C T A
w は同じ文字/物理化学的な性質が類似/進化的な距
（ギャップ１文字に対するペナルティ）
|s|: s の長さ（文字の個数）
離が近い文字に対して、大きな値を与える
アラインメントのスコア = アラインメントを構成する各
文字同士の対応関係の明確化
s[i..j] = sisi+1…sj (i < j): 部分文字列
列のスコア w(x, y) の和
最適アラインメント = 可能なアラインメントの中でスコ
ア最大のもの
（注）ギャップ記号は同じ位置に並ばない
-: ギャップ記号
13
14
15
アラインメントスコアの例
定義（ペアワイズアラインメント問題）
単純な列挙法によるアプローチ
スコア関数
入力
仮定: |s| = |r| = n
２本の配列 s, r
∑*
アラインメントにおいて各配列の文字をギャップを無視し
先頭から１個ずつ交互に取り出して得られる列（挿入列）
は、元のアラインメントと１対１対応
スコア関数 w(x, y)
出力
アラインメント
s’
r’
A
-
A
A
C
C
T
G
C
T
T
例
以下のアラインメントスコア S が最大となるアライン
A
メント (s’, r’):
s’1 s’2 s’3 r’1 - r’2 r’3
s’1 r’1 s’2 s’3 r’2 r’3 （長さ2n）
挿入列の総数（= 可能なアラインメントの総数）
アラインメントスコア
指数個
S(s’, r’) = w(A, -) + w(A, A) + w(C, C) + w(-, T)
+ w(G, C) + w(T, T) + w(-, A)
=-1+1+1-1-1+1-1=-1
入力、出力が何であるかを
常に意識すること
16
単純な列挙法では
指数時間かかる！
Stirlingの公式
17
18
動的計画法（DP）による最適アラインメント
DPの表とアラインメントグラフ
DPの表とアラインメントグラフ（続き）
s = s1s2…sn, r = r1r2…rm: 入力配列
DP (dynamic programming) table
Alignment graph
Needleman–Wunschのアルゴリズム (1970)
j
A
F(i, j): s[1..i] と r[1..j] に対する最適アラインメントスコア
T
C
j
G
T
(0, 5)
(0, 0)
初期化
A
(0, 0)
A
A
C
反復（漸化式）
DPは部分問題の
解からより大きな
問題の解を効率よ
く計算する手法
C
-1
1 -1 -1
G
-1
-1 -1
-1
T
-1
-1 -1
-1
-1
-1 -1
-1
(0, 5)
-1
i G
T
-1
(4, 0)
が基本単位
となるように
矢印と重みを
書き込む
ここでは
一致⇔1
不一致⇔-1
ギャップ⇔-1
(4, 5)
20
19
21
DPの表とアラインメントグラフ（続き）
DPの表とアラインメントグラフ（続き）
DPの表とアラインメントグラフ（続き）
初期化
反復（漸化式）
最終結果
j
A
T
C
j
G
T
A
-1 -1 -1 -2 -1 -3 -1 -4 -1 -5 (0, 5)
(0, 0) 0
A -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1
-1
-1
-1
-1
-1
-1
C -1
-2
i G
i G
T -1
(4, 0) -4
T
C
j
G
A
T
-1
-3
T -1
(4, 0) -4
(4, 5)
T
C
-1 -1 -1 -2 -1
(0, 0) 0
A -1 1 -1 -1 -1 -1
1
0
-1
-1
-1
-1
C -1
0
0
-2
-1 -1 -1 -2 -1 -3 -1 -4 -1 -5 (0, 5)
(0, 0) 0
A -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1
1
-1
-1
-1
-1
-1
-1
C -1
-2
-1
-3
-d
-d
-1
T
(4, 5)
w(si, rj)
-1
-1
i G
(4, 0)
-1
-1
F(i, j) の値に
対応
C
-1
T
(4, 5)
22
T
頂点(0, 0)から
頂点(n, m)への
最大重みパス
-1 -1 -1 -1 -1
-1
-2
-3
-1
-1
1
0
-1
-1
0
2
1
0
-1
1
3 (4, 5)
最適アラインメント
-1
-3
-1
T -1
(4, 0) -4
-2
i G
G
-3 -1 -4 -1 -5 (0, 5)
A - C G T
A T C G T
24
23
トレースバック
Needleman–Wunschのアルゴリズムの計算量
アフィンギャップスコア
最終結果 F(n, m) の値は最適アラインメントのスコア
漸化式において、添え字の動く範囲を考える
ギャップはバラバラよりも固まって出現する傾向が大
きい
最適スコアを実現する
アラインメントそのものは？ (0, 0) A
0
→F(n, m) から逆にたどり
ながらアラインメントを後 A
-1
ろから前へと計算
（トレースバック）
漸化式の計算過程で
最大値を与える頂点
（位置）を記憶すれば
よい
-1
T
-2
C
-3
G
-4
T
-5
1
0
-1
-2
-3
0
0
1
0
-1
C
-2
G
T
1≤i≤n
1≤j≤m
線形ギャップスコア vs. アフィンギャップスコア
ギャップ開始
時間計算量（どれだけの計算時間が必要か？）
A
A
O(nm)
n ≈ mのとき、O(n2)
-3
-1
-1
0
2
1
-4
-2
0
-1
1
3
(n, m)
25
C
C
G
ギャップ伸長
T
C
C
A
A
-d -d -d -d
-d -e -e -e
ただし、d > e > 0
アフィンギャップスコアはより現実に即したスコア
線形ギャップスコア
アフィンギャップスコア
領域計算量（どれだけのメモリが必要か？）
O(nm)
n ≈ mのとき、O(n2)
26
27
線形ギャップとアフィンギャップの比較
アフィンギャップスコアを用いたアラインメント
アルゴリズム
一般的なギャップスコアを用いたアラインメント
アルゴリズム
ギャップスコア関数をグラフ化すると理解しやすい
３種類のテーブル M, Ix, Iy を用いた動的計画法
γ(k) < 0: 長さ k (> 0) のギャップに対するスコア関数
いずれも s[1..i] と r[1..j] のアラインメントスコアを表す
DPの漸化式
線形ギャップスコア: γ(k) = -dk (d > 0)
アフィンギャップスコア: γ(k) = -d-e(k-1) (d > e > 0)
0
1
si とrj がマッチ
k
-d
si とギャップがマッチ
rj とギャップがマッチ
時間計算量: O(nm(n+m))
n ≈ mのとき、O(n3)
領域計算量: O(nm)
時間計算量、領域計算量はともに O(nm)
28
29
30
グローバル vs. ローカル
ローカルアラインメントの単純な計算法
ローカルアラインメントアルゴリズム
全体でのアラインメント
各配列の全ての部分文字列の組に対してグロ
Smith–Wartermanのアルゴリズム (1981)
ーバルアラインメントを計算
DPの漸化式
その中で最も高いスコアとなるアラインメントを
出力
長い配列の比較では必ずしも全体としては類似していない
s
連続した部分領域間のアラインメント
r
（ローカルアラインメント）
最適スコアは F(i, j) の中での最大値
O(nm) O(n2) O(m2) = O(n3m3) 時間！
sの部分列
グローバル
アラインメント の個数
DPテーブル
A A T G C A T
G
A
T
C
G
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
1
1
0
0
0
1
0
0
0
0
2
1
0
0
2
0
0
0
1
1
2
1
0
0
0
0
0
2
1
1
0
時間計算量、領域計算量はともに O(nm)
32
31
ローカルアラインメントの例
トレースバックは最大値から始めて0になる時点で終了
rの部分列
の個数
33
スコア行列 w(x, y)
スコア行列の導出
DNA塩基→一致・不一致スコア
オッズ比（アラインメント (s, r) がランダムな場合と比較
してどの程度出現しやすいかを表す）:
タンパク質アミノ酸→類似度を反映したスコア
多数のアラインメントからスコアを算出
ローカル
アラインメント
A T - C
A T G C
スコア関数
34
M: ある確率分布に従ってギャップなしアラインメントを
対数オッズ比
生成するモデル
pab: アミノ酸 (a, b) が同じ列に出現する確率
各列は独立に生成される
R: ２本の配列をランダムに生成するモデル
qa: アミノ酸 a が出現する確率
s, r ∑* (|s| = |r| = n)
スコア関数
対数オッズ比 = アラインメントスコア
pab, qa は実際のアラインメントから出現頻度を計算
（にわとりと卵）
応用例: PAM行列 [Dayhoff et al. 1978],
BLOSUM行列 [Henikoff & Henikoff 1992]
35
36
本日（３時限目）の内容
ホモロジー検索
バイオインフォマティクス概観
データベースに対する類似配列の検索
BLAST: Basic Local Alignment Search Tool
両配列のドットマトリックス上で完全一致（または非常
類似配列
ペアワイズアラインメント
配列データベース
に類似したギャップなしの）領域（シード）で、同じ対角
線上にある近接ペアを検出
局所的に類似する配列検索
A C A T G A C
問い合わせ配列
ホモロジー検索
Target
データベース中の配列と数百万回のアラインメント
→O(nm) 時間アルゴリズムでは時間がかかりすぎる！
最適性を犠牲にして高速に類似配列を検索（ヒューリ
スティクス）
FASTA [Lipman & Pearson 1985]
BLAST [Altschul et al. 1990]
37
Query
G
A
T
G
A
T
38
BLASTにおけるシード２段階伸長法
BLASTサーバーを使ってみよう
第１段階: シードのペアを対角線方向に沿ってギャッ
http://blast.ncbi.nlm.nih.gov/ [Altschul et al. 1997]
プを含めず前後に伸長
塩基配列なら nucleotide blast を選択
統計的に有意なアラインメントのみを考慮
アミノ酸配列なら protein blast を選択
39
BLASTサーバーの出力例
→HSP (High‐scoring Segment Pair)
第２段階: HSPを連結させてDPによるギャップありロー
カルアラインメント、統計的有意度を計算
Target
Query
シードだけに着目
してHSPを構成す
るため、探索空間
の大幅な削減が
可能
40
41
42
まとめ
参考文献
レポート課題
配列アラインメントはバイオインフォマティクスで古くか
阿久津達也、バイオインフォマティクスの数理とアルゴリ
配列解析について、情報科学技術の有用性をまと
ら使われ、今なお有用である手法
グローバルアラインメント
ローカルアラインメント
動的計画法（DP）は配列解析を支える根幹技術の１つ
大量の配列検索のためのヒューリスティクス
ズム、共立出版、2007年
吉川寛、伊藤隆司、上野直人、佐々木裕之、中井謙太、
ゲノム科学の基礎、岩波書店、2009年
金久實、ポストゲノム情報への招待、共立出版、2001年
Durbin, R., Eddy, S., Krogh, A. and Mitchison, G., Biological Sequence Analysis, Cambridge University Press, 1998
日本バイオインフォマティクス学会、バイオインフォマティ
クス事典、共立出版、2006年
43
44
め、今後の動向を自由に発想し、A4用紙１枚以内
で論じなさい
本日配布したレポート用紙を使うこと
提出期限
2015年7月9日（木）午後５時まで
提出先
バイオ事務室（入り口のボックス）
講義資料
http://tcs.cira.kyoto‐u.ac.jp/~ykato/lecture/bioinfo15‐1/
45
© Copyright 2024 ExpyDoc
