Faster Computation of the Robinson-Foulds Distance between Phylogenetic Networks
スポンサーリンク
概要
- 論文の詳細を見る
Combinatorial Pattern Matching : 21st Annual Symposium, CPM 2010, New York, NY, USA, June 21-23, 2010.The Robinson-Foulds distance, which is the most widely used metric for comparing phylogenetic trees, has recently been generalized to phylogenetic networks. Given two networks N_1,N_2 with n leaves, m nodes, and e edges, the Robinson-Foulds distance measures the number of clusters of descendant leaves that are not shared by N_1and N_2. The fastest known algorithm for computing the Robinson-Foulds distance between those networks runs in O(m(m+e)) time. In this paper, we improve the time complexity to O(n(m + e)/ log n) for general networks and O(nm/log n) for general networks with bounded degree, and to optimal O(m+e) time for planar phylogenetic networks and boundedlevel phylogenetic networks. We also introduce the natural concept of theminimum spread of a phylogenetic network and show how the running time of our new algorithm depends on this parameter. As an example, we prove that the minimum spread of a level-k phylogenetic network is at most k + 1, which implies that for two level-k phylogenetic networks, our algorithm runs in O((k + 1)(m + e)) time.
論文 | ランダム
- 上関 その豊穣なる生態系に魅せられて (特集 JCO事故2周年--今、環境を守る) -- (上関原発予定地は希少種の宝庫だった--レポート山口県祝島)
- 電解ニッケル-リンメッキ皮膜の熱処理による分極特性の変化(合金メッキの研究-4-)
- 無電解ニッケル-リンメッキ皮膜の熱処理による分極特性(合金メッキの研究-3- 研究ノート)
- 無電解ニッケル-ホウ素メッキ皮膜の熱処理による相変化
- 電解析出によるニッケル-コバルト-リンメッキ皮膜の性状について