By reconciling the phylogenetic tree of a gene family with the corresponding species tree, it is possible to infer lineage-specific duplications and losses with high confidence and hence to annotate orthologs and paralogs. The currently available reconciliation methods for nonbinary gene trees are computationally expensive for genome-scale applications. We present four O (| G |+| S |) algorithms to reconcile an arbitrary gene tree G with a binary species tree S in the duplication, loss, duploss (also known as mutation), and deep coalescence cost models, where |· | denotes the number of nodes in a tree. The improvement is achieved through two innovations: a linear-time computation of compressed child-image subtrees and efficient reconstruction of irreducible duplication histories. Our technique for child-image subtree compression also results in an order of magnitude speedup in runtime for the dynamic programming and Wagner parsimony--based methods for tree reconciliation in the affine cost model.

In the tree reconciliation approach to infer the duplication history of a gene family, the gene (family) tree is compared to the corresponding species tree. Incomplete lineage sorting (ILS) gives rise to stochastic variation in the topology of a gene tree and hence likely introduces false duplication events when a tree reconciliation method is used. We quantify the effect of ILS on gene duplication inference in a species tree in terms of the expected number of false duplication events inferred from reconciling a random gene tree, which occurs with a probability predicted in coalescent theory, and the species tree. We computationally examine the relationship between the effect of ILS on duplication inference in a species tree and its topological parameters. Our findings suggest that ILS may cause non-negligible bias on duplication inference, particularly on an asymmetric species tree. Hence, when gene duplication is inferred via tree reconciliation or any other approach that takes gene tree topology into account, the ILS-induced bias should be examined cautiously.