ゲノム統合データベースからの知識発見

分子生物情報学(2)
配列のマルチプルアライメント法
阿久津達也
京都大学化学研究所
バイオインフォマティクスセンター
内容






ペアワイズアライメントの復習
マルチプルアライメント
多次元DP
プログレッシブアライメント
モチーフ発見
局所マルチプルアライメント
マルチプルアライメント：意味




３本以上の配列が与えられた時、全ての配列の長さが
同じになるようにギャップを挿入
進化的、構造的に相同な残基（塩基）ができるだけ同じ
カラムに並ぶようにする
通常はスコアを用いて、最適化問題として定式化
理想的なアライメント
同一残基から派生した残基が同一カラムに並ぶ
 構造的に重なり合う残基が同一カラムに並ぶ
⇒構造的に重なり合わない場所を無理に重ね合わせるのは、あ
まり意味がない

マルチプルアライメント：定式化

３本以上の配列が与えられた時、長さが同じで、かつ、スコアが最適とな
るように各配列にギャップを挿入したもの
HBA_HUMAN
HBB_HUMAN
MYG_PHYCA
GLB5_PETMA
LGB2_LUPLU
GLB1_GLYDI

VGAHAGEY
VNVDEV
VEADVAGH
VYSTYETA
FNANIPKH
IAGADNGAGV
HBA_HUMAN
HBB_HUMAN
MYG_PHYCA
GLB5_PETMA
LGB2_LUPLU
GLB1_GLYDI
V
V
V
V
F
I
G
E
Y
N
A
A
A
S
A
G
A
D
H
N
D
T
N
N
A
V
V
Y
I
G
G
D
A
E
P
A
E
E
G
T
K
G
スコアづけ（全体スコアは基本的に各列のスコアの和:∑S(mi)）
 最小エントロピースコア


S(mi) = -∑cia log pia
SPスコア(Sum-of-Pairs)

S(mi)=∑k＜ｌ s(mik,mil)
（cia= i列におけるaの出現回数,
pia = i列におけるaの生起確率）
（mik = i列, k行目の文字）
Y
V
H
A
H
V
SP(Sum of Pairs)スコア

S(mi)=∑k＜ｌ s(mik,mil)
k
 mi

= i列, k行目の文字
問題点


S (m1 )  s(L, I)  s(L, V)  s(I, V)
S (m2 )  s(D,)  s(D,)  s(,)
S (m3 )  s(D,)  s(D, E)  s(, E)
確率的な正当性が無い
同一カラムに a,b,c が並んだ
場合、log(pabc/qaqbqc) とすべ
きだが、SPスコアでは
log(pab/qaqb)+ log(pbc/qbqc)+
log(pac/qaqc)
L D D
I
V
E
m 1 m2 m 3
多次元DPによる
マルチプルアライメント

N個の配列に対するマルチ
プルアライメント


N次元DPによりO(2NnN)時間
（各配列の長さはO(n)を仮定）
(i,j,k-1)
例：N=3
 F (i  1, j  1, k  1)  S ( 1 , 2 , 3 )
xi x j x k

 F (i, j  1, k  1)  S (, 2 , 3 )
x j xk

 F (i  1, j , k  1)  S ( 1 ,, 3 )
xi x k

1
2

F (i, j , k )  max  F (i  1, j  1, k )  S ( xi , x j ,)

3
 F (i, j , k  1)  S (,, xk )

2
 F (i, j  1, k )  S (, x j ,)

 F (i  1, j , k )  S ( x1i ,,)

(i,j-1,k)
(i-1,j,k) (i,j,k)
マルチプルアライメントの計算手法

分枝限定法






１０配列程度なら最適解が計算可能
シミュレーテッドアニーリング
遺伝的アルゴリズム
逐次改善法
HMMによるアライメント
プログレッシブアライメント


CLUSTAL-W（最も広く利用されているソフト）で採用
逐次改善法との組み合わせが、より有効
実用的マルチプルアライメント法

ヒューリスティックアルゴリズム
の開発



STEP 1
N次元DPは（N=4ですら）
非実用的
一般にはNP困難
プログレッシブアライメント
1.
2.

入力配列
近隣結合法などを用いて案内
木を作る
類似度が高い節点から低い節
点へという順番で、配列対配列、
配列対プロファイル、プロファイ
ル対プロファイルのアラインメン
トを順次計算
逐次改善法

「配列を一本取り除いては、アラ
インメントしなおす」を繰り返す
STEP 2
③
①
②
プログレッシブアライメント
A C C - GA A C - - GA T
- C C A GA T
- C GA - A T
A C C GA A C - GA T
A C C GA
C C A GA T
C GA - A T
A C GA T
C C A GA T
C GA A T
プロファイル-プロファイル・アライメント

各列を１文字のように扱うことにより、DPにより計算
Profile vs. Profile
A C C GA A C C - GA A C - GA T
A C - - GA T
- C C A GA T
C C A GA T
- C GA - A T
C GA - A T
A C C GA
C C A GA T
C GA - A T
Sequnce vs. Profile
A C C - GA - C C A GA T
- C GA - A T
Score for
column pair
A
A
C
G
Score for
column pair
C
C
G
逐次改善法

「配列を一本取り除いては、アラインメントしなおす」
を繰り返す
モチーフ発見


モチーフ :共通の性質を持つ遺伝子などに現れる共通の文字列
パターン
決定的表現法
正規表現などを用いる（例： A-x(1,3)-[CG]）
 一般にNP困難。学習理論において数多くの研究
 正例のみならず、
3.8
A
負例が与えられることが多い


確率的表現法

重み行列（プロファイル）
Σ×[1…L] から実数への関数

HMM (Hidden Markov Models)
-3.5
1.2
2.3
C
1.5
1.3
-0.3
-4.6
G
T
-1.5
-2.9
4.2
3.1
0.2
-4.1
3.7
-1.3
A
C
G
G
A
score= 3.8 + 1.3 + 4.2 + 3.1
C
局所マルチプルアライメント
(Local Multiple Alignment)


複数配列と長さLが与えられた時、スコア最大と
なるように各配列から長さLの部分列を抽出
モチーフ（共通の性質を持つ遺伝子などに共通
の部分パターン）抽出などに有用
Sequence 1
Sequence 2
Sequence 3
A A T C G G T
A A T C C G T
A T T C G G A
相対エントロピースコアのもとでの
局所マルチプルアライメント

相対エントロピースコアの定義



fj(a): （モチーフ領域の）j列目におけるaの出現頻度
p(a): aの出現頻度（事前確率）
L: モチーフ領域の長さ
score 


 Lj1a
f j (a) log
実用的アルゴリズム
 Gibbsサンプリング, EM
NP困難
f j (a)
p(a)
相対エントロピースコア
score 

 Lj1a f j (a) log
f j (a)


p(a)

ti
A A T C G G T
s1
s2
s3
A A T C C G T
A T T C G G A
L=7
f1(A)=1, f1(C)=f1(G)=f1(T)=0
f2(A)=2/3, f2(T)=1/3,
f2(C)=f2(G)=0, …
p(A)=p(C )=p(G)=p(T)=1/4
Gibbs サンプリング
1.
2.
3.
4.
5.
各配列xjからランダム
に部分配列tjを選ぶ
1個の配列xiをランダム
に選ぶ
L f (t 'i[ j ])
j

xiの部分列ti’を j 1 p(t'i[ j])
に比例する確率で選ぶ
ti をti’ でおきかえる
ステップ2-4を十分な回
数だけ繰り返す
( ti[j]: 部分列ti のj列目の文字 )
Step 1
x1
t1
x2
x3
t2
t3
Step 2-3
Probabilistic Search
x2
t2’
Step 4
x1
x2
x3
t1
t2’
t3
講義のまとめ(配列アライメント
2)

配列のマルチプルアライメント法

多次元DP
 プログレッシブアライメント
 モチーフ発見
 局所マルチプルアライメント
参考文献


阿久津、浅井、矢田訳：バイオインフォマティクス－確
率モデルによる遺伝子配列解析―、医学出版、2001

Download Report