Phylogenetic network is a model for reticulate evolution. Hybridization network is one type of phylogenetic network for a set of discordant gene trees, and "displays" each gene tree. A central computational problem on hybridization networks is: given a set of gene trees, reconstruct the minimum (i.e. most parsimonious) hybridization network that displays each given gene tree. This problem is known to be NP-hard, and existing approaches for this problem are either heuristics or make simplifying assumptions (e.g. work with only two input trees or assume some topological properties). In this paper, we develop an exact algorithm (called PIRNc) for inferring the minimum hybridization networks from multiple gene trees. The PIRNc algorithm does not rely on structural assumptions. To the best of our knowledge, PIRNc is the first exact algorithm for this formulation. When the number of reticulation events is relatively small (say four or fewer), PIRNc runs reasonably efficient even for moderately large datasets. For building more complex networks, we also develop a heuristic version of PIRNc called PIRNch- Simulation shows that PIRNch usually produces networks with fewer reticulation events than those by an existing method.
展开▼
