Frederick A. Matsen. ConstNJ: an algorithm to reconstruct sets of phylogenetic trees satisfying pairwise topological constraints. In JCB, Vol. 17(6):799818, 2010. Keywords: from distances, Program constNJ, reconstruction. Note: http://arxiv.org/abs/0901.1598v2.
Toggle abstract
"This article introduces constNJ (constrained neighborjoining), an algorithm for phylogenetic reconstruction of sets of trees with constrained pairwise rooted subtreepruneregraft (rSPR) distance. We are motivated by the problem of constructing sets of trees that must fit into a recombination, hybridization, or similar network. Rather than first finding a set of trees that 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 treelike manner, such as blocks of an alignment which do not contain any recombination breakpoints. The other input is a set of rSPR constraint inequalities for any set of pairs of trees. constNJ is consistent and a strict generalization of the neighborjoining algorithm; it uses the new notion of maximum agreement partitions (MAPs) to assure that the resulting trees satisfy the given rSPR distance constraints. Copyright 2010, Mary Ann Liebert, Inc."
