Phylogenetic trees and algorithms on graphs in virology

Phylogenetic trees – graphs that represent evolutionary histories of biological organisms – play an important role in virology, where they are used to understand the genetic diversity of viruses that circulate in humans and other hosts. For example, during the COVID-19 pandemic, phylogenetic trees were used by WHO and public health agencies to identify variants of concern and trace the emergence of novel SARS-CoV-2 lineages. In this talk, I will discuss a specific computational problem on a phylogenetic tree that helps choose most representative vaccine strains among thousands of sampled viral genomes. This problem can be formulated as a generalized k-medoids problem on a tree and solved optimally in polynomial time. Further, I will discuss why phylogenetic trees do not always accurately capture the evolution of viruses and how can we start moving away from trees to more general graphs. I will introduce “phylogenetic networks” that are directed acyclic graphs. Although many standard problems on phylogenetic trees become NP-hard on phylogenetic networks, I will show new results that help us design effective treewidth-parametrized algorithms on phylogenetic networks.

About Dr. Markin

Dr. Markin is a computational biologist with the USDA Agricultural Research Service. He develops scalable phylogenetic algorithms for inference and analysis of virus evolution. Dr. Markin studies how influenza A viruses evolve to become a pandemic threat and develops approaches to prioritize specific virus strains for vaccine development. Dr. Markin did his PhD in Computer Science at Iowa State University with a focus on phylogenetic algorithms in the genomics era.