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

The limits of phylogenetic analysis: identifying analytical hallucinations

Phylogenetic analysis strives to construct graphs, such as trees or networks, that encapsulate the historical structure of a set of terminal taxa. This process is based on comparative character data and an optimality criterion by which these graphs are evaluated. Whether there is structure in the data or not, phylogenetic analytical methods will produce a collection of heuristically optimal graphs. The question examined here is how to determine when a data set, or components of a data set, possess sufficient shared information to yield results founded in historical phylogenetic structure, and where "hallucinatory" patterns are conjured from a lack of information. A method is described to identify mutually analysable data components based on shared information and to distinguish them from components that cannot be meaningfully analysed.

Phylogenetic minimum description length: an optimality criterion based on algorithmic complexity

Phylogenetic minimum description length (PMDL) is proposed as an optimality criterion for phylogenetic analysis. PMDL is based on algorithmic (Kolmogorov) information and the minimum description length principle. This criterion generates natural weighting functions (i.e. not being externally specified) for a diversity of phylogenetic graph, data and model types. PMDL is a generalized criterion that converges on existing forms of inference (i.e. parsimony, likelihood, Bayesian) in specific circumstances. Furthermore, as opposed to existing criteria, PMDL includes graph complexity allowing for the competition of hypotheses with myriad types of phylogenetic graphs (e.g. trees, networks, forests). Owing to its compound nature, PMDL allows for analytical model choice along with phylogenetic graph hypothesis while avoiding over-parameterization. Although uncomputable, heuristic methods are presented for the calculation of upper bounds on the algorithmic information content of a phylogenetic hypothesis. Examples are presented demonstrating the approach.

Insertions and Deletions: Computational Methods, Evolutionary Dynamics, and Biological Applications

Insertions and deletions constitute the second most important source of natural genomic variation. Insertions and deletions make up to 25% of genomic variants in humans and are involved in complex evolutionary processes including genomic rearrangements, adaptation, and speciation. Recent advances in long-read sequencing technologies allow detailed inference of insertions and deletion variation in species and populations. Yet, despite their importance, evolutionary studies have traditionally ignored or mishandled insertions and deletions due to a lack of comprehensive methodologies and statistical models of insertions and deletion dynamics. Here, we discuss methods for describing insertions and deletion variation and modeling insertions and deletions over evolutionary time. We provide practical advice for tackling insertions and deletions in genomic sequences and illustrate our discussion with examples of insertions and deletion-induced effects in human and other natural populations and their contribution to evolutionary processes. We outline promising directions for future developments in statistical methodologies that would allow researchers to analyze insertions and deletion variation and their effects in large genomic data sets and to incorporate insertions and deletions in evolutionary inference.

PSA: an effective method for predicting horizontal gene transfers through parsimonious phylogenetic networks

Horizontal gene transfer (HGT) from one organism to another, according to some researchers, can be abundant in the evolution of species. A phylogenetic network is a network structure that describes the HGTs among species. Several studies have proposed methods to construct phylogenetic networks to predict HGTs based on parsimony values. Existing definitions of parsimony values for a phylogenetic network are based on the assumption that each gene site or segment evolves independently along different trees in the network. However, in the current study, we define a novel parsimony value, denoted the p definition, for phylogenetic networks, considering that a gene as a whole typically evolves along a tree. Using Simulated Annealing, a new method called the Phylogeny with Simulated Annealing (PSA) algorithm is proposed to search for an optimal network based on the p definition. The PSA method is tested on the simulated data. The results reveal that the parsimonious networks constructed using PSA can better represent the evolutionary relationships of species involving HGTs. Additionally, the HGTs predicted using PSA are more accurate than those predicted using other methods. The PSA algorithm is publicly accessible at http://github.com/imustu/sap.

Multi-armed bandits, Thomson sampling and unsupervised machine learning in phylogenetic graph search

A phylogenetic graph search relies on a large number of highly parameterized search procedures (e.g. branch-swapping, perturbation, simulated annealing, genetic algorithm). These procedures vary in effectiveness over datasets and at alternative points in analytical pipelines. The multi-armed bandit problem is applied to phylogenetic graph searching to more effectively utilize these procedures. Thompson sampling is applied to a collection of search and optimization "bandits" to favour productive search strategies over those that are less successful. This adaptive random sampling strategy is shown to be more effective in producing heuristically optimal phylogenetic graphs and more time efficient than existing uniform probability randomized search strategies. The strategy acts as a form of unsupervised machine learning that can be applied to a diversity of phylogenetic datasets without prior knowledge of their properties.