進化生物学における離散最適化問題の数理的研究

点击翻译按钮获取中文摘要

進化生物学における最節約原理の数学的定式化および基本的定理が花沢正純、成嶋弘らによって与えられ、これらの結果を基礎にして系統樹の祖先形質最節約復元問題(MPR問題)の数理的研究が進められ、平成8(1996)年度には、その研究において重要な概念であるACCTRAN復元の性質を浮き彫りにする次の二つの定理が得られた。第1定理(ACCTRANの完全最節約性):ACCTRAN復元は自分自身を含め、そのすべての部分木が最節約性を持つ。第2定理(ACCTRANの極値性):ACCTRAN復元はその各ノードにおいて、最節約復元が取り得る形質値の最大値または最小値のいずれかをとる。さらに、大域的最適解(祖先と現存種の多重形質値が与えられたとき、その間の全長を最小化する樹形および中間種の形質値を同時に与える解)を求める問題(第2種のMPR問題)は、一般的には、Steiner問題と結びつけられ、NP完全問題であることが証明されていたが、単一形質または単一化された多重形質の場合に、簡明な方法で本質的に一意な大域的最適解が求まることを示した。平成9(1997)年度には、ACCTRAN復元の最大元予想問題に取り組む中で、最節約復元順序集合(MPR-poset)のσ(γ)-versionの定式化、およびその束論的性質の研究が進められ、予想の反例やいくつかの定理が得られた。そのうち最も重要な定理は次の通りである。最小元定理:σ(γ)-version MPR-posetは最小元をもつ。