Search

The standard models of sequence evolution on a tree determine probabilities for every character or site pattern. A flattening is an arrangement of these probabilities into a matrix, with rows corresponding to all possible site patterns for one set $A$ of taxa and columns corresponding to all site patterns for another set $B$ of taxa. Flattenings have been used to prove difficult results relating to phylogenetic invariants and consistency and also form the basis of several methods of phylogenetic inference. We prove that the rank of the flattening equals $r^{\ell_T(A|B)}$, where $r$ is the number of states and $\ell_T(A|B)$ is the parsimony length of the binary character separating $A$ and $B$. This result corrects an earlier published formula and opens up new applications for old parsimony theorems. Since completing this work, we have learnt that an equivalent result has been proved much earlier by Casanellas and Fern\'andez-S\'anchez, using a different proof strategy.

The generalized circumradius of a set of points $A \subseteq \mathbb{R}^d$ with respect to a convex body $K$ equals the minimum value of $\lambda \geq 0$ such that $A$ is contained in a translate of $\lambda K$. Each choice of $K$ gives a different function on the set of bounded subsets of $\mathbb{R}^d$; we characterize which functions can arise in this way. Our characterization draws on the theory of diversities, a recently introduced generalization of metrics from functions on pairs to functions on finite subsets. We additionally investigate functions which arise by restricting the generalised circumradius to a finite subset of $\mathbb{R}^d$. We obtain elegant characterizations in the case that $K$ is a simplex or parallelotope., Comment: To be published in Discrete and Computational Geometry

Computational inference of dated evolutionary histories relies upon various hypotheses about RNA, DNA, and protein sequence mutation rates. Using mutation rates to infer these dated histories is referred to as molecular clock assumption. Coalescent theory is a popular class of evolutionary models that implements the molecular clock hypothesis to facilitate computational inference of dated phylogenies. Cancer and virus evolution are two areas where these methods are particularly important. Methodologically, phylogenetic inference methods require a tree space over which the inference is performed, and geometry of this space plays an important role in statistical and computational aspects of tree inference algorithms. It has recently been shown that molecular clock, and hence coalescent, trees possess a unique geometry, different from that of classical phylogenetic tree spaces which do not model mutation rates. Here we introduce and study a space of discrete coalescent trees, that is, we assume that time is discrete, which is inevitable in many computational formalisations. We establish several geometrical properties of the space and show how these properties impact various algorithms used in phylogenetic analyses. Our tree space is a discretisation of a known time tree space, called t-space, and hence our results can be used to approximate solutions to various open problems in t-space. Our tree space is also a generalisation of another known trees space, called the ranked nearest neighbour interchange space, hence our advances in this paper imply new and generalise existing results about ranked trees.

Diversities are a generalization of metric spaces, where instead of the non-negative function being defined on pairs of points, it is defined on arbitrary finite sets of points. Diversities have a well-developed theory. This includes the concept of a diversity tight span that extends the metric tight span in a natural way. Here we explore the generalization of diversities to lattices. Instead of defining diversities on finite subsets of a set we consider diversities defined on members of an arbitrary lattice (with a 0). We show that many of the basic properties of diversities continue to hold. However, the natural map from a lattice diversity to its tight span is not a lattice homomorphism, preventing the development of a complete tight span theory as in the metric and diversity cases., Comment: 18 pages, 4 figures

Hidden Markov models (HMMs) are general purpose models for time-series data widely used across the sciences because of their flexibility and elegance. However fitting HMMs can often be computationally demanding and time consuming, particularly when the the number of hidden states is large or the Markov chain itself is long. Here we introduce a new Graphical Processing Unit (GPU) based algorithm designed to fit long chain HMMs, applying our approach to an HMM for nonvolcanic tremor events developed by Wang et al.(2018). Even on a modest GPU, our implementation resulted in a 1000-fold increase in speed over the standard single processor algorithm, allowing a full Bayesian inference of uncertainty related to model parameters. Similar improvements would be expected for HMM models given large number of observations and moderate state spaces (<80 states with current hardware). We discuss the model, general GPU architecture and algorithms and report performance of the method on a tremor dataset from the Shikoku region, Japan.

We describe a new and computationally efficient Bayesian methodology for inferring species trees and demographics from unlinked binary markers. Likelihood calculations are carried out using diffusion models of allele frequency dynamics combined with a new algorithm for numerically computing likelihoods of quantitative traits. The diffusion approach allows for analysis of datasets containing hundreds or thousands of individuals. The method, which we call \snapper, has been implemented as part of the Beast2 package. We introduce the models, the efficient algorithms, and report performance of \snapper on simulated data sets and on SNP data from rattlesnakes and freshwater turtles.

The general theory developed by Ben Yaacov for metric structures provides Fra\"iss\'e limits which are approximately ultrahomogeneous. We show here that this result can be strengthened in the case of relational metric structures. We give an extra condition that guarantees exact ultrahomogenous limits. The condition is quite general. We apply it to stochastic processes, the class of diversities, and its subclass of $L_1$ diversities., Comment: 22 pages

We define a set inner product to be a function on pairs of convex bodies which is symmetric, Minkowski linear in each dimension, positive definite, and satisfies the natural analogue of the Cauchy-Schwartz inequality (which is not implied by the other conditions). We show that any set inner product can be embedded into an inner product space on the associated support functions, thereby extending fundamental results of Hormander and Radstrom. The set inner product provides a geometry on the space of convex bodies. We explore some of the properties of that geometry, and discuss an application of these ideas to the reconstruction of ancestral ecological niches in evolutionary biology.

The Minimal Ancestral Deviation (MAD) method is a recently introduced procedure for estimating the root of a phylogenetic tree, based only on the shape and branch lengths of the tree. The method is loosely derived from the midpoint rooting method, but, unlike its predecessor, makes use of all pairs of OTUs when positioning the root. In this note we establish properties of this method and then describe a fast and memory efficient algorithm. As a proof of principle, we use our algorithm to determine the MAD roots for simulated phylogenies with up to 100,000 OTUs. The calculations take a few minutes on a standard laptop.

Tree comparison metrics have proven to be an invaluable aide in the reconstruction and analysis of phylogenetic (evolutionary) trees. The path-length distance between trees is a particularly attractive measure as it reflects differences in tree shape as well as differences between branch lengths. The distance equals the sum, over all pairs of taxa, of the squared differences between the lengths of the unique path connecting them in each tree. We describe an $O(n \log n)$ time for computing this distance, making extensive use of tree decomposition techniques introduced by Brodal et al. (2004).

Diversities are a generalization of metric spaces in which a non-negative value is assigned to all finite subsets of a set, rather than just to pairs of points. Here we provide an analogue of the theory of negative type metrics for diversities. We introduce negative type diversities, and show that, as in the metric space case, they are a generalization of $L_1$-embeddable diversities. We provide a number of characterizations of negative type diversities, including a geometric characterisation. Much of the recent interest in negative type metrics stems from the connections between metric embeddings and approximation algorithms. We extend some of this work into the diversity setting, showing that lower bounds for embeddings of negative type metrics into $L_1$ can be extended to diversities by using recently established extremal results on hypergraphs.

In the case of a linear state space model, we implement an MCMC sampler with two phases. In the learning phase, a self-tuning sampler is used to learn the parameter mean and covariance structure. In the estimation phase, the parameter mean and covariance structure informs the proposed mechanism and is also used in a delayed-acceptance algorithm. Information on the resulting state of the system is given by a Gaussian mixture. In on-line mode, the algorithm is adaptive and uses a sliding window approach to accelerate sampling speed and to maintain appropriate acceptance rates. We apply the algorithm to joined state and parameter estimation in the case of irregularly sampled GPS time series data., Comment: adaptive MCMC method application. need further work

Smoothing splines can be thought of as the posterior mean of a Gaussian process regression in a certain limit. By constructing a reproducing kernel Hilbert space with an appropriate inner product, the Bayesian form of the V-spline is derived when the penalty term is a fixed constant instead of a function. An extension to the usual generalized cross-validation formula is utilized to find the optimal V-spline parameters., Comment: a draft. not peer-reviewed yet

Trajectory reconstruction is the process of inferring the path of a moving object between successive observations. In this paper, we propose a smoothing spline -- which we name the V-spline -- that incorporates position and velocity information and a penalty term that controls acceleration. We introduce a particular adaptive V-spline designed to control the impact of irregularly sampled observations and noisy velocity measurements. A cross-validation scheme for estimating the V-spline parameters is given and we detail the performance of the V-spline on four particularly challenging test datasets. Finally, an application of the V-spline to vehicle trajectory reconstruction in two dimensions is given, in which the penalty term is allowed to further depend on known operational characteristics of the vehicle., Comment: 25 pages, submitted

We state an open problem in the theory of diversities: what is the worst case minimal distortion embedding of a diversity on $n$ points in $\ell_1$. This problem is the diversity analogue of a famous problem in metric geometry: what is the worst case minimal distortion embedding of an $n$-point metric space in $\ell_1$. We explain the problem, state some special classes of diversities for which the answer is known, and show why the standard techniques from the metric space case do not work. We then outline some possible lines of attack for the problem that are not yet fully explored.

Consensus methods are widely used for combining phylogenetic trees into a single estimate of the evolutionary tree for a group of species. As more taxa are added, the new source trees may begin to tell a different evolutionary story when restricted to the original set of taxa. However, if the new trees, restricted to the original set of taxa, were to agree exactly with the earlier trees, then we might hope that their consensus would either agree with or resolve the original consensus tree. In this paper, we ask under what conditions consensus methods exist that are 'future proof' in this sense. While we show that some methods (e.g. Adams consensus) have this property for specific types of input, we also establish a rather surprising `no-go' theorem: there is no 'reasonable' consensus method that satisfies the future-proofing property in general. We then investigate a second notion of 'future proofing' for consensus methods, in which trees (rather than taxa) are added, and establish some positive and negative results. We end with some questions for future work., Comment: 15 pages, 5 figures

Diversities are like metric spaces, except that every finite subset, instead of just every pair of points, is assigned a value. Just as there is a theory of minimal distortion embeddings of finite metric spaces into $L_1$, there is a similar, yet undeveloped, theory for embedding finite diversities into the diversity analogue of $L_1$ spaces. In the metric case, it is well known that an $n$-point metric space can be embedded into $L_1$ with $\mathcal{O}(\log n)$ distortion. For diversities, the optimal distortion is unknown. Here, we establish the surprising result that symmetric diversities, those in which the diversity (value) assigned to a set depends only on its cardinality, can be embedded in $L_1$ with constant distortion., Comment: 14 pages, 3 figures

We present an efficient and flexible method for computing likelihoods of phenotypic traits on a phylogeny. The method does not resort to Monte-Carlo computation but instead blends Felsenstein's discrete character pruning algorithm with methods for numerical quadrature. It is not limited to Gaussian models and adapts readily to model uncertainty in the observed trait values. We demonstrate the framework by developing efficient algorithms for likelihood calculation and ancestral state reconstruction under Wright's threshold model, applying our methods to a dataset of trait data for extrafloral nectaries (EFNs) across a phylogeny of 839 Labales species., Comment: 23 pages, 3 figures