Reconciliation with Non-binary Gene Trees Revisited

By reconciling the phylogenetic tree of a gene family with the corresponding species tree, it is possible to infer lineage-specic duplications and losses with high condence and hence annotate orthologs and paralogs. However, the currently available reconciliation methods for non-binary gene trees are too computationally expensive to be applied on a genomic level. Here, we present an O(m+ n) algorithm to reconcile an arbitrary gene tree with its corresponding species tree, where m and n are the number of nodes in the gene and species trees respectively. The improve-ment is achieved through two innovations: a fast computation of compressed child-image subtrees, and ecient reconstruction of irreducible dupli-cation histories. This method will be a valuable tool to genome-wide studies of the evolution of individual gene families.