近隣結合法のソースを表示

[[File:Neighbor joining 7 taxa start to finish diagram.svg|thumb|right|400px|近隣結合法のアルゴリズム]]
'''近隣結合法'''（きんりんけつごうほう、'''Neighbor joining method'''）は、[[系統樹]]を作製するためのボトムアップ式の[[クラスタ解析]]法。星型の樹形から出発してOTU（操作上分類単位、系統樹の葉にあたる分類群）をクラスタリングする各段階において、総分岐長を最小化するOTUの組を発見することを原理とする。近隣結合法では解析可能な系統樹の樹形や枝長を短時間で求めることができる。1987年に[[斎藤成也]]・[[根井正利]]が発表した<ref name=齋藤1987>{{Cite journal|url=http://mbe.oxfordjournals.org/content/4/4/406.long |author1=Saitou N |author2=Nei M |title=The neighbor-joining method: a new method for reconstructing phylogenetic trees |journal=Molecular Biology and Evolution |volume=4 |issue=4 |pages=406-425 |year=1987}}</ref>。

== 原理 ==
=== 基本的原理 ===
近隣結合法は[[距離行列法]]の一つである。距離行列法では、総枝長が最短となる系統樹が最適樹であるという仮定（最小進化原理）に基づいて系統樹が構築される。近隣結合法は、全ての配列の組において間の距離を計算して[[距離行列]]を構築する段階までは、他の距離行列法（[[非加重結合法]]、[[最小二乗法]]、{{仮リンク|最小進化法|en|Minimum evolution}}など）と共通する<ref name=松井2021>{{Cite journal|和書|title=分子系統解析の最前線 |author=松井求 |journal=JSBi Bioinformatics Review |volume=2 |issue=1 |pages=30-57 |year=2021 |url= https://doi.org/10.11234/jsbibr.2021.7 |doi=10.11234/jsbibr.2021.7}}{{オープンアクセス}}</ref>。

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

また、近隣結合法では進化速度が一定であるという仮定がされておらず<ref name=長谷川>{{Cite web|和書|title=第７章　進化と系統　-進化の歴史を再現する- |author=長谷川英祐 |publisher=[[北海道大学大学院農学研究院・大学院農学院・農学部]] |accessdate=2021-10-23 |url=http://lab.agr.hokudai.ac.jp/ecosys/ecolgy/Nattoku/nattoku7.htm}}</ref>、これは非加重結合法と異なる。進化速度が一定でない場合には誤った系統推定をしてしまう非加重結合法と異なり、系統樹の枝ごとに（すなわち生物ごとに）進化速度が変化していても、進化距離と系統樹上での経路の長さが等しい場合には最小進化原理を満たす系統樹を正確に構築できる<ref name=松井2021/>。

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

<math>d_{ab}=d_{ax}+d_{bx}</math>

=== アルゴリズム ===
近隣結合法では、進化的距離を計算した全ての生物に対して、まず出発点となる放射状の星状系統樹を暫定的に作成する<ref name=高松2005>{{Cite journal|和書|title=分子系統学の基礎 |author=高松進 |year=2005 |journal=植物防疫 |volume=59 |issue=3 |pages=64-69 |url=http://jppa.or.jp/archive/pdf/59_03_20.pdf}}</ref>。ここで、星状系統樹の中心に位置するノードをaとし、系統樹の葉にあたるノードに自然数をナンバリングする。葉の集合を<math>L</math>、葉の数を<math> |L|</math>とすると、この星状系統樹の枝長の総和<math>S_0</math>は以下の式で表される<ref name=松井2021/>。

<math>S_0=\sum_{i\in L}d_{ia}= \frac{1} {|L|-1}\sum_{i<j\in L}d_{ij}</math>

次に、葉iと葉jの生物を1対1で結合して括り出し、上図Bのような系統樹に変形する<ref name=高松2005/>。この新たな系統樹の枝長の総和<math>S_{ij}</math>は以下の式で表される<ref name=松井2021/>。

<math>S_{ij}=\frac{1} {2}(d_{ij}-\frac{1} {|L|-2}\sum_{k\in L}d_{ik}-\frac{1} {|L|-2}\sum_{k\in L}d_{jk}+\frac{2} {|L|-2}\sum_{i<j\in L}d_{ij})</math>

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

== 特徴 ==
近隣結合法は同じ距離行列法である[[非加重結合法]]のアルゴリズムを改変して1987年に日本の[[斎藤成也]]と[[根井正利]]により発表された手法で<ref name=齋藤1987/>、他の距離行列法を抑えて広く利用されている<ref name=隈2006>{{Cite journal|和書|title=実践的系統樹推定方法 |author1=隈啓一 |author2=加藤和貴 |year=2006 |volume=44 |issue=3 |pages=185-191 |journal=化学と生物 |url=https://doi.org/10.1271/kagakutoseibutsu1962.44.185 |doi=10.1271/kagakutoseibutsu1962.44.185}}{{フリーアクセス}}</ref><ref name=三中2009>{{Cite journal|和書|url=http://jppa.or.jp/archive/pdf/63_03_66.pdf |author=[[三中信宏]] |journal=植物防疫 |year=2009 |volume=63 |issue=3 |title=分子系統学：最近の進歩と今後の展望 |pages=192-196}}</ref>。2021年現在でも最大節約法・最尤法・ベイズ法と並んで標準的な解析手法である。松井 (2021) では、分子データを用いた種レベルの系統樹を作成する場合、進化距離が近く加法性を仮定できるのであれば近隣結合法を用いるのが良いとされている<ref name=松井2021/>。

近隣結合法での計算は当時から高速とされ<ref name=齋藤1987/>、2006年時点のコンピュータでは1000種類の内群を含む解析を一瞬で完了できる<ref name=隈2006/>。進化速度の一定性を仮定しないため、自然界で理想的なケースが多くない非加重結合法よりも広く適用できる点も長所である<ref name=長谷川/><ref name=隈2006/>。また、最初に与えられる[[距離行列]]が信頼できるものであれば正確性の高い樹形を構成できる点も特徴である<ref name=隈2006/>。ただし、そもそもの正確な距離行列の推定が容易ではないという指摘もされている<ref name=益子2003>{{Cite journal|和書|title=分枝系統樹構成法に関する最新技術動向|journal=情報処理学会第65回全国大会講演論文集 |author1=益子理絵 |author2=山田真介 |author3=山名早人 |year=2003 |pages=233-234 |issue=1}}</ref>。

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

== 出典 ==
{{Reflist}}

== 関連項目 ==
*[[非加重結合法]]（UPGMA）
*[[最大節約法]]（MP法）
*[[最尤推定|最尤法]]（ML法）
*[[ベイズ法]]（BI法）

{{デフォルトソート:きんりんけつこうほう}}
[[Category:系統学]]
[[Category:バイオインフォマティクス・アルゴリズム]]
[[Category:進化]]
[[Category:クラスター分析アルゴリズム]]