An optimal algorithm to reconstruct trees from additive distance data.
In this article the question of reconstructing a phylogeny from additive distance data is addressed. Previous algorithms used the complete distance matrix of the n OTUs (Operational Taxonomic Unit), that corresponds to the tips of the tree. This used O(n2) computing time. It is shown that this is wasteful for biologically reasonable trees. If the tree has internal nodes with degrees that are bounded an O(n*log(n] algorithm is possible. It is also shown if the nodes can have unbounded degrees the problem has n2 as lower bound.
Algorithms↗