遺伝的な距離に基づいた家系図推定問題

摘要

進化系統樹とは地球上の生物が、共通の祖先から進化したと考えた時の、種間の進化的な関係を表現した木構造である。 遺伝的な情報から進化系統樹を推定する方法に対する研究はさかんに行われてきた。 また系統樹の一部に修正を加えたデータ構造を推定する研究も近年行われきている。 これに対し、家系図は進化系統樹をさらに詳しくしたものと考えることができる。 進化系統樹をグラフで表現すれば有向木になるのに対し、家系図は入次数が2以下の非閉路的有向グラフとなる。 本稿では、与えられた2節点間の遺伝的距離を満足する家系図を全て列挙する問題を考え、所望の家系図の全てが、節点数を増やすことなく一つの有向グラフで表現できることを示し、それを得るO(m{sup}3)時間アルゴリズムを与える。