Phylogenetic reconstruction techniques often produce multiple, competing evolutionary hypotheses. The umbrella term phylogenetic postprocessing encompassesmethods that attempt to reconcile the ambiguity. Three classes of phylogenetic postprocessing results are presented. (1) A sublinear (1 + E) approximation algorithm is derived for computing the familiar Robinson-Foulds (RF) distance [4] between two trees. (2) Standard consensus methods are augmented to take edge weight into consideration. A new consensus method based on edge weights is introduced. (3) A generalized family of metrics on tree space is derived. The metrics can be equipped with sensitivity to edge weights. Two members of the family are the RF metric and the weighted RF metric.

The time complexity of the RF approximation algorithm is logarithmic in the number of trees and completely independent of the size of each tree (save a more expensive, one time, embedding step). This algorithm is easy to implement and should prove particularly useful in clusteringbased phylogenetic postprocessing because tree size is more prohibitive than the number of competing trees in phylogenetic reconstructions of biological datasets (as opposed to simulation-generated datasets).

The remainder of this extended abstract focuses solely on the RF approximation algorithm. The reader is referred to [3] and the poster in this conference for detailed treatment of the other results.