From Small Parsimony to Horizontal Gene Transfer: Inferring Horizontal Transfer and Gene Loss for Single-Origin Characters

Abstract

The simple underlying pattern of presence–absence of a character within a species tree provides useful steps to trace complex evolutionary histories. Character-based models such as perfect transfer networks and its galled variant aim to leverage this information to predict horizontal gene transfers. Under the assumption that characters have a single origin, are rarely lost, and can be transferred horizontally, they remain an efficient inference method for almost tree-like scenarios. Nevertheless, they can sometimes predict overly complicated scenarios, and its simplest structural variants are too restrictive for practical uses. With the goal of extending this model to include loss events, we present a Sankoff–Rousseau-like algorithm that aims to recover the simplest possible scenarios that combine gene transfers and losses using solely the single character information already contained in a given species tree. We establish a link between the small parsimony problem and the inference of scenarios with a minimum number of losses and transfers, allowing losses and transfers to have a user-defined penalization for this end. We also explore the utility of our model for tracing possible highways of gene transfers by presenting a real case study on a dataset of bacterial species and Kyoto Encyclopedia of Genes and Genome functions as characters.