Search for: All records

Abstract The emergence of viral variants with altered phenotypes is a public health challenge underscoring the need for advanced evolutionary forecasting methods. Given extensive epistatic interactions within viral genomes and known viral evolutionary history, efficient genomic surveillance necessitates early detection of emerging viral haplotypes rather than commonly targeted single mutations. Haplotype inference, however, is a significantly more challenging problem precluding the use of traditional approaches. Here, using SARS-CoV-2 evolutionary dynamics as a case study, we show that emerging haplotypes with altered transmissibility can be linked to dense communities in coordinated substitution networks, which become discernible significantly earlier than the haplotypes become prevalent. From these insights, we develop a computational framework for inference of viral variants and validate it by successful early detection of known SARS-CoV-2 strains. Our methodology offers greater scalability than phylogenetic lineage tracing and can be applied to any rapidly evolving pathogen with adequate genomic surveillance data. 

Over the past two decades, the study of self-similarity and fractality in discrete structures, particularly complex networks, has gained momentum. This surge of interest is fueled by the theoretical developments within the theory of complex networks and the practical demands of real-world applications. Nonetheless, translating the principles of fractal geometry from the domain of general topology, dealing with continuous or infinite objects, to finite structures in a mathematically rigorous way poses a formidable challenge. In this paper, we overview such a theory that allows to identify and analyze fractal networks through the innate methodologies of graph theory and combinatorics. It establishes the direct graph-theoretical analogs of topological (Lebesgue) and fractal (Hausdorff) dimensions in a way that naturally links them to combinatorial parameters that have been studied within the realm of graph theory for decades. This allows to demonstrate that the self-similarity in networks is defined by the patterns of intersection among densely connected network communities. Moreover, the theory bridges discrete and continuous definitions by demonstrating how the combinatorial characterization of Lebesgue dimension via graph representation by its subsets (subgraphs/communities) extends to general topological spaces. Using this framework, we rigorously define fractal networks and connect their properties with established combinatorial concepts, such as graph colorings and descriptive complexity. The theoretical framework surveyed here sets a foundation for applications to real-life networks and future studies of fractal characteristics of complex networks using combinatorial methods and algorithms.