An optimal algorithm to reconstruct trees from additive distance data
JJ Hein - Bulletin of mathematical biology, 1989 - Elsevier
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 (n 2)
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 n 2 as lower bound.
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 (n 2)
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 n 2 as lower bound.