Мы используем файлы cookie.
Продолжая использовать сайт, вы даете свое согласие на работу с этими файлами.

近隣結合法

Подписчиков: 0, рейтинг: 0
近隣結合法のアルゴリズム

近隣結合法(きんりんけつごうほう、Neighbor joining method)は、系統樹を作製するためのボトムアップ式のクラスタ解析法。星型の樹形から出発してOTU(操作上分類単位、系統樹の葉にあたる分類群)をクラスタリングする各段階において、総分岐長を最小化するOTUの組を発見することを原理とする。近隣結合法では解析可能な系統樹の樹形や枝長を短時間で求めることができる。1987年に斎藤成也根井正利が発表した。

原理

基本的原理

近隣結合法は距離行列法の一つである。距離行列法では、総枝長が最短となる系統樹が最適樹であるという仮定(最小進化原理)に基づいて系統樹が構築される。近隣結合法は、全ての配列の組において間の距離を計算して距離行列を構築する段階までは、他の距離行列法(非加重結合法最小二乗法最小進化法など)と共通する。

最小二乗法や最小進化法との違いは、これら2つが可能なすべての系統樹で総枝長を計算して最小進化原理を満たす樹形を決定するのに対し、近隣結合法では系統樹作成の各ステップで最小進化原理を満たす葉(系統樹の節)の組を決定する点にある。より具体的には、生物同士の進化距離を生物の組ごとに計算し、距離の最も小さいもの同士を最初に接続し、次に近縁なものを続けて次々に接続していくという方法を取る。このため計算効率は上記2つの距離行列法に比べて良い。

また、近隣結合法では進化速度が一定であるという仮定がされておらず、これは非加重結合法と異なる。進化速度が一定でない場合には誤った系統推定をしてしまう非加重結合法と異なり、系統樹の枝ごとに(すなわち生物ごとに)進化速度が変化していても、進化距離と系統樹上での経路の長さが等しい場合には最小進化原理を満たす系統樹を正確に構築できる。

なお、進化距離と系統樹上での経路の長さが等しいことは、「加法性」が成り立つことを意味する。例として、子孫ノードaおよびbと祖先ノードxの3つのノードが存在し、ab間の進化距離を、各葉ノードとxの間の距離をおよびとすると、以下の式が成立する場合に加法性が成立する。

アルゴリズム

近隣結合法では、進化的距離を計算した全ての生物に対して、まず出発点となる放射状の星状系統樹を暫定的に作成する。ここで、星状系統樹の中心に位置するノードをaとし、系統樹の葉にあたるノードに自然数をナンバリングする。葉の集合を、葉の数をとすると、この星状系統樹の枝長の総和は以下の式で表される。

次に、葉iと葉jの生物を1対1で結合して括り出し、上図Bのような系統樹に変形する。この新たな系統樹の枝長の総和は以下の式で表される。

この時点で実行者はどの葉同士が近縁であるかを知らないため、全ての葉で括り出しの組み合わせを試すことになる。こうして総和を最小にするiとjの組み合わせを発見し、それを近隣として扱う。そしてこの近隣を1つに括り出して同様の操作を繰り返し、全ての葉が近隣として結合されて無根系統樹が出来上がると推定完了となる。

特徴

近隣結合法は同じ距離行列法である非加重結合法のアルゴリズムを改変して1987年に日本の斎藤成也根井正利により発表された手法で、他の距離行列法を抑えて広く利用されている。2021年現在でも最大節約法・最尤法・ベイズ法と並んで標準的な解析手法である。松井 (2021) では、分子データを用いた種レベルの系統樹を作成する場合、進化距離が近く加法性を仮定できるのであれば近隣結合法を用いるのが良いとされている。

近隣結合法での計算は当時から高速とされ、2006年時点のコンピュータでは1000種類の内群を含む解析を一瞬で完了できる。進化速度の一定性を仮定しないため、自然界で理想的なケースが多くない非加重結合法よりも広く適用できる点も長所である。また、最初に与えられる距離行列が信頼できるものであれば正確性の高い樹形を構成できる点も特徴である。ただし、そもそもの正確な距離行列の推定が容易ではないという指摘もされている。

また、これは距離行列法全てに該当する欠点であるが、形質状態を距離に変換する際に情報量の損失が起こり、異なる情報を持つ形質状態の配列が同じ距離として扱われる場合がある。

関連項目


Новое сообщение