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.

Comprehensive Species Sampling and Sophisticated Algorithmic Approaches Refute the Monophyly of Arachnida.

Deciphering the evolutionary relationships of Chelicerata (arachnids, horseshoe crabs, and allied taxa) has proven notoriously difficult, due to their ancient rapid radiation and the incidence of elevated evolutionary rates in several lineages. Although conflicting hypotheses prevail in morphological and molecular data sets alike, the monophyly of Arachnida is nearly universally accepted, despite historical lack of support in molecular data sets. Some phylotranscriptomic analyses have recovered arachnid monophyly, but these did not sample all living orders, whereas analyses including all orders have failed to recover Arachnida. To understand this conflict, we assembled a data set of 506 high-quality genomes and transcriptomes, sampling all living orders of Chelicerata with high occupancy and rigorous approaches to orthology inference. Our analyses consistently recovered the nested placement of horseshoe crabs within a paraphyletic Arachnida. This result was insensitive to variation in evolutionary rates of genes, complexity of the substitution models, and alternative algorithmic approaches to species tree inference. Investigation of sources of systematic bias showed that genes and sites that recover arachnid monophyly are enriched in noise and exhibit low information content. To test the impact of morphological data, we generated a 514-taxon morphological data matrix of extant and fossil Chelicerata, analyzed in tandem with the molecular matrix. Combined analyses recovered the clade Merostomata (the marine orders Xiphosura, Eurypterida, and Chasmataspidida), but merostomates appeared nested within Arachnida. Our results suggest that morphological convergence resulting from adaptations to life in terrestrial habitats has driven the historical perception of arachnid monophyly, paralleling the history of numerous other invertebrate terrestrial groups.

Much ado about nothing: inapplicable data as insertion-deletion events.

The treatment of inapplicable characters has proved especially vexing to systematists. Investigators have wrestled with alternative coding scenarios to capture both the presence and absence of a feature, and its variation when present, in a reasonable manner. Three basic issues have presented themselves: (i) impossible states at internal nodes; (ii) action at a distance among disparate parts of the tree; and (iii) "secondary" (i.e. aspect variation) characters overwhelming "primary" (i.e. character presence/absence) patterns in grouping taxa. Multiple methods have been proposed to deal with these issues in the context of standard character coding with varying levels of complexity. Here, I show that these issues can be dealt with in a direct fashion by treating presence/absence not as a character, but as insertion/deletion of a character with all its potential variation. This approach removes these three problems in simple, straightforward manner.

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.

Phylogenomic Resolution of Sea Spider Diversification through Integration of Multiple Data Classes.

Despite significant advances in invertebrate phylogenomics over the past decade, the higher-level phylogeny of Pycnogonida (sea spiders) remains elusive. Due to the inaccessibility of some small-bodied lineages, few phylogenetic studies have sampled all sea spider families. Previous efforts based on a handful of genes have yielded unstable tree topologies. Here, we inferred the relationships of 89 sea spider species using targeted capture of the mitochondrial genome, 56 conserved exons, 101 ultraconserved elements, and 3 nuclear ribosomal genes. We inferred molecular divergence times by integrating morphological data for fossil species to calibrate 15 nodes in the arthropod tree of life. This integration of data classes resolved the basal topology of sea spiders with high support. The enigmatic family Austrodecidae was resolved as the sister group to the remaining Pycnogonida and the small-bodied family Rhynchothoracidae as the sister group of the robust-bodied family Pycnogonidae. Molecular divergence time estimation recovered a basal divergence of crown group sea spiders in the Ordovician. Comparison of diversification dynamics with other marine invertebrate taxa that originated in the Paleozoic suggests that sea spiders and some crustacean groups exhibit resilience to mass extinction episodes, relative to mollusk and echinoderm lineages.

Phylogenetic supergraphs.

Phylogenetic graph structures used in empirical and theoretical analysis have expanded beyond trees to more general directed acyclic graphs including networks and forests. Several methods to reconcile multiple such graphs are presented and discussed here, extending existing consensus and supertree techniques to form a set of phylogenetic supergraph methods. These graphs can be used as the summary of analytical results, or as heuristic initial graphs for further phylogenetic analysis.

Phylogenetic relationships of the Boana pulchella Group (Anura: Hylidae).

In this paper we present a phylogenetic analysis of the treefrogs of the Boana pulchella Group with the goals of (1) providing a rigorous test of its monophyly; (2) providing a test of relationships supported in previous studies; and (3) exploring the relationships of the several species not included in previous analyses. The analyses included>300 specimens of 37 of the 38 species currently included in the group, plus 36 outgroups, exemplars of the diversity of Boana and the other genera of the hylid tribe Cophomantini. The dataset included eight mitochondrial genes (12S, 16S, CytB, COI, ND1, tRNAIle, tRNALeu, and tRNAVal) and five nuclear genes (RHO, TYR, RAG-1, CXCR4, SIAH1). The phylogenetic analyses recover the monophyly of the B. pulchella Group with lower support than previous studies, as a result of the inclusion of the B. claresignata Group, which is recovered as its sister taxon. Within the B. pulchella Group, the inclusion of almost all species of the group had little impact on previous notions of its phylogeny, except for the rejection of the hypothesized B. polytaenia Clade (B. goiana and B. phaeopleura are nested in the clade here called the B. prasina Clade), which is redefined. Phylogenetic support is strong for five major clades, which collectively include all but three of the species sampled: the B. balzani Clade (B. aguilari, B. balzani, B. gladiator, B. melanopleura, B. palaestes), the redefined B. polytaenia Clade (B. botumirim, B. buriti, B. cipoensis, B. jaguariaivensis, B. leptolineata, B. polytaenia, B. stenocephala, and two undescribed species), the B. prasina Clade (B. bischoffi, B. caingua, B. cordobae, B. goiana, B. guentheri, B. marginata, B. phaeopleura, B. prasina, B. pulchella, and one undescribed species), the B. riojana Clade (B. callipleura, B. marianitae, B. riojana), and the B. semiguttata Clade (B. caipora, B. curupi, B. joaquini, B. poaju, B. semiguttata, B. stellae, and two undescribed species). The monophyly of the B. prasina + B. riojana Clades, and that of the B. polytaenia + B. semiguttata Clades are well-supported. The relationships among these two clades, the B. balzani Clade, B. ericae + B. freicanecae, and B. cambui (representing the deepest phylogenetic splits within the B. pulchella Group) are recovered with weak support. We discuss the phenotypic evidence supporting the monophyly of the B. pulchella Group, and the taxonomy of several species, identifying three new synonyms of Boana polytaenia, one new synonym of Boana goiana, and one new synonym of B. riojana.

Statistical Modeling of Distribution Patterns: A Markov Random Field Implementation and Its Application on Areas of Endemism.

A statistical framework to infer areas of endemism from geographic distributions is proposed. This novel method is based on hidden Markov random fields (HMRFs), a type of undirected graph model commonly used in computer vision. This framework assumes areas of endemism are the states of the hidden layer of the model, whereas taxon distributions are emitted values in the observed layer. Taxon distributions are associated to the observed layer through a clustering procedure based on the extent of overlap. Observations are emitted by the hidden layer according to a Gaussian distribution, whereas the joint distribution of the hidden layer follows a Potts model. State and parameter inference of the maximum a posteriori configuration is performed through a modified version of the expectation-maximization algorithm. The optimal number of areas of endemism in the data set is estimated through the pseudolikelihood information criterion, a model selection procedure that uses an approximation to likelihood. The performance of the new algorithm was assessed on simulated data, and compared with the most popular methods for delimitation of areas of endemism: biotic element analysis, parsimony analysis of endemism, and endemicity analysis. HMRFs efficiently recovered the true pattern across a wide range of uncertainty values. The performance was also examined on empirical data: South African weevils (Sciobius) and Central American ground beetles and funnel-web tarantulas (Carabidae and Dipluridae, respectively). HMRFs uncovered six areas of endemism from the weevil data set, whereas eight were estimated for the Central American arthropods (compared with 3-5 and 3-14 from the other methods, respectively).

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.

The phylogeny of Dendropsophini (Anura: Hylidae: Hylinae).

The relationships of the hyline tribe Dendropsophini remain poorly studied, with most published analyses dealing with few of the species groups of Dendropsophus. In order to test the monophyly of Dendropsophini, its genera, and the species groups currently recognized in Dendropsophus, we performed a total evidence phylogenetic analysis. The molecular dataset included sequences of three mitochondrial and five nuclear genes from 210 terminals, including 12 outgroup species, the two species of Xenohyla, and 93 of the 108 recognized species of Dendropsophus. The phenomic dataset includes 46 terminals, one per species (34 Dendropsophus, one Xenohyla, and 11 outgroup species). Our results corroborate the monophyly of Dendropsophini and the reciprocal monophyly of Dendropsophus and Xenohyla. Some species groups of Dendropsophus are paraphyletic (the D. microcephalus, D. minimus, and D. parviceps groups, and the D. rubicundulus clade). On the basis of our results, we recognize nine species groups; for three of them (D. leucophyllatus, D. microcephalus, and D. parviceps groups) we recognize some nominal clades to highlight specific morphology or relationships and facilitate species taxonomy. We further discuss the evolution of oviposition site selection, where our results show multiple instances of independent evolution of terrestrial egg clutches during the evolutionary history of Dendropsophus.

Efficient implied alignment.

BACKGROUND: Given a binary tree [Formula: see text] of n leaves, each leaf labeled by a string of length at most k, and a binary string alignment function ⊗, an implied alignment can be generated to describe the alignment of a dynamic homology for [Formula: see text]. This is done by first decorating each node of [Formula: see text] with an alignment context using ⊗, in a post-order traversal, then, during a subsequent pre-order traversal, inferring on which edges insertion and deletion events occurred using those internal node decorations. RESULTS: Previous descriptions of the implied alignment algorithm suggest a technique of "back-propagation" with time complexity [Formula: see text]. Here we describe an implied alignment algorithm with complexity [Formula: see text]. For well-behaved data, such as molecular sequences, the runtime approaches the best-case complexity of Ω(k∗n). CONCLUSIONS: The reduction in the time complexity of the algorithm dramatically improves both its utility in generating multiple sequence alignments and its heuristic utility.

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.

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.

Revisiting habitat and lifestyle transitions in Heteroptera (Insecta: Hemiptera): insights from a combined morphological and molecular phylogeny.

Heteroptera, the true bugs, are part of the largest clade of non-holometabolous insects, the Hemiptera, and include > 42 000 described species in about 90 families. Despite progress in resolving phylogenetic relationships between and within infraorders since the first combined morphological and molecular analysis published in 1993 (29 taxa, 669 bp, 31 morphological characters), recent hypotheses have relied entirely on molecular data. Weakly supported nodes along the backbone of Heteroptera made these published phylogenies unsuitable for investigations into the evolution of habitats and lifestyles across true bugs. Here we present the first combined morphological and molecular analyses of Heteroptera since 1993, using 135 taxa in 60 families, 4018 aligned bp of ribosomal DNA and 81 morphological characters, and various analytical approaches. The sister-group relationship of the predominantly aquatic Nepomorpha with all remaining Heteroptera is supported in all analyses, and a clade formed by Enicocephalomorpha, Dipsocoromorpha and Gerromorpha in some. All analyses recover Leptopodomorpha + (Cimicomorpha + Pentatomomorpha), mostly with high support. Parsimony- and likelihood-based ancestral state reconstructions of habitats and lifestyles on the combined likelihood phylogeny provide new insights into the evolution of true bugs. The results indicate that aquatic and semi-aquatic true bugs invaded these habitats three times independently from terrestrial habitats in contrast to a recent hypothesis. They further suggest that the most recent common ancestor of Heteroptera was predacious, and that the two large predominantly phytophagous clades (Trichophora and Miroidea) are likely to have derived independently from predatory ancestors. We conclude that by combining morphological and molecular data and employing various analytical methods our analyses have converged on a relatively well-supported hypothesis of heteropteran infraordinal relationships that now requires further testing using phylogenomic and more extensive morphological datasets.

Revising the Bantu tree.

Phylogenetic methods offer a promising advance for the historical study of language and cultural relationships. Applications to date, however, have been hampered by traditional approaches dependent on unfalsifiable authority statements: in this regard, historical linguistics remains in a similar position to evolutionary biology prior to the cladistic revolution. Influential phylogenetic studies of Bantu languages over the last two decades, which provide the foundation for multiple analyses of Bantu sociocultural histories, are a major case in point. Comparative analyses of basic lexica, instead of directly treating written words, use only numerical symbols that express non-replicable authority opinion about underlying relationships. Building on a previous study of Uto-Aztecan, here we analyse Bantu language relationships with methods deriving from DNA sequence optimization algorithms, treating basic vocabulary as sequences of sounds. This yields finer-grained results that indicate major revisions to the Bantu tree, and enables more robust inferences about the history of Bantu language expansion and/or migration throughout sub-Saharan Africa. "Early-split" versus "late-split" hypotheses for East and West Bantu are tested, and overall results are compared to trees based on numerical reductions of vocabulary data. Reconstruction of language histories is more empirically based and robust than with previous methods.

Expression and function of spineless orthologs correlate with distal deutocerebral appendage morphology across Arthropoda.

The deutocerebral (second) head segment is putatively homologous across Arthropoda, in spite of remarkable disparity of form and function of deutocerebral appendages. In Mandibulata this segment bears a pair of sensory antennae, whereas in Chelicerata the same segment bears a pair of feeding appendages called chelicerae. Part of the evidence for the homology of deutocerebral appendages is the conserved function of homothorax (hth), which has been shown to specify antennal or cheliceral fate in the absence of Hox signaling, in both mandibulate and chelicerate exemplars. However, the genetic basis for the morphological disparity of antenna and chelicera is not understood. To test whether downstream targets of hth have diverged in a lineage-specific manner, we examined the evolution of the function and expression of spineless (ss), which in two holometabolous insects is known to act as a hth target and distal antennal determinant. Toward expanding phylogenetic representation of gene expression data, here we show that strong expression of ss is observed in developing antennae of a hemimetabolous insect, a centipede, and an amphipod crustacean. By contrast, ss orthologs are not expressed throughout the cheliceral limb buds of spiders or harvestmen during developmental stages when appendage fate is specified. RNA interference-mediated knockdown of ss in Oncopeltus fasciatus, which bears a simple plesiomorphic antenna, resulted in homeotic distal antenna-to-leg transformation, comparable to data from holometabolous insect counterparts. Knockdown of hth in Oncopeltus fasciatus abrogated ss expression, suggesting conservation of upstream regulation. These data suggest that ss may be a flagellar (distal antennal) determinant more broadly, and that this function was acquired at the base of Mandibulata.

Taxon cycle predictions supported by model-based inference in Indo-Pacific trap-jaw ants (Hymenoptera: Formicidae: Odontomachus).

Nonequilibrium dynamics and non-neutral processes, such as trait-dependent dispersal, are often missing from quantitative island biogeography models despite their potential explanatory value. One of the most influential nonequilibrium models is the taxon cycle, but it has been difficult to test its validity as a general biogeographical framework. Here, we test predictions of the taxon cycle model using six expected phylogenetic patterns and a time-calibrated phylogeny of Indo-Pacific Odontomachus (Hymenoptera: Formicidae: Ponerinae), one of the ant genera that E.O. Wilson used when first proposing the hypothesis. We used model-based inference and a newly developed trait-dependent dispersal model to jointly estimate ancestral biogeography, ecology (habitat preferences for forest interiors, vs. "marginal" habitats, such as savannahs, shorelines, disturbed areas) and the linkage between ecology and dispersal rates. We found strong evidence that habitat shifts from forest interior to open and disturbed habitats increased macroevolutionary dispersal rate. In addition, lineages occupying open and disturbed habitats can give rise to both island endemics re-occupying only forest interiors and taxa that re-expand geographical ranges. The phylogenetic predictions outlined in this study can be used in future work to evaluate the relative weights of neutral (e.g., geographical distance and area) and non-neutral (e.g., trait-dependent dispersal) processes in historical biogeography and community ecology.

There is no evidence that Podoctidae carry eggs of their own species: Reply to Machado and Wolff (2017).

In our recent publication (Sharma et al., 2017), we tested the hypothesis that eggs attached to the legs of male Podoctidae (Opiliones, Laniatores) constituted a case of paternal care, using molecular sequence data in tandem with multiple sequence alignments to test the prediction that sequences of the eggs and the adults that carried them would indicate conspecific identity. We discovered that the sequences of the eggs belonged to spiders, and thus rejected the paternal care hypothesis for these species. Machado and Wolff (2017) recently critiqued our work, which they regarded as a non-critical interpretation and over-reliance on molecular sequence data, and defended the traditional argument that the eggs attached to podoctids are in fact harvestman eggs. Here we show that additional molecular sequence data also refute the identity of the eggs as conspecific harvestman eggs, using molecular cloning techniques to rule out contamination. We show that individual gene trees consistently and reliably place the egg and adult sequences in disparate parts of the tree topology. Phylogenetic methods consistently place all egg sequences within the order Araneae (spiders). We submit that evidence for the paternal care hypothesis based on behavioral, morphological, and natural history approaches is either absent or insufficient for concluding that the eggs of podoctids are conspecific.

Nomenclatural stability does not justify recognition of paraphyletic taxa: A response to Scherz et al. (2016).

Peloso et al. (2015: PELOSO) published a comprehensive phylogenetic study of the frog family Microhylidae, which resulted in the discovery that several taxa were not monophyletic. To remedy this, a series of nomenclatural changes were proposed (several generic synonymies and two new subfamilies named). A recent study published in this journal by Scherz et al. (2016: SCHERZ), provided a novel phylogeny for the Malagasy subfamily Cophylinae. SCHERZ dispute the analyses and taxonomic conclusions of PELOSO. Their study is, however, based on substantial reduction of data from the PELOSO study, limited addition of new data, and different analytical methods. In spite of the fact that their own results are consistent with the taxonomy of PELOSO, SCHERZ reject that conservative taxonomy and suggest the revalidation of Platypelis (from the synonymy of Cophyla), the revalidation of Stumpffia (from the synonymies of Rhombophryne), and the creation of at least two new genera (only one named therein). In doing so, SCHERZ accept the recognition of likely paraphyletic taxa, with Stumpffia paraphyletic in their parsimony analysis. Herein, we provide a response to several points raised in SCHERZ: (1) we discuss issues with their interpretation (and selective use) of available phylogenetic and phenotypic evidence; (2) and provide a new phylogenetic analysis of all the data in PELOSO and SCHERZ combined. In the new analysis Stumpffia is paraphyletic with respect to Rhombophryne, whereas Cophyla and Platypelis are both monophyletic and sister taxa. We provide a case for the use of the taxonomy suggested in PELOSO.