Data from: Minimizing the average distance to a closest leaf in a phylogenetic tree

When performing an analysis on a collection of molecular sequences, it can be convenient to reduce the number of sequences under consideration while maintaining some characteristic of a larger collection of sequences. For example, one may wish to select a subset of high-quality sequences that represent the diversity of a larger collection of sequences. One may also wish to specialize a large database of characterized “reference sequences” to a smaller subset that is as close as possible on average to a collection of “query sequences” of interest. Such a representative subset can be useful whenever one wishes to find a set of reference sequences that is appropriate to use for comparative analysis of environmentally-derived sequences, such as for selecting “reference tree” sequences for phylogenetic placement of metagenomic reads. In this paper we formalize these problems in terms of the minimization of the Average Distance to the Closest Leaf (ADCL) and investigate algorithms to perform the relevant minimization. We show that the greedy algorithm is not effective, show that a variant of the Partitioning Among Medoids (PAM) heuristic gets stuck in local minima, and develop an exact dynamic programming approach. Using this exact program we note that the performance of PAM appears to be good for simulated trees, and is faster than the exact algorithm for small trees. On the other hand, the exact program gives solutions for all numbers of leaves less than or equal to the given desired number of leaves, while PAM only gives a solution for the pre-specified number of leaves. Via application to real data, we show that the ADCL criterion chooses chimeric sequences less often than random subsets, while the maximization of phylogenetic diversity chooses them more often than random. These algorithms have been implemented in publicly available software.在对分子序列集合开展分析时，在保留更大规模序列集合部分核心特征的前提下，缩减待分析序列的数量往往会带来诸多便利。例如，研究人员可能希望选取能代表更大规模序列集合多样性的优质序列子集；也可能需要将已注释的大型“参考序列”数据库精简为一个更小的子集，使其在平均距离上尽可能贴近目标查询序列集合。此类代表性子集在诸多场景中均可发挥作用：例如当需要选取适用于环境来源序列比较分析的参考序列集时——如为宏基因组读段的系统发育定位选取“参考树”序列时。本文中，我们以最小化至最近叶节点的平均距离（Average Distance to the Closest Leaf, ADCL）为目标，对上述问题进行形式化定义，并研究用于完成相关最小化任务的算法。我们证明了贪心算法在此场景下效果不佳，同时发现围绕中心点划分（Partitioning Among Medoids, PAM）启发式算法的变体易陷入局部最优，并提出了一种精确动态规划方法。借助该精确规划方法，我们发现PAM算法在模拟树场景下表现良好，且对于小规模树而言，其运行速度快于精确算法。但另一方面，精确算法可针对所有不超过预设叶节点数的规模生成解，而PAM算法仅能针对预先指定的叶节点数生成唯一解。通过真实数据应用验证，我们发现ADCL准则选取嵌合序列的概率低于随机子集，而最大化系统发育多样性的准则选取嵌合序列的概率则高于随机子集。上述算法已在公开可用的软件中实现。