Phylogenetic networks that display a tree twice

PhylogeneticGraph (PhyG) a new phylogenetic graph search and optimization program

We present Phylogenetic Graph (PhyG), an open-source, phylogenetic search tool for diverse data types and graphs, including softwired and hardwired networks, in addition to trees. This allows for analysis of horizontal transfer and hybridization scenarios, as well as the necessary vertical inheritance of trees. PhyG is the successor to POY5 in performing combined data tree-alignment with enhancements in heuristic optimality (up to 7% in example data) and execution time (up to a factor of 200). Input data may exhibit a practically unlimited number of character states in qualitative or sequence (aligned and unaligned) types. Novel graph construction and refinement algorithms have been implemented and integrated into a variety of search procedures. Currently, PhyG implements parsimony and No-Common-Mechanism Likelihood optimization.

Parsimony optimization of phylogenetic networks

An algorithm is described for the optimization of character data (e.g. qualitative, nucleic acid sequence) on softwired phylogenetic networks. The algorithm presented here is an extension of those developed for trees under the parsimony criterion and can form the basis for phylogenetic network search procedures. Although the problem is (in general) an NP-Hard optimization, the resolution-based algorithm we describe here capitalizes on the significant amount of shared structure in sub-graphs containing network edges, reducing the execution time and allowing for the analysis of empirical datasets.

Classes of explicit phylogenetic networks and their biological and mathematical significance

The evolutionary relationships among organisms have traditionally been represented using rooted phylogenetic trees. However, due to reticulate processes such as hybridization or lateral gene transfer, evolution cannot always be adequately represented by a phylogenetic tree, and rooted phylogenetic networks that describe such complex processes have been introduced as a generalization of rooted phylogenetic trees. In fact, estimating rooted phylogenetic networks from genomic sequence data and analyzing their structural properties is one of the most important tasks in contemporary phylogenetics. Over the last two decades, several subclasses of rooted phylogenetic networks (characterized by certain structural constraints) have been introduced in the literature, either to model specific biological phenomena or to enable tractable mathematical and computational analyses. In the present manuscript, we provide a thorough review of these network classes, as well as provide a biological interpretation of the structural constraints underlying these networks where possible. In addition, we discuss how imposing structural constraints on the network topology can be used to address the scalability and identifiability challenges faced in the estimation of phylogenetic networks from empirical data.

Comparing and displaying phylogenetic trees using edge union networks

The general problem of representing collections of trees as a single graph has led to many tree summary techniques. Many consensus approaches take sets of trees (either inferred as separate gene trees or gleaned from the posterior of a Bayesian analysis) and produce a single "best" tree. In scenarios where horizontal gene transfer or hybridization are suspected, networks may be preferred, which allow for nodes to have two parents, representing the fusion of lineages. One such construct is the cluster union network (CUN), which is constructed using the union of all clusters in the input trees. The CUN has a number of mathematically desirable properties, but can also present edges not observed in the input trees. In this paper we define a new network construction, the edge union network (EUN), which displays edges if and only if they are contained in the input trees. We also demonstrate that this object can be constructed with polynomial time complexity given arbitrary phylogenetic input trees, and so can be used in conjunction with network analysis techniques for further phylogenetic hypothesis testing.

Phylogenetic network analysis as a parsimony optimization problem

BACKGROUND

Many problems in comparative biology are, or are thought to be, best expressed as phylogenetic "networks" as opposed to trees. In trees, vertices may have only a single parent (ancestor), while networks allow for multiple parent vertices. There are two main interpretive types of networks, "softwired" and "hardwired." The parsimony cost of hardwired networks is based on all changes over all edges, hence must be greater than or equal to the best tree cost contained ("displayed") by the network. This is in contrast to softwired, where each character follows the lowest parsimony cost tree displayed by the network, resulting in costs which are less than or equal to the best display tree. Neither situation is ideal since hard-wired networks are not generally biologically attractive (since individual heritable characters can have more than one parent) and softwired networks can be trivially optimized (containing the best tree for each character). Furthermore, given the alternate cost scenarios of trees and these two flavors of networks, hypothesis testing among these explanatory scenarios is impossible.

RESULTS

A network cost adjustment (penalty) is proposed to allow phylogenetic trees and soft-wired phylogenetic networks to compete equally on a parsimony optimality basis. This cost is demonstrated for several real and simulated datasets. In each case, the favored graph representation (tree or network) matched expectation or simulation scenario.

CONCLUSIONS

The softwired network cost regime proposed here presents a quantitative criterion for an optimality-based search procedure where trees and networks can participate in hypothesis testing simultaneously.

Which Phylogenetic Networks are Merely Trees with Additional Arcs?

A binary phylogenetic network may or may not be obtainable from a tree by the addition of directed edges (arcs) between tree arcs. Here, we establish a precise and easily tested criterion (based on “2-SAT”) that efficiently determines whether or not any given network can be realized in this way. Moreover, the proof provides a polynomial-time algorithm for finding one or more trees (when they exist) on which the network can be based. A number of interesting consequences are presented as corollaries; these lead to some further relevant questions and observations, which we outline in the conclusion.