reconcILS: A gene tree-species tree reconciliation algorithm that allows for incomplete lineage sorting

Reconciliation algorithms infer the evolutionary history of individual gene trees given a species tree. Many reconciliation algorithms consider only duplication and loss events (and sometimes horizontal transfer), ignoring effects of the coalescent process, including incomplete lineage sorting (ILS). Here, we present a new heuristic algorithm for carrying out reconciliation that accurately accounts for ILS by treating it as a series of nearest neighbor interchange (NNI) events. For discordant branches of the gene tree identified by last common ancestor (LCA) mapping, our algorithm recursively chooses the optimal history by comparing the cost of duplication and loss to the cost of NNI and loss. We demonstrate the accuracy of our new method, which we call reconcILS, using a new simulation engine (dupcoal) that generates gene trees produced by the interaction of duplication, loss, and ILS under the MSC-DL model. Despite being a heuristic method, reconcILS is much more accurate than models that ignore ILS, and at least as accurate or better than leading methods that can model ILS, while also able to handle much larger datasets. We demonstrate the use of reconcILS by applying it to a dataset of 23 primate genomes, highlighting its accuracy compared to standard methods in the presence of large amounts of ILS.