Maximum likelihood of phylogenetic networks

Motivation:Horizontal gene transfer (HGT) is believed tobeubiquitous amongbacteria,andplaysamajor role in their genomediversificationas well as their ability to develop resistance to antibiotics. In light of its evolutionary significanceand implications for humanhealth, developing accurate and efficient methods for detecting and reconstructing HGT is imperative. Results: In this article we provide a new HGT-oriented likelihood framework for many problems that involve phylogeny-based HGT detection and reconstruction. Beside the formulation of various like-lihood criteria, we show that most of these problems are NP-hard, and offer heuristics for efficient and accurate reconstruction of HGT under these criteria. We implemented our heuristics and used them to analyze biological as well as synthetic data. In both cases, our criteria and heuristics exhibited very good performance with respect to identifying the correct number of HGT events as well as inferring their correct location on the species tree. Availability: Implementation of the criteria as well as heuristics and hardnessproofs are available from theauthors upon request.Hardness proofs can also be downloaded a