42digest首页
加权食物网络使计算系统发育多样性更加艰难

Weighted Food Webs Make Computing Phylogenetic Diversity So Much Harder

Jannik Schestag

arXiv
2025年10月7日

植物发育树代表某些物种及其可能的祖先。 在这样的树中,今天的物种是叶子,从u到v的边缘表示u是v的祖先。 这些边缘的重量表示系统发育距离。 一组物种A的系统发育多样性(PD)是系统发育树根与A物种之间的任何路径上的边缘的总重量。 选择一组小物种,为给定的植物发育树最大限度地发挥系统发育多样性,是保护规划中的一项基本任务,其中有限的资源自然阻止拯救所有物种。 可以通过贪婪的算法找到最佳解决方案[Steel, Systematic Biology, 2005; Pardi and Goldman, PLoS Genetics, 2005]。 然而,当给出一个代表捕食者-捕食者关系的食物网时,找到一组优化系统发育多样性的物种,条件是每个被拯救的物种应该能够在保存的物种中找到食物,这是NP-hard[Spillner等人,IEEE / ACM,2008]。 我们提出了这个问题的概括,在生物考虑的启发下,食物网具有加权边缘,以代表捕食者与猎物关系的重要性。 我们表明,这个版本是NP-硬,即使两个结构,食物网和系统发育树,都是恒星。 为了应对这种棘手性,我们朝两个方向前进。 首先,我们研究一些特殊情况,如果一个物种的猎物被保存下来,它只能生存。 其次,我们通过参数化复杂性的镜头来分析这些问题。 我们的结果包括,在食物网的顶点覆盖数上,找到一个解决方案是固定的参数,假设系统发育树是恒星。

Phylogenetic trees represent certain species and their likely ancestors. In such a tree, present-day species are leaves and an edge from u to v indicates that u is an ancestor of v. Weights on these edges indicate the phylogenetic distance. The phylogenetic diversity (PD) of a set of species A is the total weight of edges that are on any path between the root of the phylogenetic tree and a species in A. Selecting a small set of species that maximizes phylogenetic diversity for a given phylogenet...