第5回 2019/5/29

講師：斎藤成也
参考書：Introduction to Evolutionary Genomics Second Edition
参考書：バイオインフォマティクスの数理とアルゴリズム

17.1 Classification of tree-building hogehoge

進化距離は、基本的に距離と言っているだけあり、対象律が成り立っている。つまり、下三角行列のみが必要。

系統樹には根がある場合と根がない場合の2つのパターンがある。

17.2 Distance matrix methods

進化系統樹の推定法にはいくつかの方法論があるが、最も広く利用されている方法論は、最初に何らかの方法で全ての葉間の距離（遺伝子配列間の距離）を計算したあとで、その距離情報だけから系統樹を推定する方法である。

よく使われている方法には、UPGMA(Unweighted Pair Group Method with Arithmetic mean)と近隣結合法(Neighbor-joining Method)がある。

以下では、$n$ 個の配列 $s_1,\ldots,s_n$ が最初に与えられ、$i<j$ なる配列対（$s_i,s_j$）全てについて、その間の距離 $d_{ij}$ が既に計算されているものとする。

なお、ここで $d_{ij}$ は必ずしも距離の定義を満たす必要はないが、非負かつ $d_{ij} = d_{ji}$ という条件は満たすものとする。

なお、配列間の距離は、一般にJukes-Cantor行列を用いて以下のように表されることがほとんどである。（配列対($s_i,s_j$)において、同じ文字が並ぶ列の比率を $f$ とする。）

$$d_{ij} = \frac{3}{4}\log\left(1-\frac{4}{3}f\right)$$

なお、この距離は $f$ が $0.75$ に近づくに従い、つまりランダムな置換に近づくに従い、無限大に発散することになることも確認できる。

UPGMA

UPGMA(Unweighted Pair Group Method with Arithmetic mean)は、最初は1個の配列からなるクラスタ（集合）をそれぞれ作り、距離が最も小さいクラスタを1つにまとめることを繰り返していくことによって、系統樹を構成していく。

アルゴリズム

$n$ 個の入力配列 $s_i(i=1,...,n)$ のそれぞれに対して、$i$ のみを要素とする集合 $C_i$ を作り、それらをリスト $L$ に入れる。また、各配列 $s_i$ に対応する葉 $i$ を作り、それを高さ $0$ の位置に置く。そして、すべての $i<j$ について $D_{ij} = d_{ij}$ とする。さらに、$k\leftarrow n+1$ とする。
$L$ から $D_{ij}$ が最小となる対 $(C_i,C_j)$ の一つを求める。
$C_k=C_i\cup C_j$ によって新たなクラスタ $C_k$ を作る。
節点 $i,j$ を子に持つ節点 $k$ を作り、高さ $D_{ij}/2$ の位置に配置する。
$L$ から $C_i$ と $C_j$ を削除して $C_k$ を追加する。
$C_k$ と、全ての他のクラスタ $C_l$ に対して距離 $D_{kl}$ を計算し、$k\leftarrow k+1$ とする。
ステップ $2\sim6$ を、$L$ の要素が $1$ 個になるまで繰り返す。

なお、クラスタ間の距離 $D_{kl}$ は、$C_k$ の要素と $C_j$ の要素間の平均距離、すなわち次の式により定義されるものとする。

$$D_{kl} = \frac{1}{|C_k||C_l|}\sum_{s_i\in C_k,s_j\in C_l}d_{ij}$$

$C_k=C_i\cup C_j$ という操作によって新たなクラスタ $C_k$ が生成されるたびに、$C_k$ と他のクラスタ $C_l$ との距離を計算する必要があるが、クラスタ間の距離 $D_{kl}$ は以下の式によって効率的に求めることができる。（計算量 $\mathrm{O}(n^2)\rightarrow\mathrm{O}(n))$）

$$D_{kl} = \frac{D_{il}|C_i| + D_{jl}|C_j|}{|C_i| + |C_j|}$$

正当性

UPGMA法によって推定される進化系統樹は、元の系統樹が分子時計(molecular clock)仮説（節点間の距離 $d_{ij}$ が節点間を結ぶパスに現れる枝長の和で与えられ、かつ根から葉までの距離が全て等しい）を満たす場合にのみ、元の系統樹と同じトポロジーとなる。

なお、この仮説は「系統樹のどの場所においても、配列の変異が同じ割合で起こる」という仮説である。

17.3 Neighbor-joining Method (近隣結合法)

Neighbor-joining Method は距離行列法の一種であり、星型の木(a)から近隣結合を段階的に適用することで無根の系統樹を効率的に生成する手法である。

UPGMA法では、距離が分子時計仮説に従って生成された場合にのみ、進化系統樹を正しく推定することが保証された。つまり、 - 根から葉までの距離が等しい - 節点間の距離がそれらを結ぶパス中の辺の長さの和に等しい

という条件を用いていたが、近隣結合法では、後者の条件のみを満たす場合でも進化系統樹を正しく推定することができる。

基本的な発想はUPGMA法と同じで、「葉から根にという順番で木を生成していく。」

相違点としては、「根は定まらず無根系統樹が生成されていく」ことと「結合すべき対の選び方および新たに生成された節点と他の節点との距離の計算方法」が異なることである。

距離の計算方法

「葉の間の距離がそれらを結ぶパス中の辺の長さの和に等しい」という条件が成立するとき、その距離は加法性(additivity)を満たす、という。

ここで、近隣の葉（同じ親を持つ葉）の対（$i,j$）を何らかの方法で見つけたとする。次に、$i,j$ を隣接する節点として持つ節点 $k$ を新たに作成し、$i,j$ を削除して $k$ を新たな葉として扱う。

この際にもちろん新しくできた $k$ から他の葉 $m$ までの距離を計算する必要があるが、これは加法性を用いると以下で計算できる。

$$d_{km} = \frac{1}{2}\left(d_{im} + d_{jm} -d_{ij}\right)$$

なお、この式が成立することは以下から明らか

$$d_{im} = d_{ik} + d_{km},\quad d_{jm} = d_{jk} + d_{km},\quad d_{ij} = d_{jk} + d_{jk}$$

近隣の葉（$i,j$）の選び方

次に、近隣の葉（$i,j$）の選び方についてだが、単純に $d_{ij}$ が最小になるものを選んでしまうと誤った対を選ぶ場合があるので、「他の葉までの平均距離を引く」ことによって補正した距離を用いる。具体的には次で定義される。

$$d^{\prime}_{ij} = d_{ij} - (r_i + r_j),\quad r_i = \frac{1}{|L| - 2}\sum_{h\in L}d_{ih}$$

なお、$L$ は（各時点での）葉の集合を表し、$L$ は葉の個数を表す。

アルゴリズム

$n$ 個の入力配列 $s_i(i=1,\ldots,n)$ のそれぞれについて、孤立した節点（葉）$i$ をつくり、それらの節点の集合を $L$ とする。また、$k\leftarrow n+1$ とする。
$L$ から $d^{\prime}$ が最小となる対（$i,j$）の1つを求める。
新しい節点 $k$ をつくり、$L$ 中の全ての $m$ について $d_{km} = \frac{1}{2}\left(d_{im} + d_{jm} - d_{ij}\right)$ を計算する。
節点 $k$ と節点 $i,j$ を枝で結び、$d_{ik} = \frac{1}{2}(d_{ij} + r_i - r_j), d_{jk} = \frac{1}{2}(d_{ij} - r_i + r_j)$ とする。
$L$ から節点 $i,j$ を削除して節点 $k$ を追加し、$k\leftarrow k+1$ とする。
ステップ $2\sim5$ を、$L$ の要素が2個になるまで繰り返し、最後に残った2個の節点を枝で結び、その長さを $d_{ij}$ とする。

上のアルゴリズムでは、$d_{ik}$ を $\frac{1}{2}(d_{ij} + r_i - r_j)$ によって計算しているが、これは

$$ \begin{aligned} d_{ik} &=d_{im} - d_{km} = d_{im} - \frac{1}{2}(d_{im} + d_{jm} - d_{ij})\\ &= \frac{1}{2}(d_{im} - d_{jm} + d_{ij})\\ &= \frac{1}{2}\left(d_{ij} + \frac{1}{|L| - 2}\sum_{h\in L - \{i,j\}}(d_{ih} - d_{jh})\right) \end{aligned} $$

によって正当性が確かめられる。

特徴

近隣結合法では、距離の加法性が満たされてさえいれば系統樹を正しく再構成できるという利点があるが、その一方で作成される系統樹が無根系統樹であるという欠点も持つ。

この問題に対処するため、無根系統樹において根の位置を決定する方法がいくつか考案されている。その中で広く使われている方法として、アウトグループ(outgroup)を利用する、というものがある。

これは、対象としている全ての種よりも明らかに遠い時期に枝分かれしたことがわかっている生物種を系統樹に追加し、アウトグループと直接つながっている節点を根とするという方法である。

17.7 Parsimony Method(最節約法)

ここまでは、配列間の距離情報を基に系統樹を推定する方法を説明してきたが、別のアプローチとして、必要な置換の回数が最小となる系統樹を推定する、という方法が提案されており、最節約法(Parsimony Method)と呼ばれている。

最節約法では、基本的に文字の挿入・欠失は考えずに、置換のみを考える。そのため、全ての入力配列の長さは $l$ であると仮定し、内部節点に全体として置換の回数が最小となるように長さ $l$ の配列をそれぞれ割り当てていく。

また、一般に文字 $a$ から文字 $b$ への置換コスト $w(a,b)$ を考え、コストの和の最小化を考える。節点 $i$ の親を $p(i)$ とし、根を $2n-1$ とすると、最節約法による進化系統樹推定問題は次のように定式化される。

定義

入力：長さ $l$ の $n$ 個の配列 $s_i,\ldots,s_n$
出力：$1,\ldots,n$ を葉とし、次のコストが最小となる有根系統樹 $T$ と、内部節点 $j$ への配列割り当て $s_j(j=nL1,\cdots, 2n-1)$

$$\sum_{j=1}^{2n-2}\sum_{i=1}^lw(s_{p(j)}[i],s_j[i])$$

この問題は、

系統樹のトポロジーを固定した場合に、置換の回数が最小となる内部節点への配列の割り当て
置換の回数が最小となるトポロジーの計算

の二種類が必要だが、後者に関しては多項式時間アルゴリズムが存在していないため、一般に最節約法はNP困難であることが知られている。

なお、前者に関しては動的計画法によって計算することが可能である。

分子進化学第5回

第5回 2019/5/29

17.1 Classification of tree-building hogehoge

17.2 Distance matrix methods

UPGMA

アルゴリズム

正当性

17.3 Neighbor-joining Method (近隣結合法)

距離の計算方法

近隣の葉（\(i,j\)）の選び方

アルゴリズム

特徴

17.7 Parsimony Method(最節約法)

定義

Table of Contents

Published

Last Updated

Category

Tags

Contact

Other contents