MINIMIZING THE AVERAGE DISTANCE TO A CLOSEST LEAF IN A PHYLOGENETIC TREE

Abstract. When performing an analysis on a collection of molecular se-quences, it can be convenient to reduce the number of sequences under con-sideration while maintaining some characteristic of a larger collection of se-quences. For example, one may wish to select a subset of high-quality se-quences that represent the diversity of a larger collection of sequences. One may also wish to specialize a large database of characterized “reference se-quences ” to a smaller subset that is as close as possible on average to a col-lection of “query sequences ” of interest. Such a representative subset can be useful whenever one wishes to find a set of reference sequences that is appro-priate 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 pro-gram 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 cri-terion 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. 1