Algorithmic Strategies for Estimating the Amount of Reticulation From a Collection of Gene Trees

H. J. Park, G. Jin, L. Nakhleh*

Department of Computer Science, Rice University, 6100 Main Street, Houston, TX 77005, USA. nakhleh@cs.rice.edu

Proc LSS Comput Syst Bioinform Conf. August, 2010. Vol. 9, p. 114-123. Full-Text PDF

*To whom correspondence should be addressed.

Phylogenetic networks have emerged as a unifying evolutionary model of both vertical and horizontal inheritance. A major approach for reconstructing such networks is to reconcile gene trees that are reconstructed from various genomic regions. The Subtree Prune and Regraft (SPR) operation has been used to obtain lower bound estimates of the number of reticulation events from a pair of trees. However, more than two trees are available in general and, to date, no work exists on estimating the amount of reticulation by the SPR operation from a collection, not only a pair, of trees. In this paper we address this problem, and propose two algorithmic strategies for heuristically solving it. The first is based on a simple, yet novel, observation on the binomial distribution of pairwise distances of trees inside a network. The second is based on the aggregation of solutions from pairwise computations. We have implemented both approaches and studied their performance in extensive simulations. The methods produce good results in general in terms of estimating the minimum number of reticulation events required to reconcile a set of trees. In addition, we identify conditions under which the methods do not work as well, in an attempt to help in the development of new methods in this area.