  Reconciling gene trees with a species tree is a fundamental problem to
understand the evolution of gene families. Many existing approaches reconcile
each gene tree independently. However, it is well-known that the evolution of
gene families is interconnected. In this paper, we extend a previous approach
to reconcile a set of gene trees with a species tree based on segmental
macro-evolutionary events, where segmental duplication events and losses are
associated with cost $\delta$ and $\lambda$, respectively. We show that the
problem is polynomial-time solvable when $\delta \leq \lambda$ (via
LCA-mapping), while if $\delta > \lambda$ the problem is NP-hard, even when
$\lambda = 0$ and a single gene tree is given, solving a long standing open
problem on the complexity of the reconciliation problem. On the positive side,
we give a fixed-parameter algorithm for the problem, where the parameters are
$\delta/\lambda$ and the number $d$ of segmental duplications, of time
complexity $O(\lceil \frac{\delta}{\lambda} \rceil^{d} \cdot n \cdot
\frac{\delta}{\lambda})$. Finally, we demonstrate the usefulness of this
algorithm on two previously studied real datasets: we first show that our
method can be used to confirm or refute hypothetical segmental duplications on
a set of 16 eukaryotes, then show how we can detect whole genome duplications
in yeast genomes.
