進化系統樹最節約復元問題の代数論・束論的観点からの研究

代数/丛理论视角下进化系统发育树最简约恢复问题研究

• 批准号: 16740069
• 负责人: 宮川 幹平
• 金额: $ 0.96万
• 依托单位: Tokai University Fukuoka Junior College
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Young Scientists (B)
• 财政年份: 2004
• 资助国家: 日本
• 起止时间: 2004 至 2005
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-16740069/
• 关键词: 進化系統樹; 最節約原理; 最節約復元; 結び規約; 分配束; 半順序集合; 系統樹推定問題; 最軽拡張; 結び既約

次数1の頂点に付値のされた単純木構造(el-tree)に対して,内点(次数2以上の頂点)の付値をel-treeの復元と呼ぶ。ある復元が与えられたとき,el-treeの各辺の長さを辺の両端点における付値の絶対値差,el-treeの長さをその総和と定義する。このとき,el-treeの長さを最小化するような復元を最節約復元(MPR)と呼ぶ。先行研究によって,与えられたel-treeのMPRは既に特徴付けられており,また,MPR全体の空間に,ある自然な順序関係を導入したとき,分配束をなすことがわかっている。本研究においては,これら先行研究の結果を受け,MPR束への代数的な興味として,結び演算で既約となる元(結び既約元)に焦点を当てた。結果として,(1)el-tree上の復元が,MPR束における結び規約元であるための必要十分条件の証明,(2)結び既約元を全て列挙する再帰アルゴリズムの提案とその計算量解析,(3)結び既約元からなるMPR束の部分半順序集合Pの効率的な構築法の提示,という成果を得た。(1)の成果をもとにした(2)のアルゴリズムにおいては,MPR束における結び既約元のどのひとつに関しても,与えられたel-treeの頂点数に関して線形時間で決定することができる。また,(3)においては,半順序集合Pにおける全ての被覆関係をel-treeの頂点数に関して線形時間で決定できることを示しており,このことと有限分配束の基本的な定理により,MPR束を代数的に構築するための生成元を効率よく構築できることが示せた。次に,問題自体の拡張として,対象を閉路を高々1つ含むグラフに拡張した場合について考察を行った。任意のMPRが,各頂点において取り得る値の範囲が既に知られていたことを発展させ,ある復元がMPRであるための必要十分条件とともに,全てのMPRを列挙する再帰アルゴリズムを提示した。

The vertex of degree 1 is assigned to the el-tree structure, and the vertex of degree 2 and above is assigned to the el-tree structure. The length of each side of the el-tree is equal to the end of the el-tree, and the length of the el-tree is equal to the end of the el-tree. Minimize the length of el-tree and restore the most economical restoration (MPR). First study the characteristics of MPR and its el-tree, and introduce the natural order relationship of MPR. In this study, the results of previous studies were received, and the interest of MPR bundle algebra was reduced. The results are as follows: (1) The proof of the necessary conditions for complex elements on el-tree,MPR bundle, and MPR bundle;(2) The analysis of computational quantities for the proposal of complex elements on el-tree, and MPR bundle;(3) The suggestion of the efficient method for partial semi-sequential sets P of complex elements on el-tree, and the construction of MPR bundle. (1)The result of the algorithm is that (2) the number of vertices of the tree is determined by the linear time of the MPR bundle and the number of vertices of the tree. The number of vertices of an el-tree is determined by the linear time of the semi-ordered set P, and the basic theorem of finite distribution bundles is shown in the algebraic construction of MPR bundles. Second, the problem itself is open, the image is closed, and the situation is closed. Any MPR, each vertex in the middle of the range to obtain the value of the range, both know the middle of the range to develop, restore the MPR, the necessary conditions, all MPR, the range to display the range to prompt.