| 講演名 | 2001/7/9 系統樹最節約復元の部分木に関する最小性について 宮川 幹平, 成嶋 弘, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 外点に付値された木構造が与えられたときに, その木の長さを最小化するような内点への値付け(最節約復元)を考える第1最節約復元問題について, その最節約復元すべてを求めるアルゴリズムは既に与えられているが, 一般に最節約復元の個数は木の頂点数で上界を定められない.各最節約復元に対して, 与えられた木をある外点で根付けしたとき, 各部分木の全長をどれだけ最小化しているかを示す指標として歪み指数(distortion index)及び歪み列(distortion sequence)を導入し, その基準の下での最節約復元全体の構造を明らかにする.具体的には, この基準の下で最適又は最悪な最節約復元の特徴付けとこれらを決定するためのアルゴリズム, 及びこの基準(順序)による最節約復元全体の半順序集合が下に完備な半束となることを示す. |
| 抄録(英) | The First Most-Parsimonious Reconstruction Problem is: for a given tree (called an eltree) whose endnodes are evaluated, to find an assignment to all internal nodes of the tree, so as to minimize the total length of the tree. Such assingment is called an MPR. On this problem, an algorithm which enumerates all MPRs on a given el-tree has already given. In this paper, we introduce indicators for each MPR, that is, the distortion index and the distortion sequence, which show how an MPR minimizes each length of subtrees on a rooted el-tree. We characterize the best (or worst) MPR on base of those indicators and a poset induced by those indicators. |
| キーワード(和) | 進化系統樹 / 最節約復元 / 形質状態最適化 / 束論的特徴付け / 歪み列 |
| キーワード(英) | Evolutionary tree / MPR / Character-state optimization / Lattice-theoretic properties / Distortion sequence |
| 資料番号 | COMP2001-25 |
| 発行日 |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 2001/7/9(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Theoretical Foundations of Computing (COMP) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 系統樹最節約復元の部分木に関する最小性について |
| サブタイトル（和） | |
| タイトル（英） | Some properties of the distortion index/sequence on all MPRs |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 進化系統樹 / Evolutionary tree |
| キーワード(2)（和/英） | 最節約復元 / MPR |
| キーワード(3)（和/英） | 形質状態最適化 / Character-state optimization |
| キーワード(4)（和/英） | 束論的特徴付け / Lattice-theoretic properties |
| キーワード(5)（和/英） | 歪み列 / Distortion sequence |
| 第 1 著者 氏名（和/英） | 宮川 幹平 / Kampei Miyakawa |
| 第 1 著者 所属（和/英） | 電気通信大学大学院電気通信学研究科情報工学専攻 Course of Computer Science and Information Mathematics, Graduate School of Electro-Communication, The University of Electro-Communications. |
| 第 2 著者 氏名（和/英） | 成嶋 弘 / Hiroshi Narushima |
| 第 2 著者 所属（和/英） | 東海大学福岡短期大学情報処理学科 Department of Information Processing, Tokai University Fukuoka Junior College. |
| 発表年月日 | 2001/7/9 |
| 資料番号 | COMP2001-25 |
| 巻番号（vol） | vol.101 |
| 号番号（no） | 184 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |