Reconciliation of a gene network and species tree.

The phylogenetic trees of genes and the species which they belong to are similar, but distinct due to various evolutionary processes which affect genes but do not create new species. Reconciliations map the gene tree into the species tree, explaining the discrepancies by events including gene duplications and losses. However, when duplicate genes undergo recombination (a phenomenon known as paralog exchange, or non-allelic homologous recombination), the phylogeny of the genes becomes a network, not a tree. In this paper, we explore how to reconcile a gene network to a species tree with duplications and losses. We propose an extension of the lowest common ancestor (LCA) mapping which solves the problem for tree-child gene networks, show that a restricted version of the problem is polynomial-time solvable and bounds the optimal position of each gene node in the full problem, and show that the full problem is fixed-parameter tractable in the level of the gene network. This provides a formal foundation for the development of efficient algorithms to solve this problem.