系統樹作成アルゴリズムの

性能評価実験

日本大学 文理学部 情報システム解析学科

谷研究室 西村 久香

目次

卒業研究の目標

系統樹の定義

距離算出法

系統樹作成法

実験結果

今後の目標

目次

卒業研究の目標

系統樹の定義

距離算出法

系統樹作成法

実験結果

今後の目標

卒業研究の目標

コンピュータの発達等もあり1990年以降

Bioinfomaticsが研究され発展し始めた

種の進化をDNAの塩基配列変換数で

求めた距離を用いて系統樹を作成されてきた

その有効性を確かめたい！！

2001,2003 Ming Li らにより定義されたKolmogorov記述量

を用いて算出した距離の有効性が主張されている

卒業研究の目標

遺伝子とは

ゲノムとは

DNA

ヒトの場合２３対４６本の染色体全て

DNAの塩基配列

ある生物がもつ遺伝情報の全体

ゲノムの中で生命活動を維持するための

機能的な部品を規定しているところ

DNAは塩基、糖、リン酸から構成されている

塩基配列はA(アデニン),G(グアニン),C(シトシン),

T(チミン)からなり、A,G,C,Tの4文字からなる

文字列とみなせる

卒業研究の目標

コンピュータの発達等もあり1990年以降

Bioinfomaticsが研究され発展し始めた

種の進化をDNAの塩基配列変換数で

求めた距離を用いて系統樹を作成されてきた

2001,2003 Ming Li らにより定義されたKolmogorov記述量

を用いて算出した距離の有効性が主張されている

その有効性を確かめたい！！

卒業研究の目標

系統樹作成法２種類と距離算出法３種類を

それぞれ組み合わせて６通り比較実験する

UPGMA法

NJ法

Kolmogorov記述量を用いた距離1

Kolmogorov記述量を用いた距離2

塩基配列の変換数

系統樹作成法

距離算出法

（2001年に定義された）

（2003年に定義された）

卒業研究の目標

系統樹作成法２種類と距離算出法３種類を

それぞれ組み合わせて６通り比較実験する

UPGMA法

NJ法

塩基配列の変換数

系統樹作成法

Kolmogorov記述量を用いた距離1

Kolmogorov記述量を用いた距離2

距離算出法

（2001年に定義された）

（2003年に定義された）

卒業研究の目標

系統樹の利用例

★生徒のプログラム課題の中から盗品（写していないか）を

見つけ出す(Algorithmic Statistics Peter Gacs 2001)

今回作った

プログラム実行例

卒業研究の目標

S

V

卒業研究の目標

V

H

目次

卒業研究の目標

系統樹の定義

距離算出法

系統樹作成法

実験結果

今後の目標

系統樹の定義

系統樹

生物間の進化関係を示す二次元グラフ

ピグミーチンパンジー

チンパンジー

ヒト

系統樹の例

系統樹の定義

配列の場合

別個の生物から得られる特定の

遺伝子間の進化関係を表す

それら別個の配列：『分類単位』

系統樹上で系統学的に異なる単位

配列A

配列B

配列C

配列D

配列A

配列B

配列C

配列D

配列A

配列B

配列C

配列D

根

根

=

同じ

系統樹の定義

系統樹は

分類単位を表す葉，

下図では配列AからDとして

示されている分類単位間の関係を表す

節と枝からなっている

配列A

配列B

配列C

配列D

：葉

：枝

：節

配列A

配列B

配列C

配列D

有根系統樹

無根系統樹

根

枝長

枝長

系統樹の定義

有根系統樹 UPGMA

無根系統樹 NJ

配列A

配列B

配列C

配列D

：葉

：枝

：節

配列A

配列B

配列C

配列D

有根系統樹

無根系統樹

根

AとBの共通祖先

CとDの共通祖先

系統樹の定義

有根系統樹 根の基部にある節がその他の全配列の

共通祖先（最も古い祖先）であることを

示している

無根系統樹 最も古い祖先の位置を明らかにして

いない

配列A

配列B

配列C

配列D

：葉

：枝

：節

配列A

配列B

配列C

配列D

有根系統樹

無根系統樹

根

目次

卒業研究の目標

系統樹の定義

距離算出法

系統樹作成法

実験結果

今後の目標

距離

系統樹を作る際必要となる

配列間の距離の算出方法

系統樹作成法の前に・・・

距離

例：以下のような４つの配列があるとする

距離

配列間の距離表の作成方法

Kolmogorov記述量を用いた距離

塩基配列の変換数を用いた距離

距離

Kolmogorov記述量を用いた距離

：yを用いたときのxの情報量

：xの情報量（εは空の文字列）

：xとyを結合した情報量

このままでは計算できないのでbzip2を使う

2001年に紹介

2003年に紹介

距離1

距離2

目次

卒業研究の目標

系統樹の定義

距離算出法

.Kolmogorov記述量を用いた距離1

.Kolmogorov記述量を用いた距離2

.塩基配列の変換数を用いた距離

系統樹作成法

実験結果

今後の目標

距離

Kolmogorov記述量を用いた距離1

計算可能な距離D

（yを用いた時のxの情報量） （xとyを結合した情報量）

－（yの情報量）

距離

求めた距離から距離表を作成

目次

卒業研究の目標

系統樹の定義

距離算出法

.Kolmogorov記述量を用いた距離1

.Kolmogorov記述量を用いた距離2

.塩基配列の変換数を用いた距離

系統樹作成法

実験結果

今後の目標

距離

Kolmogorov	記述量を用いた距離2

計算可能な距離D

（yを用いた時のxの情報量） （xとyを結合した情報量）

－（yの情報量）

距離

求めた距離から距離表を作成

距離

目次

卒業研究の目標

系統樹の定義

距離算出法

.Kolmogorov記述量を用いた距離1

.Kolmogorov記述量を用いた距離2

.塩基配列の変換数を用いた距離

系統樹作成法

実験結果

今後の目標

距離

塩基配列の変換数を用いた距離

一方の配列をもう一方の配列に

変換するのに必要なステップ数

距離

網掛け部分3ヶ所変換

配列A，B間の距離とは？

配列A，B間の距離は3

距離

求めた距離から距離表を作成

距離

塩基配列の長さが違う場合

アラインメントを行う

距離

塩基配列の長さが違う場合

アラインメントを行う

文字列が与えられた時に、

各文字列にギャップ記号（－）を挿入して

できるだけ多くの要素が対応するように並べ、

全ての文字列の長さが同じになるようにすること

A – G C T

T C G C T

例

距離

塩基配列の長さが違う場合

系統樹では2本の配列でなく

多数の配列を使用する

複数の配列を同時に考慮しながら

アラインメントを行う必要がある

距離

塩基配列の長さが違う場合

系統樹では2本の配列でなく

多数の配列を使用する

複数の配列を同時に考慮しながら

アラインメントを行う必要がある

DNAの塩基配列は数百の要素

からなっている

距離

塩基配列の長さが違う場合

系統樹では2本の配列でなく

多数の配列を使用する

複数の配列を同時に考慮しながら

アラインメントを行う必要がある

DNAの塩基配列は数百の要素

からなっている

距離

塩基配列の長さが違う場合

DNAの塩基配列は数百の要素

からなっている

コンピュータで解くには今なお困難とされている

距離

塩基配列の長さが違う場合

DNAの塩基配列は数百の要素

からなっている

高速なアルゴリズムを持たないことが

強く予想される性質を持つことが証明されている

実際に論文等に掲載されているデータは

スーパーコンピュータで計算されている

なので

本研究では塩基配列の距離は除いて

実験を行った

目次

卒業研究の目標

系統樹の定義

距離算出法

系統樹作成法

実験結果

今後の目標

目次

卒業研究の目標

系統樹の定義

距離算出法

系統樹作成法

.UPGMA法(平均距離法)

.NJ法

.比較

実験結果

今後の目標

ＵＰＧＭＡ

距離表を作成

最も近縁の塩基配列間の

枝長を計算

平均化された距離を用いて

距離表を更新

全ての葉が一つの木に

取り込まれたか

系統樹の根の位置が推定される

yes

no

準備

以下の距離表からUPGMA法を用いて，

系統樹を作成する

距離表2

距離表の最小値を見つける 近縁な配列

ＵＰＧＭＡ

距離表を作成

最も近縁の塩基配列間の

枝長を計算

平均化された距離を用いて

距離表を更新

全ての葉が一つの木に

取り込まれたか

系統樹の根の位置が推定される

yes

no

距離表2

A

B

a

b

配列A，Bが近縁

ＵＰＧＭＡ

AB

距離表2

配列A，Bが近縁

1

1

ＵＰＧＭＡ

A

B

平均をもとめる

AB

ＵＰＧＭＡ

距離表を作成

最も近縁の塩基配列間の

枝長を計算

平均化された距離を用いて

距離表を更新

全ての葉が一つの木に

取り込まれたか

系統樹の根の位置が推定される

yes

no

1

1

A

B

AB

ＵＰＧＭＡ

距離表2

1

1

A

B

AB

A

C

D

4

ＵＰＧＭＡ

距離表2

1

1

A

B

AB

A

C

D

6

4

ＵＰＧＭＡ

距離表2

ＵＰＧＭＡ

距離表を作成

最も近縁の塩基配列間の

枝長を計算

平均化された距離を用いて

距離表を更新

全ての葉が一つの木に

取り込まれたか

系統樹の根の位置が推定される

yes

no

A

B

C

D

E

F

1

2

1

1

2

2

1

1

4

1

ROOT

ＵＰＧＭＡ

距離表2

目次

卒業研究の目標

系統樹の定義

距離算出法

系統樹作成法

.UPGMA法

.NJ法(近隣結合法)

.比較

実験結果

今後の目標

NJ法

Lに残った葉が２つ

残った葉の間に枝を張って終了

Yes

No

新しいノードを作り

ペアへの枝長を計算

Lからペアを削除し

新しいノードから

葉への距離を計算

新しいノードをLに追加

近隣の葉のペアを選ぶ

Lを全ての葉の集合として初期化

距離表を作成する

NJ法

流れ

STEP 1

D

B

A

C

E

F

STEP 1

初期状態

NJ法

流れ

STEP 1

STEP 1

STEP 1

NJ法

流れ

STEP 1

STEP 2

ABのペアの場合…

STEP 2

M を求める

ij

NJ法

流れ

STEP 1

STEP 3

ここではＡＢを選ぶ

ＡＢは近隣

STEP 2

D

B

A

C

E

F

NJ法

流れ

STEP 1

STEP 3

ここではＡＢを選ぶ

ＡＢは近隣

”U”と呼ばれる新しいnodeを作る

STEP 2

D

B

A

C

E

F

U

NJ法

流れ

STEP 1

STEP 3

node UからAやBへの枝長を計算する

D

B

A

C

E

F

U

1

4

node Uからそれぞれの末端のnode

までの新しい距離を定義する

STEP 3

NJ法

流れ

STEP 1

STEP 4

D

B

A

C

E

F

U

1

4

STEP 4

NJ法

流れ

STEP 1

STEP 1

D

B

A

C

E

F

U

1

4

STEP 1にもどる

NJ法

流れ

STEP 1

系統樹完成

D

B

A

C

E

F

U

1

4

P

3

2

Q

1

2

R

1

5

1

系統樹完成

目次

卒業研究の目標

系統樹の定義

距離算出法

系統樹作成法

.UPGMA法

.NJ法

.比較

実験結果

今後の目標

比較

距離表2

D

B

A

C

E

F

1

1

2

2

1

2

1

5

1

A

B

C

D

E

F

1

2

1

1

2

2

1

1

4

1

NJ法

UPGMA法

目次

卒業研究の目標

系統樹の定義

距離算出法

系統樹作成法

実験結果

今後の目標

比較

UPGMAと塩基変換

NJと塩基変換

UPGMAとKolmogorov1

UPGMAとKolmogorov2

NJとKolmogorov1

NJとKolmogorov2

A

A

A

A

A

A

B

B

B

B

B

B

C

C

C

C

C

C

D

D

D

D

D

D

D

D

比較

UPGMAと塩基変換

NJと塩基変換

UPGMAとKolmogorov1

UPGMAとKolmogorov2

NJとKolmogorov1

NJとKolmogorov2

A

A

A

A

A

A

B

B

B

B

B

B

C

C

C

C

C

C

D

D

D

D

D

D

D

D

比較

UPGMAと塩基変換

NJと塩基変換

UPGMAとKolmogorov1

UPGMAとKolmogorov2

NJとKolmogorov1

NJとKolmogorov2

A

A

A

A

A

A

B

B

B

B

B

B

C

C

C

C

C

C

D

D

D

D

D

D

D

D

比較

mammal(NJ)

mammal(UPGMA)

比較

reyes(UPGMA)

reyes(NJ)

比較

UPGMA(距離1)

UPGMA(距離2)

NJ(距離1)

NJ(距離2)

目次

卒業研究の目標

系統樹の定義

距離算出法

系統樹作成法

実験結果

今後の目標

今後の目標

今後の目標

今回Kolmogorov記述量を用いた距離にbzip2を使用したが、他の圧縮方法で距離を求め系統樹を作成する

宿題の盗作を見つけるツールの様に役に立つツールを考える

END

Hisaka Nishimura

2004-12-23T23:23:46