Massive parallelization boosts big Bayesian multidimensional scaling

Many-core algorithms for high-dimensional gradients on phylogenetic trees

MOTIVATION

Advancements in high-throughput genomic sequencing are delivering genomic pathogen data at an unprecedented rate, positioning statistical phylogenetics as a critical tool to monitor infectious diseases globally. This rapid growth spurs the need for efficient inference techniques, such as Hamiltonian Monte Carlo (HMC) in a Bayesian framework, to estimate parameters of these phylogenetic models where the dimensions of the parameters increase with the number of sequences N. HMC requires repeated calculation of the gradient of the data log-likelihood with respect to (wrt) all branch-length-specific (BLS) parameters that traditionally takes O(N2) operations using the standard pruning algorithm. A recent study proposes an approach to calculate this gradient in O(N), enabling researchers to take advantage of gradient-based samplers such as HMC. The CPU implementation of this approach makes the calculation of the gradient computationally tractable for nucleotide-based models but falls short in performance for larger state-space size models, such as Markov-modulated and codon models. Here, we describe novel massively parallel algorithms to calculate the gradient of the log-likelihood wrt all BLS parameters that take advantage of graphics processing units (GPUs) and result in many fold higher speedups over previous CPU implementations.

RESULTS

We benchmark these GPU algorithms on three computing systems using three evolutionary inference examples exploring complete genomes from 997 dengue viruses, 62 carnivore mitochondria and 49 yeasts, and observe a >128-fold speedup over the CPU implementation for codon-based models and >8-fold speedup for nucleotide-based models. As a practical demonstration, we also estimate the timing of the first introduction of West Nile virus into the continental Unites States under a codon model with a relaxed molecular clock from 104 full viral genomes, an inference task previously intractable.

AVAILABILITY AND IMPLEMENTATION

We provide an implementation of our GPU algorithms in BEAGLE v4.0.0 (https://github.com/beagle-dev/beagle-lib), an open-source library for statistical phylogenetics that enables parallel calculations on multi-core CPUs and GPUs. We employ a BEAGLE-implementation using the Bayesian phylogenetics framework BEAST (https://github.com/beast-dev/beast-mcmc).

On the surprising effectiveness of a simple matrix exponential derivative approximation, with application to global SARS-CoV-2

The continuous-time Markov chain (CTMC) is the mathematical workhorse of evolutionary biology. Learning CTMC model parameters using modern, gradient-based methods requires the derivative of the matrix exponential evaluated at the CTMC's infinitesimal generator (rate) matrix. Motivated by the derivative's extreme computational complexity as a function of state space cardinality, recent work demonstrates the surprising effectiveness of a naive, first-order approximation for a host of problems in computational biology. In response to this empirical success, we obtain rigorous deterministic and probabilistic bounds for the error accrued by the naive approximation and establish a "blessing of dimensionality" result that is universal for a large class of rate matrices with random entries. Finally, we apply the first-order approximation within surrogate-trajectory Hamiltonian Monte Carlo for the analysis of the early spread of Severe acute respiratory syndrome coronavirus 2 (SARS-CoV-2) across 44 geographic regions that comprise a state space of unprecedented dimensionality for unstructured (flexible) CTMC models within evolutionary biology.

First report of Strongylidae nematode from pilot whale (Globicephala macrorhynchus) by molecular analysis reveals the cosmopolitan distribution of the taxon

This study investigates the identification, genetic composition, and placement in the evolutionary tree of a particular nematode species found in a short-finned pilot whale in the Gulf of Thailand. To accomplish this, we utilized various methods, including microscopic observations, molecular techniques, and comparative analyses to better understand the characteristics of this parasite. Initially, we concentrated on studying the 18s rDNA sequence through nested PCR, resulting in a 774-bp product. After conducting a BLASTn analysis, we discovered that there were only a few sequences in the GeneBank that shared similarities with our nematode, particularly with Cyathostomum catinatum, although the percent identity was relatively low. To confirm the uniqueness of our sequence, we constructed a phylogenetic tree that demonstrated a distinct branch for our nematode, suggesting significant genetic differentiation from C. catinatum. Additionally, we sequenced a 399-bp section of the ITS2 gene using PCR, and the resulting data showed a close association with the Strongylidae family, specifically with Cylicocyclus insigne. This was further confirmed by BLASTn and CD-HIT-est results, which indicated a 99 and ~94% sequence homology with C. insigne, respectively. The ITS2 phylogenetic tree also supported the position of our isolated sequence within the Strongylidae family, clustering closely with C.insigne. Our findings shed light on the genetic connections, taxonomy, and evolutionary trends within the Strongylidae family, with a particular focus on the widespread nature of the Cylicocyclus genus. This study emphasizes the importance of utilizing molecular techniques and interdisciplinary approaches to gain insight into nematode diversity, evolution, and ecological dynamics in marine environments.

The evolutionary history of hepaciviruses

In the search for natural reservoirs of hepatitis C virus (HCV), a broad diversity of non-human viruses within the Hepacivirus genus has been uncovered. However, the evolutionary dynamics that shaped the diversity and timescale of hepaciviruses evolution remain elusive. To gain further insights into the origins and evolution of this genus, we screened a large dataset of wild mammal samples (n = 1,672) from Africa and Asia, and generated 34 full-length hepacivirus genomes. Phylogenetic analysis of these data together with publicly available genomes emphasizes the importance of rodents as hepacivirus hosts and we identify 13 rodent species and 3 rodent genera (in Cricetidae and Muridae families) as novel hosts of hepaciviruses. Through co-phylogenetic analyses, we demonstrate that hepacivirus diversity has been affected by cross-species transmission events against the backdrop of detectable signal of virus-host co-divergence in the deep evolutionary history. Using a Bayesian phylogenetic multidimensional scaling approach, we explore the extent to which host relatedness and geographic distances have structured present-day hepacivirus diversity. Our results provide evidence for a substantial structuring of mammalian hepacivirus diversity by host as well as geography, with a somewhat more irregular diffusion process in geographic space. Finally, using a mechanistic model that accounts for substitution saturation, we provide the first formal estimates of the timescale of hepacivirus evolution and estimate the origin of the genus to be about 22 million years ago. Our results offer a comprehensive overview of the micro- and macroevolutionary processes that have shaped hepacivirus diversity and enhance our understanding of the long-term evolution of the Hepacivirus genus.

A quantum parallel Markov chain Monte Carlo

We propose a novel hybrid quantum computing strategy for parallel MCMC algorithms that generate multiple proposals at each step. This strategy makes the rate-limiting step within parallel MCMC amenable to quantum parallelization by using the Gumbel-max trick to turn the generalized accept-reject step into a discrete optimization problem. When combined with new insights from the parallel MCMC literature, such an approach allows us to embed target density evaluations within a well-known extension of Grover's quantum search algorithm. Letting P d e n o t e t h e n u m b e r o f p r o p o s a l s i n a s i n g l e M C M C i t e r a t i o n , t h e c o m b i n e d s t r a t e g y r e d u c e s t h e n u m b e r o f t a r g e t e v a l u a t i o n s r e q u i r e d f r o m 𝒪 ( P ) t o 𝒪 P 1 / 2 . In the following, we review the rudiments of quantum computing, quantum search and the Gumbel-max trick in order to elucidate their combination for as wide a readership as possible.

Data integration in Bayesian phylogenetics

Researchers studying the evolution of viral pathogens and other organisms increasingly encounter and use large and complex data sets from multiple different sources. Statistical research in Bayesian phylogenetics has risen to this challenge. Researchers use phylogenetics not only to reconstruct the evolutionary history of a group of organisms, but also to understand the processes that guide its evolution and spread through space and time. To this end, it is now the norm to integrate numerous sources of data. For example, epidemiologists studying the spread of a virus through a region incorporate data including genetic sequences (e.g. DNA), time, location (both continuous and discrete) and environmental covariates (e.g. social connectivity between regions) into a coherent statistical model. Evolutionary biologists routinely do the same with genetic sequences, location, time, fossil and modern phenotypes, and ecological covariates. These complex, hierarchical models readily accommodate both discrete and continuous data and have enormous combined discrete/continuous parameter spaces including, at a minimum, phylogenetic tree topologies and branch lengths. The increased size and complexity of these statistical models have spurred advances in computational methods to make them tractable. We discuss both the modeling and computational advances below, as well as unsolved problems and areas of active research.

From viral evolution to spatial contagion: a biologically modulated Hawkes model

SUMMARY

Mutations sometimes increase contagiousness for evolving pathogens. During an epidemic, scientists use viral genome data to infer a shared evolutionary history and connect this history to geographic spread. We propose a model that directly relates a pathogen's evolution to its spatial contagion dynamics-effectively combining the two epidemiological paradigms of phylogenetic inference and self-exciting process modeling-and apply this phylogenetic Hawkes process to a Bayesian analysis of 23 421 viral cases from the 2014 to 2016 Ebola outbreak in West Africa. The proposed model is able to detect individual viruses with significantly elevated rates of spatiotemporal propagation for a subset of 1610 samples that provide genome data. Finally, to facilitate model application in big data settings, we develop massively parallel implementations for the gradient and Hessian of the log-likelihood and apply our high-performance computing framework within an adaptively pre-conditioned Hamiltonian Monte Carlo routine.

SUPPLEMENTARY INFORMATION

Supplementary data are available at Bioinformatics online.

BAYESIAN MITIGATION OF SPATIAL COARSENING FOR A HAWKES MODEL APPLIED TO GUNFIRE, WILDFIRE AND VIRAL CONTAGION

Self-exciting spatiotemporal Hawkes processes have found increasing use in the study of large-scale public health threats, ranging from gun violence and earthquakes to wildfires and viral contagion. Whereas many such applications feature locational uncertainty, that is, the exact spatial positions of individual events are unknown, most Hawkes model analyses to date have ignored spatial coarsening present in the data. Three particular 21st century public health crises-urban gun violence, rural wildfires and global viral spread-present qualitatively and quantitatively varying uncertainty regimes that exhibit: (a) different collective magnitudes of spatial coarsening, (b) uniform and mixed magnitude coarsening, (c) differently shaped uncertainty regions and-less orthodox-(d) locational data distributed within the "wrong" effective space. We explicitly model such uncertainties in a Bayesian manner and jointly infer unknown locations together with all parameters of a reasonably flexible Hawkes model, obtaining results that are practically and statistically distinct from those obtained while ignoring spatial coarsening. This work also features two different secondary contributions: first, to facilitate Bayesian inference of locations and background rate parameters, we make a subtle yet crucial change to an established kernel-based rate model, and second, to facilitate the same Bayesian inference at scale, we develop a massively parallel implementation of the model's log-likelihood gradient with respect to locations and thus avoid its quadratic computational cost in the context of Hamiltonian Monte Carlo. Our examples involve thousands of observations and allow us to demonstrate practicality at moderate scales.

Relax, Keep Walking - A Practical Guide to Continuous Phylogeographic Inference with BEAST

Spatially explicit phylogeographic analyses can be performed with an inference framework that employs relaxed random walks to reconstruct phylogenetic dispersal histories in continuous space. This core model was first implemented 10 years ago and has opened up new opportunities in the field of phylodynamics, allowing researchers to map and analyze the spatial dissemination of rapidly evolving pathogens. We here provide a detailed and step-by-step guide on how to set up, run, and interpret continuous phylogeographic analyses using the programs BEAUti, BEAST, Tracer, and TreeAnnotator.

Scalable Bayesian inference for self-excitatory stochastic processes applied to big American gunfire data

The Hawkes process and its extensions effectively model self-excitatory phenomena including earthquakes, viral pandemics, financial transactions, neural spike trains and the spread of memes through social networks. The usefulness of these stochastic process models within a host of economic sectors and scientific disciplines is undercut by the processes' computational burden: complexity of likelihood evaluations grows quadratically in the number of observations for both the temporal and spatiotemporal Hawkes processes. We show that, with care, one may parallelize these calculations using both central and graphics processing unit implementations to achieve over 100-fold speedups over single-core processing. Using a simple adaptive Metropolis-Hastings scheme, we apply our high-performance computing framework to a Bayesian analysis of big gunshot data generated in Washington D.C. between the years of 2006 and 2019, thereby extending a past analysis of the same data from under 10,000 to over 85,000 observations. To encourage widespread use, we provide hpHawkes, an open-source R package, and discuss high-level implementation and program design for leveraging aspects of computational hardware that become necessary in a big data setting.