系統分類学における組合せ論的問題の研究

系统分类学组合问题的研究

• 批准号: 07804011
• 负责人: 成嶋 弘
• 金额: $ 1.28万
• 依托单位: Tokai University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for General Scientific Research (C)
• 财政年份: 1995
• 资助国家: 日本
• 起止时间: 1995 至 无数据
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-07804011/
• 关键词: 進化生物学; 系統樹; 最節約復元問題; MPR-poset; DELTRAN復元; ACCTRAN復元; 線形時間アルゴリズム

系統分類学における系統樹と仮想的形質状態の最節約復元問題を数学的に厳密に定式化することによって、系統分類学と離散数学の接点に新しい研究分野を生み、理論的および実際的両方の側面から独創的研究を展開することが大きな目的であるが、この目的は少なからず実現されつつある。当該年度の目標であった次の2点の内、1.は予定通り達成され、2.はACCTRAN復元の場合に達成された。1.先に研究代表者等によって与えられた最節約復元問題に対する一般的解法のアルゴリズム論的改良および計算量の決定。2.最節約復元全体からなる順序集合(MPR-poset)の構造、特に進化学的に意味のあるDELTRAN復元とACCTRAN復元のMPR-posetにおける位置の決定や特徴付けを行う。今後、上記2.のDELTRAN復元の場合の決定や特徴付け、MTR-posetの束論的構造の研究、および系統樹も変動した場合のグローバル最節約復元問題、さらには形質状態の一般遷移関係の下での最節約復元問題の研究に取り組むと共に、得られたアルゴリズムのコンピュータインプリメントも行ない、最節約復元問題のソフトウェアの開発作成も行なう予定である。

The most economical complex problem of the phylogenetic tree and the ideal state is formulated in mathematics. The new research field of the phylogenetic tree and the discrete mathematics is generated. The theoretical field is developed in practice. The original research is carried out in large and small quantities. When the target of the year is within 2 points, 1. the target is reached, 2. the target is reached. 1. This paper first studies the improvement of the general solution and the determination of the calculation quantity of the optimal economic complex problem 2. The structure and evolution of the MPR-poset of the most economical complex set (MPR-poset) are discussed in detail. In the future, note 2. Determination and characterization of DELTRAN complex conditions, study of the structure of MTR-poset bundle theory, study of the most economical complex problems in the case of system tree movement, study of the most economical complex problems in the case of general transition relations of physical states, study of the most economical complex problems in the case of system tree movement, and study of the most economical complex problems in the case of system tree movement. The most economical recovery problem is solved by the development of the problem.

项目成果

成嶋 弘: "進化生物学における離散最適化問題の解法について-祖先形質復元問題に対する線形時間アルゴリズム-" 京大数解研講究録.

成岛浩：《论进化生物学中离散优化问题的解决-祖先性状恢复问题的线性时间算法-》京都大学数值研究讲座记录。

Masazumi Hanazawa: "Generating most parsimonious reconstructions on a tree: a generalization of the Farris-Swofford-Maddison method" Discrete Applied Mathematics. 56. 245-265 (1995)

Masazumi Hanazawa：“在树上生成最简约的重建：Farris-Swofford-Maddison 方法的推广”离散应用数学。

Hiroshi Narushima: "On a Role of the MPR-Poset of Most Parsimonious Reconstructions in Phylogenetic Analysis-A Combinatorial Optimization Problem in Phylogeny-" Proc. 7-th RAMP Symposium. 29-36 (1995)

Hiroshi Narushima：“论最简约重建的 MPR 集合在系统发育分析中的作用 - 系统发育中的组合优化问题 -”Proc。