Network Phylogenetic Diversity (Network-PD) is a measure for the diversity of a set of species based on a rooted phylogenetic network (with branch lengths and inheritance probabilities on the reticulation edges) describing the evolution of those species. We consider the Max-Network-PD problem: given such a network, find k species with maximum Network-PD score. We show that this problem is fixed-parameter tractable (FPT) for binary networks, by describing an optimal algorithm running in  \(\mathcal {O}(2^r \log (k)(n+r))\)  time, with n the total number of species in the network and r its reticulation number. Furthermore, we show that Max-Network-PD is NP-hard for level-1 networks, proving that, unless P = NP, the FPT approach cannot be extended by using the level as parameter instead of the reticulation number.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Phylogenetic Network Diversity Parameterized by Reticulation Number and Beyond

  • Leo van Iersel,
  • Mark Jones,
  • Jannik Schestag,
  • Celine Scornavacca,
  • Mathias Weller

摘要

Network Phylogenetic Diversity (Network-PD) is a measure for the diversity of a set of species based on a rooted phylogenetic network (with branch lengths and inheritance probabilities on the reticulation edges) describing the evolution of those species. We consider the Max-Network-PD problem: given such a network, find k species with maximum Network-PD score. We show that this problem is fixed-parameter tractable (FPT) for binary networks, by describing an optimal algorithm running in  \(\mathcal {O}(2^r \log (k)(n+r))\)  time, with n the total number of species in the network and r its reticulation number. Furthermore, we show that Max-Network-PD is NP-hard for level-1 networks, proving that, unless P = NP, the FPT approach cannot be extended by using the level as parameter instead of the reticulation number.