A linear-time majority tree algorithm

Abstract. We give a randomized linear-time algorithm for computing themajorityruleconsensustree.Themajorityruletreeiswidelyused for summarizing a set of phylogenetic trees, which is usually a postprocessing step in constructing a phylogeny. We are implementing the algorithm as part of an interactive visualization system for exploring distributions of trees, where speed is a serious concern for real-time interaction. The linear running time is achieved by using succinct representation of the subtrees and efficient methods for the final tree reconstruction.