Estimating rates of SARS-CoV-2 lineage spread from graph theory analysis and data mining of genetic sequence data streams

The modern enormous scale of viral genomic data, as exemplified by SARS-CoV-2, presents unique opportunities for epidemic inference and real-time monitoring. Existing methods, however, cannot efficiently process the extremely large stream of sequence data and simultaneously identify small subsets of sequences that may represent rapid population growth of newly emerged lineages. To address this gap, we developed a new approach that combines techniques in traditional graph theory and modern data mining. We represent small subsets of sequences as graph Laplacians and identify from them features of rapid population growth. From early sequence data collected in the US and the UK between 2021 and mid-2022, we identified two features—genetic diversity and matrix connectivity—that allow us to reliably estimate growth rates of newly emerged lineages. To test our model, we used data collected from mid-2022 and end-2024 and accurately predicted the growth rates of lineages that appeared during this period. Furthermore, for data collected in 2023 when the sequencing efforts were relatively high (thousands of sequences per day) in the US and the UK, our model correctly identified the most rapidly expanding lineages when they were still at low frequencies (between 1-6%). Overall, our work provides a scalable and adaptable tool to estimate the growth rate of newly emerged SARS-CoV-2 lineages. More broadly, the interpretable logic of our method suggests potential for rapid outbreak identification for other rapidly evolving pathogens.