  When gene copies are sampled from various species, the resulting gene tree
might disagree with the containing species tree. The primary causes of gene
tree and species tree discord include lineage sorting, horizontal gene
transfer, and gene duplication and loss. Each of these events yields a
different parsimony criterion for inferring the (containing) species tree from
gene trees. With lineage sorting, species tree inference is to find the tree
minimizing extra gene lineages that had to coexist along species lineages; with
gene duplication, it becomes to find the tree minimizing gene duplications
and/or losses. In this paper, we show the following results: (i) The deep
coalescence cost is equal to the number of gene losses minus two times the gene
duplication cost in the reconciliation of a uniquely leaf labeled gene tree and
a species tree. The deep coalescence cost can be computed in linear time for
any arbitrary gene tree and species tree. (ii) The deep coalescence cost is
always no less than the gene duplication cost in the reconciliation of an
arbitrary gene tree and a species tree. (iii) Species tree inference by
minimizing deep coalescences is NP-hard.
