DS-1-1 Robustness of Greedy Type Minimum Evolution Algorithms

スポンサーリンク

概要

• 論文の詳細を見る

• For a phylogeny reconstruction problem, Desper and Gascuel [2] proposed Greedy Minimum Evolution algorithm (in short, GME) and Balanced Minimum Evolution algorithm (in short, BME). Both of them are faster than the current major algorithm, Neighbor Joining (in short, NJ); however, less accurate when an input distance matrix has errors. In this paper, we prove that BME has the same optimal robustness to such errors as NJ but GME does not. Precisely, we prove that if the maximum distance error is less than a half of the minimum edge length of the target tree, then BME reconstruct it correctly. On the other hand, there is some distance matrix such that maximum distance error is less than 2/√<n> of the minimum edge length of the target tree, for which GME fails to reconstruct the target tree.

• 2006-03-08

著者

• 繁住 健哉

  東京工業大学

• 繁住 健哉

  東京工業大学情報理工学研究科数理・計算科学専攻

関連論文

• 2-E-6 無限サーバ待ち行列がつくるスケールフリー区間グラフ : クラスタ係数の評価(待ち行列(2))
• 2-B-4 無限サーバ待ち行列がつくるスケールフリー区間グラフ(待ち行列(2))
• On NK-Community Problem (Theoretical Computer Science and its Applications)
• DS-1-5 The Greedy Minimum Evolution Algorithm with an Appropriate Input Order
• DS-1-1 Robustness of Greedy Type Minimum Evolution Algorithms
• Robustness of Greedy Type Minimum Evolution Algorithms (計算理論とアルゴリズムの新展開 RIMS研究集会報告集)

スポンサーリンク