2009/01/12 by F. A. Matsen, Frederick A. Matsen, Matsen, Frederick A.
Biochemistry, Genetics and Molecular Biology · #FOS: Biological sciences #Genetic diversity and population structure #Genomics and Phylogenetic Studies #Plant and Fungal Species Descriptions #Populations and Evolution (q-bio.PE) #q-bio.PE
paper · pdf · doi:10.48550/arxiv.0901.1598
Please contact me with any questions or comments!
openalex publication_date 2009/01/12 · arxiv created 2009/01/20 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
This paper introduces constNJ, the first algorithm for phylogenetic reconstruction of sets of trees with constrained pairwise rooted subtree-prune regraft (rSPR) distance. We are motivated by the problem of constructing sets of trees which must fit into a recombination, hybridization, or similar network. Rather than first finding a set of trees which are optimal according to a phylogenetic criterion (e.g. likelihood or parsimony) and then attempting to fit them into a network, constNJ estimates the trees while enforcing specified rSPR distance constraints. The primary input for constNJ is a collection of distance matrices derived from sequence blocks which are assumed to have evolved in a tree-like manner, such as blocks of an alignment which do not contain any recombination breakpoints. The other input is a set of rSPR constraints for any set of pairs of trees. ConstNJ is consistent and a strict generalization of the neighbor-joining algorithm; it uses the new notion of "maximum agreement partitions" to assure that the resulting trees satisfy the given rSPR distance constraints.