1 of 42

UShER:

pandemic-scale phylogenetics for SARS-CoV-2 and beyond

Angie Hinrichs, UCSC

ABPHM ‘23

2 of 42

Outline

A pandemic of genomes
UShER and the UShER SARS-CoV-2 tree
Applications of a mutation-annotated tree
What’s next

3 of 42

How many genomes?

4 of 42

How many genomes?!

5 of 42

How long to build a tree?

6 of 42

Outline

A pandemic of genomes
UShER and the UShER SARS-CoV-2 tree
Applications of a mutation-annotated tree
What’s next

7 of 42

UShER: Ultrafast Sample placement on Existing tRees

>sample_1

ATTAAAGGTTTATACCTTCCCAGGT

AACAAACCAACCAACTTTCGATCTC

TTGTAGATCTGTTCTCTAAACGAAC

TTTAAAATCTGTGTGGCTGTCACTC

…

nextstrain.org, 20 March 2020

8 of 42

UShER: what makes it Ultrafast?

Full MSA → compact binary-encoded Mutation-Annotated Tree

Maximum likelihood estimation → parsimony
Utilize all the CPUs

Turakhia et al. Nature Genetics 2021. https://doi.org/10.1038/s41588-021-00862-7

G3179A, C6982T

C3037T, C14408T, A23403G

T28144C

C8986T

C8782T

C18060T

Yatish Turakhia

UCSC → UCSD

How does it achieve this speed?

First, by using a compact data structure called a mutation-annotated tree. This takes up much less space on disk than a full multiple-sequence alignment file and can be read into memory very quickly.

Secondly, by using a simpler and faster algorithm to choose the best place for a new sequence: parsimony, which looks for the smallest number of mutation events that would explain the observed differences in your sequences.

Thirdly, by maximizing parallelism when searching for the best placement for a sequence, so it can utilize all the CPUs that you can give it.

UShER publication:

Yatish Turakhia, Bryan Thornlow, Angie S. Hinrichs, Nicola De Maio, Landen Gozashti, Robert Lanfear, David Haussler & Russell Corbett-Detig.

Ultrafast Sample placement on Existing tRees (UShER) enables real-time phylogenetics for the SARS-CoV-2 pandemic. Nat Genet 53, 809–816 (2021).

https://doi.org/10.1038/s41588-021-00862-7

https://github.com/yatisht/usher

https://usher-wiki.readthedocs.io/en/latest/

9 of 42

UShER: Ultrafast Sample placement on Existing tRees

Day 1: MSA + tree → Mutation-Annotated Tree (MAT)

G3179A, C6982T

C3037T, C14408T, A23403G

T28144C

C8986T

C8782T

C18060T

G3179A, C6982T

C3037T, C14408T, A23403G

T28144C

C8986T

C8782T

C18060T

A17858G

T26512C

G3179A, C6982T

C3037T, C14408T, A23403G

T28144C

C8986T

C8782T

C18060T

Day N+1: Day N MAT + MSA of only new sequences → new MAT

10 of 42

UShER web interface ~ https://usher.bio/

← Upload sequences

← Paste in names or IDs

or

11 of 42

UShER web interface: view subtree in Nextstrain

Get a Nextstrain subtree view of shared sequences most similar to your sequence

12 of 42

UShER web interface: check proposed Pango lineage

Pango lineage proposals often include an UShER subtree Nextstrain view screenshot

13 of 42

Growing the tree

GISAID

INSDC

COG-UK

CNCB

deduplicate

Yesterday’s

tree

diff

align

filter

optimize

annotate

Today’s

tree

This is an overview of how we’ve been maintaining a more-or-less daily updated tree of all available high-quality SARS-CoV-2 genomes since late January 2021. We pull sequences from GISAID, INSDC (which is the collaboration of GenBank, ENA and DDBJ), COG-UK because they instantly release sequences and metadata, and the China National Center for Bioinformation. Then we deduplicate the sequences, using some scripts written by my UCSC Genome Browser colleague Chris Lee. We figure out which sequences were not already in yesterday’s tree, filter out sequences with too many Ns or other quality issues, align them to the reference, and run UShER on yesterday’s tree and today’s new aligned sequences. Then we filter out excessively long branches and sequences with too many private mutations, run matOptimize which I’ll describe next, annotate Nextstrain clades and Pango lineages on corresponding branches of the tree, and then we have today’s tree for the web interface. We also provide a public-sequence-only (no GISAID) version of the tree for download (https://hgdownload.gi.ucsc.edu/goldenPath/wuhCor1/UShER_SARS-CoV-2/).

Daily update process described in https://doi.org/10.1093/molbev/msab264

Tangle of nested bash scripts starts at https://github.com/ucscGenomeBrowser/kent/blob/master/src/hg/utils/otto/sarscov2phylo/updatePublic.sh

14 of 42

Growing the tree

15 of 42

matOptimize: making an okay tree better

14U

F

6G

4U

7U

9C

2U

10U

A

B

C

D

E

2U

Cheng Ye

UCSD

Yatish Turakhia

UCSD

14U

F

6G

4U

7U

9C

2U

10U

A

B

C

D

E

10U, 14U

Ye et al. Bioinformatics 2022 https://doi.org/10.1093/bioinformatics/btac401

An important part of maintaining a tree that has been incrementally built up by parsimoniously adding sequences is optimization, to retrospectively find cases in which the initial placement wasn’t the best one in light of subsequent new sequences. Yatish Turakhia, now at UC San Diego, and his student Cheng Ye developed matOptimize which rapidly searches a tree with millions of nodes for branch moves that would maximize parsimony.

matOptimize publication:

matOptimize: a parallel tree optimization method enables online phylogenetics for SARS-CoV-2

Cheng Ye, Bryan Thornlow, Angie Hinrichs, Alexander Kramer, Cade Mirchandani, Devika Torvi, Robert Lanfear, Russell Corbett-Detig, Yatish Turakhia

Bioinformatics, Volume 38, Issue 15, August 2022, Pages 3734–3740, https://doi.org/10.1093/bioinformatics/btac401

16 of 42

Online Phylogenomics Databases

A

B

C

D

E

F

A

B

C

D

A

B

C

D

E

F

Addition Optimization

Repeat

Russ Corbett-Detig

UCSC

17 of 42

matUtils: extracting the full value from MATs

Jakob McBroome

UCSC

extract

VCF

Newick

JSON

…

summary

annotate

A

B

introduce

USA/CA → USA/TX

mask

uncertainty

merge

McBroome et al. Mol Biol Evol. 2021 https://doi.org/10.1093/molbev/msab264

18 of 42

Scaling challenges

usher-sampled!

multiple usher jobs on cluster

UShER is much faster than Maximum Likelihood Estimation-based tools, but it can still take a long time to add tens of thousands of genomes to a tree that already has millions of genomes, and there are only 24 hours in a day. If there was some pipeline hiccup or server issue that caused the tree not to be updated for a day or two, that meant that once the pipeline was back up, we would have multiple days’ worth of genomes to add to the tree. Sometimes it would take a few days of extra-long runs before a day with not so many new genomes would let us catch up.

When matUtils merge was added, that let us run multiple usher jobs on a compute cluster and merge the results, instead of running a single job on a big server. As we increased the number of jobs we decreased the time it took to add new sequences – as long as I had the cluster all to myself. Sometimes I didn’t. And then there were the early days of Omicron, when the most sequences were pouring in, around 1 million per month into GISAID. Maintaining the build was getting more difficult and we were just about to move it from the Genome Browser cluster to the cloud, and hope that CDC would be happy to pay thousands of dollars per month in cloud costs.

19 of 42

Scaling challenges

usher-sampled!

Cheng Ye

UCSD

20 of 42

Making Ultrafast even faster

usher-sampled:

Parallelized across samples → reduce redundant traversals
Vector instructions

Cheng Ye

UCSD

21 of 42

Outline

A pandemic of genomes
UShER and the UShER SARS-CoV-2 tree
Applications of a mutation-annotated tree
What’s next

22 of 42

pangolin’s UShER analysis mode

Full tree of ~14.5 million sequences

pangolin-data v1.19

68k consensus sequences

23 of 42

autolin

Information-theoretic identification of candidate lineages
Weight samples by relative representation
Weight mutations by effect

McBroome et al. bioRxiv 2023

https://doi.org/10.1101/2023.02.03.527052

Pango Autolin

Jakob McBroome

UCSC (graduated)

There’s currently a very active team of volunteer SARS-CoV-2 lineage hunters, but we can’t expect that volunteer effort to continue indefinitely and it would be nice to automate as much of the process as possible.

Jakob McBroome recently wrote autolin for automatically finding new candidate Pango lineages. He came up with an information-theoretic measure that encapsulates how well each node of the tree encodes the mutations of all of its descendants, such that the highest-scoring nodes in the tree correspond pretty well to branches that a human might pick out by eye. Here’s a comparison of several manually designated Pangolin lineages, the autolin-proposed lineages on the same branch, and how each of those corresponds to countries. This was using the public-sequence-only tree, so the USA and UK are very overrepresented. To compensate for that, Jakob added a flexible weighting scheme to help prioritize candidate lineages. For example, you can downweight samples from overrepresented countries. You can also weight mutations differently, for example upweighting Spike protein-changing mutations. We expect that different pathogens will need different tweaks for ranking proposed lineages. For SARS-CoV-2, growth rate is another important factor for ranking.

autolin pre-print:

Automated Agnostic Designation of Pathogen Lineages

Jakob McBroome, Adriano de Bernardi Schneider, Cornelius Roemer, Michael T. Wolfinger, Angie S. Hinrichs, Aine Niamh O’Toole, Christopher Ruis, Yatish Turakhia, Andrew Rambaut, Russell Corbett-Detig

doi: https://doi.org/10.1101/2023.02.03.527052

24 of 42

Taxonium viewer – cov2tree.org

Theo Sanderson

Crick Institute

Sanderson. eLife 2022

https://doi.org/10.7554/eLife.82392

25 of 42

Treenome Browser

Alex Kramer

UCSC

Kramer et al. Bioinformatics 2022 https://doi.org/10.1093/bioinformatics/btac772

26 of 42

ClusterTracker ~ https://clustertracker.gi.ucsc.edu/

McBroome et al. Virus Evolution 2022 https://doi.org/10.1093/ve/veac048

Jakob McBroome

UCSC

Jakob McBroome developed the ClusterTracker web tool to make matUtils introduce results more accessible. Click on a state to see a table summarizing clusters in that state with linkouts to the taxonium tree viewer, highlighting the cluster.

The public clustertracker site is based on the public-sequence tree with 6.9 million sequences and shows transmissions between U.S. states, but there is also a firewalled ClusterTracker for the CA DPH that has the full tree plus California sequences that aren’t yet in the public repositories, with integrated access-controlled metadata for epidemiological investigations.

ClusterTracker publication:

Identifying SARS-CoV-2 regional introductions and transmission clusters in real time

Jakob McBroome, Jennifer Martin, Adriano de Bernardi Schneider, Yatish Turakhia, Russell Corbett-Detig

Virus Evolution, Volume 8, Issue 1, 2022, veac048, https://doi.org/10.1093/ve/veac048

27 of 42

RIPPLES

Recombination Inference using Phylogenetic Placements

Yatish Turakhia

UCSD

Turakhia et al. Nature 2022 https://doi.org/10.1038/s41586-022-05189-9

A phylogenetic tree is not really an appropriate structure for recombinants because a recombinant has multiple parents. If a recombinant is forced into a phylogenetic tree structure, it must be placed on or near one of the parent branches, and then it makes a long branch with reversions of the parent’s mutations that it didn’t inherit, plus mutations from the other parent. But those awkward branches actually provide a signal to search for when looking for potential recombinants. Yatish Turakhia and Cheng Ye developed Ripples, which finds those awkward branches and then searches the rest of the tree for the other parent, a branch that would explain those reversions and mutations.

Now, I’ll warn that sequencing errors can also trigger some of these detections, so each potential recombinant should be carefully evaluated. To that end… [next slide]

RIPPLES publication:

Turakhia, Y., Thornlow, B., Hinrichs, A. et al. Pandemic-scale phylogenomics reveals the SARS-CoV-2 recombination landscape. Nature 609, 994–997 (2022). https://doi.org/10.1038/s41586-022-05189-9

28 of 42

RIVET: Recombination Viewer and Tracker

https://rivet.ucsd.edu

Kyle Smith

UCSD

Smith et al. bioRxiv 2023 https://doi.org/10.1101/2023.02.17.529036

29 of 42

Outline

A pandemic of genomes
UShER and the UShER SARS-CoV-2 tree
Applications of a mutation-annotated tree
What’s next

30 of 42

Beyond SARS-CoV-2

Other pathogens:

hMPXV
RSV-A, RSV-B
In the works: influenza, M. tuberculosis

Workflows, cloudification

Mycobacterium spp.

Lily Karim

UCSC

31 of 42

UShER in the future

Support indels, structural variants
Address reference bias with pangenome

Genome 2

Genome 3

Genome 4

Genome 1

Genome 2

Genome 3

Genome 4

Reference

BA.2

Ref

BA.1

BA.2

32 of 42

Acknowledgements

Team UShER (UC Santa Cruz):

Russ Corbett-Detig
Jakob McBroome
Alex Kramer
Bryan Thornlow
Nicolas Ayala
Adriano de Bernardi Schneider
Lily Karim
Koorous Vargha
Jeltje van Baren
Jen Martin
Marc Perry
David Haussler

Funding:

Team UShER (UC San Diego):

Yatish Turakhia
Cheng Ye
Kyle Smith
Sumit Walia
Devika Torvi
Shoh Mollenkamp

ANU: Rob Lanfear

EMBL-EBI Nick Goldman, Nicola de Maio

Crick Inst. Theo Sanderson

Genomes:

Pat & Rowland

Rebele

33 of 42

Thanks!

Questions? Email me:

angie@soe.ucsc.edu

34 of 42

UShER web interface needs Existing tRee

Through Nov. 2020:

Rob Lanfear’s publicly available, regularly updated sarscov2phylo tree of complete high-quality sequences from GISAID

After Nov. 2020:

No more public updates of sarscov2phylo tree.

→ sarscov2phylo + UShER!

35 of 42

Pre-SARS-CoV-2 phylogenomics

Day 1: MSA → tree

36 of 42

Pre-SARS-CoV-2 phylogenomics

Day 1: MSA → tree

Day N+1: Day N tree + MSA → new tree

37 of 42

Outline

A pandemic of genomes
UShER and the UShER SARS-CoV-2 tree
Applications of a mutation-annotated tree
Challenges of sequencing & assembly errors
What’s next

38 of 42

Tree scrambler: false reversions to reference

https://virological.org/t/764

39 of 42

Growing pains: sequencing errors, assembly errors

?!

~20,000 seqs

40 of 42

Bad batch

41 of 42

Bad batch

42 of 42

(Pango)-UShER is More Stable

PangoLEARN

pUShER

Software Release

De Bernardi Schneider. In Prep.

78% Consistent

97% Consistent