On Inferring Additive and Replacing Horizontal Gene Transfers Through Phylogenetic Reconciliation

Horizontal gene transfer is one of the most important mechanisms for microbial evolution and adaptation. It is well known that horizontal gene transfer can be either additive or replacing depending on whether the transferred gene adds itself as a new gene in the recipient genome or replaces an existing homologous gene. Yet, all existing phylogenetic techniques for the inference of horizontal gene transfer assume either that all transfers are additive or that all transfers are replacing. This limitation not only affects the applicability and accuracy of these methods but also makes it difficult to distinguish between additive and replacing transfers. Here, we address this important problem by formalizing a phylogenetic reconciliation framework that simultaneously models both additive and replacing transfer events. Specifically, we (1) introduce the DTRL reconciliation framework that explicitly models both additive and replacing transfer events, along with gene duplications and losses, (2) prove that the underlying computational problem is NP-hard, (3) perform the first experimental study to assess the impact of replacing transfer events on the accuracy of the traditional DTL reconciliation model (which assumes that all transfers are additive) and demonstrate that traditional DTL reconciliation remains highly robust to the presence of replacing transfers, (4) propose a simple heuristic algorithm for DTRL reconciliation based on classifying transfer events inferred through DTL reconciliation as being replacing or additive, and (5) evaluate the classification accuracy of the heuristic under a range of evolutionary conditions. Thus, this work lays the methodological and algorithmic foundations for estimating DTRL reconciliations and distinguishing between additive and replacing transfers. An implementation of our heuristic for DTRL reconciliation is freely available open-source as part of the RANGER-DTL software package from https://compbio.engr.uconn.edu/software/ranger-dtl/.