  Horizontal gene transfer inference approaches are usually based on gene
sequences: parametric methods search for patterns that deviate from a
particular genomic signature, while phylogenetic methods use sequences to
reconstruct the gene and species trees. However, it is well-known that
sequences have difficulty identifying ancient transfers since mutations have
enough time to erase all evidence of such events. In this work, we ask whether
character-based methods can predict gene transfers. Their advantage over
sequences is that homologous genes can have low DNA similarity, but still have
retained enough important common motifs that allow them to have common
character traits, for instance the same functional or expression profile. A
phylogeny that has two separate clades that acquired the same character
independently might indicate the presence of a transfer even in the absence of
sequence similarity. We introduce perfect transfer networks, which are
phylogenetic networks that can explain the character diversity of a set of taxa
under the assumption that characters have unique births, and that once a
character is gained it is rarely lost. Examples of such traits include
transposable elements, biochemical markers and emergence of organelles, just to
name a few. We study the differences between our model and two similar models:
perfect phylogenetic networks and ancestral recombination networks. Our goals
are to initiate a study on the structural and algorithmic properties of perfect
transfer networks. We then show that in polynomial time, one can decide whether
a given network is a valid explanation for a set of taxa, and show how, for a
given tree, one can add transfer edges to it so that it explains a set of taxa.
We finally provide lower and upper bounds on the number of transfers required
to explain a set of taxa, in the worst case.
