Pavel Skums

Motivation: In this study, we investigate the application of Semidefinite Programming (SDP) to phylogenetics. SDP is a powerful optimization framework that seeks to optimize a linear objective function over the cone of positive semidefinite matrices. As a convex optimization problem, SDP generalizes linear programming and provides relaxations for many combinatorial optimization problems. However, despite its many applications, SDP remains largely unused in computational biology. Results: We show how SDP relaxations can be designed and used for phylogenetic inference. We consider the Balanced Minimum Evolution (BME) problem, a widely used model in distance-based phylogenetics, and introduce an algorithm that combines an SDP relaxation with a rounding scheme that iteratively converts relaxed solutions into valid tree topologies. Experiments on simulated and empirical datasets show that the method enables accurate phylogenetic reconstruction. Availability and Implementation: The code and data are available at https://github.com/compbel/SDPTree (DOI 10.5281/zenodo.20838318).

Wastewater-based genomic surveillance (WWGS) has proven effective for monitoring SARS-CoV-2 and other viruses within communities. It enables rapid detectio

This study utilized a clustering-based approach to investigate whether countries with similar COVID-19 dynamics also share similar public health and selected sociodemographic factors. The pairwise distances between 42 European countries for six characteristics were calculated, including COVID-19 incidence, mortality, vaccination, SARS-CoV-2 genetic diversity, cross-country mobility and sociodemographic data. Hierarchical clustering trees were constructed, and the strengths of association between the pairs of trees were quantified using cophenetic correlation and Baker’s Gamma correlation measures. The analysis revealed distinct patterns of agreement between clusterings. Vaccination clusterings showed moderate agreement with incidence but no strong agreement with mortality. Mortality-based clustering only agreed with population health clustering. Incidence-based clustering aligned with population health, genetic diversity and selected sociodemographic parameters. Genetic diversity clusterings agreed with mobility and related sociodemographic characteristics. The utility of the cluster-based methods for the time-series is illustrated, and these findings provide insights into the underlying mechanisms driving epidemiological disparities across localities and subpopulations.

Viral infections and cancers are driven by evolution of populations of highly mutable genomic variants. A key evolutionary process in these populations is their migration or spread via transmission or metastasis. Understanding this process is crucial for research, clinical practice, and public health, yet tracing spread pathways is challenging. Phylogenetics offers the main methodological framework for this problem, with challenges including determining the conditions when a phylogenetic tree reflects the underlying migration tree structure, and balancing computational efficiency, flexibility, and biological realism. We tackle these challenges using the powerful machinery of graph homomorphisms, a mathematical concept describing how one graph can be mapped onto another while preserving its structure. We focus on metastatic migrations and viral host-to-host transmissions in outbreak settings. We investigate how structural constraints on migration patterns influence the relationship between phylogenetic and migration trees and propose algorithms to evaluate trees consistency under varying conditions. Leveraging our findings, we introduce a framework for inferring transmission/migration trees by sampling potential solutions from a prior random tree distribution and identifying a subsample consistent with a given phylogeny. By varying the prior distribution, this approach generalizes several existing models, offering a versatile strategy applicable in diverse settings.

This paper presents the first systematic molecular epidemiology study of the HIV epidemic in Belarus, an Eastern European country that, like much of Eastern Europe and including the Post-Soviet region, has been largely understudied in relation to HIV epidemics. HIV sequences collected nationwide between January 2018 and May 2022 were analyzed using phylogenetic and phylodynamic methods. The findings reveal two distinct epidemic waves spanning 1997–2005 and 2009–2018, each driven by different dominant modes of transmission. The study also identifies potential introductions and intra-country transmission routes, emphasizing the pivotal role of the capital city and eastern industrial hubs within Belarus in shaping the epidemic’s trajectory. This work addresses an important gap in understanding HIV dynamics in Eastern Europe.

The 2022–2023 mpox outbreak exhibited an uneven global distribution. While countries such as the UK, Brazil, and the USA were most heavily affected in 2022, many Asian countries, specifically China, Japan, South Korea, and Thailand, experienced the outbreak later, in 2023, with significantly fewer reported cases relative to their populations. This variation in timing and scale distinguishes the outbreaks in these Asian countries from those in the first wave. This study evaluates the predictability of mpox outbreaks with smaller case counts in Asian countries using popular epidemic forecasting methods, including the ARIMA, Prophet, GLM, GAM, n-Sub-epidemic, and Sub-epidemic Wave frameworks. Despite the fact that the ARIMA and GAM models performed well for certain countries and prediction windows, their results were generally inconsistent and highly dependent on the country, i.e., the dataset, as well as the prediction interval length. In contrast, n-Sub-epidemic Ensembles demonstrated more reliable and robust performance across different datasets and predictions, indicating the effectiveness of this model on small datasets and its utility in the early stages of future pandemics.

Many human diseases, including viral infections and cancers, are driven by the evolutionary dynamics of heterogeneous populations of genomic variants. A major type of evolutionary behavior of these populations is migration including viral transmissions and cancer metastatic spread. A common strategy for migration pathways reconstruction involves constructing a phylogenetic tree of observed genotypes and inferring its ancestral states corresponding to migration sites. Key challenges here include determining the conditions when a phylogenetic tree topology reflects the underlying migration tree structure, and balancing computational tractability, flexibility, and biological realism of inference algorithms and models. In this study, we address these challenges using the powerful machinery of graph homomorphisms, a mathematical concept that describes how one graph can be mapped onto another while preserving its structure. We investigate how structural constraints on migration patterns and migration tree topologies influence the relationship between phylogenies and migration trees, characterize trees compatible with a given phylogeny and propose a series of algorithms to assess whether given phylogenetic and migration trees are compatible under various migration scenarios. Leveraging our findings, we present a framework for inferring migration trees by sampling potential trees from a prior random tree distribution and identifying a subsample compatible with a given phylogeny. By varying prior tree distributions, this approach expands upon several existing models, offering a versatile strategy applicable to a variety of biological processes. We validate our methodology using simulated datasets and real data from studies of viral outbreaks and cancer metastasis, demonstrating its effectiveness across different contexts.