Visualizing Multilayer Spatiotemporal Epidemiological Data with Animated Geocircles.

OBJECTIVE: The COVID-19 pandemic emphasized the value of geospatial visual analytics for both epidemiologists and the general public. However, systems struggled to encode temporal and geospatial trends of multiple, potentially interacting variables, such as active cases, deaths, and vaccinations. We sought to ask (1) how epidemiologists interact with visual analytics tools, (2) how multiple, time-varying, geospatial variables can be conveyed in a unified view, and (3) how complex spatiotemporal encodings affect utility for both experts and non-experts. MATERIALS AND METHODS: We propose encoding variables with animated, concentric, hollow circles, allowing multiple variables via color encoding and avoiding occlusion problems, and we implement this method in a browser-based tool called CoronaViz. We conduct task-based evaluations with non-experts, as well as in-depth interviews and observational sessions with epidemiologists, covering a range of tools and encodings. RESULTS: Sessions with epidemiologists confirmed the importance of multivariate, spatiotemporal queries and the utility of CoronaViz for answering them, while providing direction for future development. Non-experts tasked with performing spatiotemporal queries unanimously preferred animation to multi-view dashboards. DISCUSSION: We find that conveying complex, multivariate data necessarily involves trade-offs. Yet, our studies suggest the importance of complementary visualization strategies, with our animated multivariate spatiotemporal encoding filling important needs for exploration and presentation. CONCLUSION: CoronaViz's unique ability to convey multiple, time-varying, geospatial variables makes it both a valuable addition to interactive COVID-19 dashboards and a platform for empowering experts and the public during future disease outbreaks. CoronaViz is open-source and a live instance is freely hosted at http://coronaviz.umiacs.io.

Dollo-CDP: a polynomial-time algorithm for the clade-constrained large Dollo parsimony problem.

The last decade of phylogenetics has seen the development of many methods that leverage constraints plus dynamic programming. The goal of this algorithmic technique is to produce a phylogeny that is optimal with respect to some objective function and that lies within a constrained version of tree space. The popular species tree estimation method ASTRAL, for example, returns a tree that (1) maximizes the quartet score computed with respect to the input gene trees and that (2) draws its branches (bipartitions) from the input constraint set. This technique has yet to be used for parsimony problems where the input are binary characters, sometimes with missing values. Here, we introduce the clade-constrained character parsimony problem and present an algorithm that solves this problem for the Dollo criterion score in [Formula: see text] time, where n is the number of leaves, k is the number of characters, and [Formula: see text] is the set of clades used as constraints. Dollo parsimony, which requires traits/mutations to be gained at most once but allows them to be lost any number of times, is widely used for tumor phylogenetics as well as species phylogenetics, for example analyses of low-homoplasy retroelement insertions across the vertebrate tree of life. This motivated us to implement our algorithm in a software package, called Dollo-CDP, and evaluate its utility for analyzing retroelement insertion presence / absence patterns for bats, birds, toothed whales as well as simulated data. Our results show that Dollo-CDP can improve upon heuristic search from a single starting tree, often recovering a better scoring tree. Moreover, Dollo-CDP scales to data sets with much larger numbers of taxa than branch-and-bound while still having an optimality guarantee, albeit a more restricted one. Lastly, we show that our algorithm for Dollo parsimony can easily be adapted to Camin-Sokal parsimony but not Fitch parsimony.

Quartets enable statistically consistent estimation of cell lineage trees under an unbiased error and missingness model.

Cancer progression and treatment can be informed by reconstructing its evolutionary history from tumor cells. Although many methods exist to estimate evolutionary trees (called phylogenies) from molecular sequences, traditional approaches assume the input data are error-free and the output tree is fully resolved. These assumptions are challenged in tumor phylogenetics because single-cell sequencing produces sparse, error-ridden data and because tumors evolve clonally. Here, we study the theoretical utility of methods based on quartets (four-leaf, unrooted phylogenetic trees) in light of these barriers. We consider a popular tumor phylogenetics model, in which mutations arise on a (highly unresolved) tree and then (unbiased) errors and missing values are introduced. Quartets are then implied by mutations present in two cells and absent from two cells. Our main result is that the most probable quartet identifies the unrooted model tree on four cells. This motivates seeking a tree such that the number of quartets shared between it and the input mutations is maximized. We prove an optimal solution to this problem is a consistent estimator of the unrooted cell lineage tree; this guarantee includes the case where the model tree is highly unresolved, with error defined as the number of false negative branches. Lastly, we outline how quartet-based methods might be employed when there are copy number aberrations and other challenges specific to tumor phylogenetics.

Improving quartet graph construction for scalable and accurate species tree estimation from gene trees.

methods are widely used to estimate species trees from genome-scale data. However, they can fail to produce accurate species trees when the input gene trees are highly discordant because of estimation error and biological processes, such as incomplete lineage sorting. Here, we introduce TREE-QMC, a new summary method that offers accuracy and scalability under these challenging scenarios. TREE-QMC builds upon weighted Quartet Max Cut, which takes weighted quartets as input and then constructs a species tree in a divide-and-conquer fashion, at each step forming a graph and seeking its max cut. The wQMC method has been successfully leveraged in the context of species tree estimation by weighting quartets by their frequencies in the gene trees; we improve upon this approach in two ways. First, we address accuracy by normalizing the quartet weights to account for "artificial taxa" introduced during the divide phase so subproblem solutions can be combined during the conquer phase. Second, we address scalability by introducing an algorithm to construct the graph directly from the gene trees; this gives TREE-QMC a time complexity of [Formula: see text], where n is the number of species and k is the number of gene trees, assuming the subproblem decomposition is perfectly balanced. These contributions enable TREE-QMC to be highly competitive in terms of species tree accuracy and empirical runtime with the leading quartet-based methods, even outperforming them on some model conditions explored in our simulation study. We also present the application of these methods to an avian phylogenomics data set.