WEBVTT Kind: captions Language: en 00:00:00.720 --> 00:00:05.680 Cool. Thank you. So hopefully people see  my slides. So yeah I'm Niema Moshiri. I'm   00:00:05.680 --> 00:00:09.040 at UC San Diego. I'm in the Computer  Science and Engineering Department   00:00:09.040 --> 00:00:12.960 and I'll be talking about a recent  development that we've made called viral MSA. 00:00:14.880 --> 00:00:18.880 Basically a standard phylogenetics workflow-  if you've ever seen an evolutionary history of   00:00:18.880 --> 00:00:23.440 virus sequences, you kind of- you start with  these initial sequences at the beginning that   00:00:23.440 --> 00:00:28.160 don't necessarily line up very nicely. And  the first step is you do multiple sequence   00:00:28.160 --> 00:00:33.200 alignment to get them to line up. Lining  them up like this tells us stuff about,   00:00:33.200 --> 00:00:36.880 you know, what is the sequence homology, what  are the relationships between the sequences.  00:00:37.840 --> 00:00:41.040 Using this alignment, you  then estimate a phylogeny.   00:00:42.000 --> 00:00:44.960 And then you root the phylogeny to  determine what is the common ancestor.   00:00:45.520 --> 00:00:48.480 And then there's a bunch of other downstream  analyses that you might be interested in doing,   00:00:48.480 --> 00:00:54.160 you know, things like what are the  clusters of outbreaks that are happening   00:00:54.160 --> 00:01:01.280 you know what demographics do we think are more  at risk of getting infected by some disease? Yeah,   00:01:01.280 --> 00:01:06.240 a lot of stuff that you can do. So in general  my focus is on these two steps: the multiple   00:01:06.240 --> 00:01:10.000 sequence alignment and the phylogenetic inference  which are really the computational bottlenecks.   00:01:10.880 --> 00:01:14.880 And in this talk, I'll be focusing just on  this single step: multiple sequence alignment. 00:01:15.680 --> 00:01:20.880 So the multiple sequence alignment problem is  NP-Complete, which, TLDR, that means we don't   00:01:20.880 --> 00:01:27.280 have a polynomial time solution, and as a result,  many heuristics have been developed to approximate   00:01:27.280 --> 00:01:32.880 solutions. They're pretty accurate reasonably.  Some of the tools that people might be familiar   00:01:32.880 --> 00:01:37.360 with are MUSCLE, ClustalOmega, and MAFFT. These  are some of the common tools that implement them.   00:01:38.240 --> 00:01:42.480 However, even these heuristics generally  scale quadratically with respect to the number   00:01:42.480 --> 00:01:47.920 of sequences. So in the case of SARS-CoV-2,  we've had an exponential growth of sequencing   00:01:49.120 --> 00:01:54.640 happening where, I mean, this is a great thing for  us. We're getting more and more sequence data, but   00:01:54.640 --> 00:01:58.880 the downside is we have to analyze those sequence  data and our tools just don't scale properly.   00:02:00.240 --> 00:02:04.240 So right now- so this is actually outdated.  This was from I think a week or two ago. Now   00:02:04.240 --> 00:02:11.760 we're almost at 200,000 sequences. So the tools  just do not scale to enable real-time analysis. 00:02:14.080 --> 00:02:19.920 So, what if instead, we knew in advance so a  priori we knew that our sequences are going   00:02:19.920 --> 00:02:26.960 to be super similar and we already have some high  confidence representative reference genome against   00:02:26.960 --> 00:02:32.080 which we can compare them to? So here, I'm showing  the reference genome as a green line on the top   00:02:32.080 --> 00:02:36.240 and each of those other colored sequences below  it are the sequence that I want to align with   00:02:36.240 --> 00:02:41.040 each other. Instead of aligning them amongst  themselves, what I can do is just align the first   00:02:41.040 --> 00:02:45.600 sequence against the reference genome. Align the  second sequence against the reference genome. Keep   00:02:45.600 --> 00:02:49.840 aligning each of the sequences independently  directly against the reference genome.   00:02:50.720 --> 00:02:55.600 And then using the positions of the reference  genome as anchors, I can merge the individual   00:02:55.600 --> 00:03:00.400 pairwise alignments into one multiple  sequence line. So take the first column   00:03:00.400 --> 00:03:05.280 of my multiple sequence assignment see- in the  first sequence this is the position that matched,   00:03:05.280 --> 00:03:09.760 then this position matched in the second, and  the third, and then just collapse them together.   00:03:10.800 --> 00:03:13.840 I can do this for each position of the  reference genome and then now I have   00:03:13.840 --> 00:03:18.480 a multiple sequence line. And the nice thing  is that this parallelizes super nicely. Every   00:03:18.480 --> 00:03:22.560 single sequence can be aligned against the  reference independently and simultaneously,   00:03:23.440 --> 00:03:26.960 and it scales linearly with the number  of sequences rather than quadratically. 00:03:28.400 --> 00:03:32.800 But let me take a step back real quick  and think about this approach. My input   00:03:32.800 --> 00:03:38.000 is a reference genome and a bunch of sequences  that are very similar to that reference genome,   00:03:38.000 --> 00:03:44.640 and my output is an alignment of every sequence  against the reference genome. So if people are   00:03:44.640 --> 00:03:50.240 at all familiar with long read sequencing, this is  exactly the same computational problem as mapping   00:03:50.240 --> 00:03:57.200 long reads to a reference genome. So my question  was: can I leverage existing well-implemented   00:03:57.200 --> 00:04:02.160 read mapping tools to enable this type of scalable  reference guided multiple sequence alignment? 00:04:02.800 --> 00:04:08.800 So I developed a tool called ViralMSA which wraps  around existing read mappers in order to perform   00:04:08.800 --> 00:04:13.120 reference-guided multiple sequence alignment.  I wrap around a few of them, but there's one   00:04:13.120 --> 00:04:20.240 tool specifically, Minimap2, that's kind of the  gold standard right now for what I'm doing. So I   00:04:20.240 --> 00:04:25.360 only recommend using my tool with that specific  read mapper, but I wrap around a few of them to   00:04:25.360 --> 00:04:30.480 demonstrate that I can evolve this tool naturally  as read mapping technologies evolve as well.   00:04:31.840 --> 00:04:37.280 So basically, you simply provide viral MSA  reference genome and the sequences to align and   00:04:37.280 --> 00:04:41.040 then it'll handle indexing the reference genome  and doing any pre-processing it needs to do,   00:04:41.600 --> 00:04:46.480 and it'll call the read mapper and then merge  the results into a multiple sequence alignment. 00:04:46.480 --> 00:04:52.640 And here you can see a comparison of this approach  with existing best practice tools. So my tool is   00:04:52.640 --> 00:04:57.520 the blue line on the bottom and then the two  other lines are other tools and you see that, in   00:04:57.520 --> 00:05:03.040 general, it's multiple orders of magnitude faster  than what people are generally doing right now,   00:05:03.040 --> 00:05:07.680 and it scales very nicely. And the sequence  alignments that we get are very accurate. 00:05:08.720 --> 00:05:12.480 So in conclusion, this tool that I've  developed enables rapid multiple sequence   00:05:12.480 --> 00:05:15.840 alignment of viral genomes. It's  open source. You can get it online,   00:05:16.720 --> 00:05:19.680 and hopefully if you do any  viral analyses consider using it. 00:05:20.240 --> 00:05:22.880 So some acknowledgements:  Heng Li developed Minimap2,   00:05:22.880 --> 00:05:27.120 which is kind of the essence of the speed and  this work was supported by NSF and Google.   00:05:28.240 --> 00:05:32.560 And yeah, I'll leave questions for  the chat or later in the session.