Revising the Bantu tree

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.

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.

Demonstrating environmental impacts on the sound structure of languages: challenges and solutions

Recent research has suggested that there are significant associations between aspects of the phonological properties of languages and the locations in which they are spoken. In this paper we outline a strategy for assembling maximally reliable and well documented climatic and environmental data to place in juxtaposition with carefully curated linguistic information on both language location and structure. Problems with temperature records are specifically highlighted as an illustration of the use of the platform and considerations when selecting environmental data for analytic use. Preliminary analyses suggest that certain previously proposed language-environment relationships are statistically valid, but that these may be better placed in a broader framework of language types.

Phylogeographic analysis of the Bantu language expansion supports a rainforest route

Southern Africa has been shaped by the large-scale expansion of Bantu populations fueled by agriculture: Currently, 240 million people speak one of the more than 500 Bantu languages. However, the timing and geographic routes undergone by the Bantu populations remain largely unknown. We use cutting-edge phylogeographic techniques to show that Bantu populations migrated through the Central African tropical rainforest around 4,400 y ago. This adds to the growing evidence that agricultural expansions can successfully overcome ecological challenges as they unfold.

The Bantu expansion transformed the linguistic, economic, and cultural composition of sub-Saharan Africa. However, the exact dates and routes taken by the ancestors of the speakers of the more than 500 current Bantu languages remain uncertain. Here, we use the recently developed “break-away” geographical diffusion model, specially designed for modeling migrations, with “augmented” geographic information, to reconstruct the Bantu language family expansion. This Bayesian phylogeographic approach with augmented geographical data provides a powerful way of linking linguistic, archaeological, and genetic data to test hypotheses about large language family expansions. We compare four hypotheses: an early major split north of the rainforest; a migration through the Sangha River Interval corridor around 2,500 BP; a coastal migration around 4,000 BP; and a migration through the rainforest before the corridor opening, at 4,000 BP. Our results produce a topology and timeline for the Bantu language family, which supports the hypothesis of an expansion through Central African tropical forests at 4,420 BP (4,040 to 5,000 95% highest posterior density interval), well before the Sangha River Interval was open.

Distance Wagner tree refinement as a heuristic approach to character-based initial tree construction

The distance Wagner procedure of Farris (American Naturalist, 1972, 106, 645), in its original or random addition sequence form, is a rapid method of tree construction. The original formulation did not allow for refinement of tree hypotheses via common trajectory search operations (e.g. SPR, TBR). Here, the distance Wagner method is extended to allow for refinement of initial trees produced via the four-point condition (Mathematics and the Archeological and Historical Sciences, Edinburgh University Press, Edinburgh, 1974). The performance of the extended distance Wagner as a heuristic search procedure is evaluated with several unaligned sequences and combined source datasets within the parsimony framework. Distance Wagner both with and without refinement is shown to be a rapid and useful heuristic method to generate initial trees for further, character-based, analysis.

FASTC: a file format for multi-character sequence data

Here, we define a sequence file format that allows for multi-character elements (FASTC). The format is derived from the FASTA format and the custom alphabet format of POY4/5. The format is more general than either of these formats and can represent a broad variety of sequence-type data. This format should be useful for analyses involving datasets encoded as linear streams such as gene synteny, comparative linguistics, temporal gene expression and development, complex animal behaviours, and general biological time-series data.