Manuel E. Lladser

We address the problem of localizing the source of infection in an undirected, tree-structured network under a susceptible–infected outbreak model. The infection propagates with independent random time increments (i.e., edge-delays) between neighboring nodes, while only the infection times of a subset of nodes can be observed. We show that a reduced set of observers may be sufficient, in the statistical sense, to localize the source and characterize its identifiability via the joint Laplace transform of the observers’ infection times. Using the explicit form of these transforms in terms of the edge-delay probability distributions, we propose scale-invariant estimators of the source. We evaluate their performance on synthetic trees and on a river network, demonstrating accurate localization under diverse edge-delay models.

Haar-like wavelets sparsify the phylogenetic covariance matrices of large, uniformly random k -regular trees with overwhelmingly high probability. This motivates the Haar-like distance, a β -diversity metric that implicitly ranks the splits of a reference phylogeny by their relevance in differentiating two microbial environments, offering an interpretation as to why the environments differ compositionally. Nevertheless, uniform binary trees exhibit statistical features distinct from those of the trees used by practitioners, leaving the extent of sparsification and the practical validity of the implied Haar-like distance speculative. To address this, our manuscript examines the sparsification of phylogenetic covariance matrices of large critical beta-splitting random trees, a model introduced to better reflect real-world phylogenies. By obtaining sharp asymptotic estimates of the first and second moments of the external path length in this ensemble, we demonstrate that the Haar-like basis also pseudo-diagonalizes the phylogenetic covariance matrix of most large trees in this more realistic framework. Additionally, we devise a test to assess the statistical significance of splits in the reference phylogeny identified by the Haar-like distance. We apply the test to a well-studied microbial mat to further substantiate the presumption that the identified splits represent genuine biological signals differentiating the top and bottom layers of the mat.

Despite an ever-expanding number of bacterial taxa being discovered, many of these taxa remain uncharacterized with unknown traits and environmental preferences. This diversity makes it challenging to interpret ecological patterns in microbiomes and understand why individual taxa, or assemblages, may vary across space and time. Although we can use information from the rapidly growing databases of bacterial genomes to infer traits, we still need an approach to organize what we know, or think we know, about bacterial taxa to match taxonomic and phylogenetic information to trait inferences. Inspired by the periodic table of the elements, we have constructed a “periodic table” of bacterial taxa to organize and visualize monophyletic groups of bacteria based on the distributions of key traits predicted from genomic data. By analyzing 50 745 genomes across 31 bacterial phyla, we used the Haar-like wavelet transformation, a model-free transformation of trait data, to identify clades of bacteria which are nearly uniform with respect to six selected traits—oxygen tolerance, autotrophy, chlorophototrophy, maximum potential growth rate, GC content, and genome size. The identified functionally uniform clades of bacteria are presented in a concise periodic table-like format to facilitate identification and exploration of bacterial lineages in trait space. While our approach could be improved and expanded in the future, we demonstrate its utility for integrating phylogenetic information with genome-derived trait values to improve our understanding of the bacterial diversity found in environmental and host-associated microbiomes.

We address the problem of localizing the source of infection in an undirected, tree-structured network under a susceptible-infected outbreak model. The infection propagates with independent random time increments (i.e., edge-delays) between neighboring nodes, while only the infection times of a subset of nodes can be observed. We show that a reduced set of observers may be sufficient, in the statistical sense, to localize the source and characterize its identifiability via the joint Laplace transform of the observers' infection times. Using the explicit form of these transforms in terms of the edge-delay probability distributions, we propose scale-invariant least-squares estimators of the source. We evaluate their performance on synthetic trees and on a river network, demonstrating accurate localization under diverse edge-delay models. To conclude, we highlight overlooked technical challenges for observer-based source localization on networks with cycles, where standard spanning-tree reductions may be ill-posed.

For general non-Gaussian distributions, the covariance and precision matrices do not encode the independence structure of the variables, as they do for the multivariate Gaussian. This paper builds on previous work to show that for a class of non-Gaussian distributions -- those derived from diagonal transformations of a Gaussian -- information about the conditional independence structure can still be inferred from the precision matrix, provided the data meet certain criteria, analogous to the Gaussian case. We call such transformations of the Gaussian as the generalized nonparanormal. The functions that define these transformations are, in a broad sense, arbitrary. We also provide a simple and computationally efficient algorithm that leverages this theory to recover conditional independence structure from the generalized nonparanormal data. The effectiveness of the proposed algorithm is demonstrated via synthetic experiments and applications to real-world data.

Random forests have emerged as a promising tool in comparative metagenomics because they can predict environmental characteristics based on microbial composition in datasets where β-diversity metrics fall short of revealing meaningful relationships between samples. Nevertheless, despite this efficacy, they lack biological insight in tandem with their predictions, potentially hindering scientific advancement. To overcome this limitation, we leverage a geometric characterization of random forests to introduce a data-driven phylogenetic β-diversity metric, the adaptive Haar-like distance. This new metric assigns a weight to each internal node (i.e., split or bifurcation) of a reference phylogeny, indicating the relative importance of that node in discerning environmental samples based on their microbial composition. Alongside this, a weighted nearest-neighbors classifier, constructed using the adaptive metric, can be used as a proxy for the random forest while maintaining accuracy on par with that of the original forest and another state-of-the-art classifier, CoDaCoRe. As shown in datasets from diverse microbial environments, however, the new metric and classifier significantly enhance the biological interpretability and visualization of high-dimensional metagenomic samples.

The metric dimension of a graph is the smallest number of nodes required to identify all other nodes uniquely based on shortest path distances. Applications of metric dimension include discovering the source of a spread in a network, canonically labeling graphs, and embedding symbolic data in low-dimensional Euclidean spaces. This survey gives a self-contained introduction to metric dimension and an overview of the quintessential results and applications. We discuss methods for approximating the metric dimension of general graphs, and specific bounds and asymptotic behavior for deterministic and random families of graphs. We conclude with related concepts and directions for future work.

Random forests have emerged as a promising tool in comparative metagenomics because they can predict environmental characteristics based on microbial composition in datasets where β -diversity metrics fall short of revealing meaningful relationships between samples. Nevertheless, despite this efficacy, they lack biological insight in tandem with their predictions, potentially hindering scientific advancement. To overcome this limitation, we leverage a geometric characterization of random forests to introduce a data-driven phylogenetic β -diversity metric, the adaptive Haar-like distance. This new metric assigns a weight to each internal node (i.e., split or bifurcation) of a reference phylogeny, indicating the relative importance of that node in discerning environmental samples based on their microbial composition. Alongside this, a weighted nearest-neighbors classifier, constructed using the adaptive metric, can be used as a proxy for the random forest while maintaining accuracy on par with that of the original forest and another state-of-the-art classifier, CoDaCoRe. As shown in datasets from diverse microbial environments, however, the new metric and classifier significantly enhance the biological interpretability and visualization of high-dimensional metagenomic samples. Author summary: Traditional phylogenetic β -diversity metrics, particularly weighted and unweighted UniFrac, have had great success in comparing and visualizing high-dimensional metagenomic samples. Nonetheless, these metrics rely upon pre-established biological assumptions that might not capture key microbial players or relationships between some samples. On the contrary, supervised machine learning algorithms, such as random forests, can often capture intricate relationships between microbial samples; however, unveiling these relationships is often challenging due to the intricate inner mechanisms inherent to these algorithms. The adaptive Haar-like distance integrates the merits of β -diversity metrics and random forests, allowing for precise, intuitive, and visual comparison of metagenomic samples, offering valuable scientific insight into the distinctions and associations among microbial environments.

Ultrametric matrices appear in many domains of mathematics and science; nevertheless, they can be large and dense, making them difficult to store and manipulate, unlike large but sparse matrices. In this manuscript, we exploit that ultrametric matrices can be represented as binary trees to sparsify them via an orthonormal base change based on Haar-like wavelets. We show that, with overwhelmingly high probability, only an asymptotically negligible fraction of the off-diagonal entries in random but large ultrametric matrices remain non-zero after the base change; and develop an algorithm to sparsify such matrices directly from their tree representation. We also identify the subclass of matrices diagonalized by the Haar-like wavelets and supply a sufficient condition to approximate the spectrum of ultrametric matrices outside this subclass. Our methods give computational access to a covariance matrix model of the microbiologists’ Tree of Life, which was previously inaccessible due to its size, and motivate introducing a new wavelet-based (beta-diversity) metric to compare microbial environments. Unlike the established metrics, the new metric may be used to identify internal nodes (i.e. splits) in the Tree that link microbial composition and environmental factors in a statistically significant manner.