2
$\begingroup$

I'm a computer scientist teaching algorithms development in the Fall. One of the algorithms we teach is called Edit Distance, and our folklore is that it is used to compare RNA sequences (is this actually true in practice?).

I would like to have students implement the edit distance algorithm and run it on actual SARS-COV-2 sequences, so I'm trying to understand exactly what I get from the GenBank database. I downloaded this one: https://www.ncbi.nlm.nih.gov/nuccore/1798174254

I am looking at the genomic.fna file. So this is apparently the FASTA file format, and the lines that begin with >MN988669.1 ... are comments. I see comments like:

>MN988669.1 Severe acute respiratory syndrome coronavirus 2 isolate 2019-nCoV WHU02, complete genome

Followed by an RNA string. Is this the start of a new sequence for a different coronavirus specimen? So I could have students extract each of these and run edit distance and then produce a dendrogram or something? How do I find more information on where the samples came from? Is this the right file to be using, or should I use the gbff file? And are the PDB files interesting to me at all (I actually do know what PDB files are)?

Also, are there any recommended data sets where we could do something like track mutations in the virus (and see, e.g., that the NYC outbreak originated from Europe and not China)? Are there other useful algorithms / data that might be interesting for students to study in this vein? Specifically interesting to me would be graph-search algorithms, minimum spanning trees, and network flow. Also any NP-complete algorithms that we could run backtracking on. Obviously taking the theoretical study of algorithms to something as currently topical as the coronavirus has pedagogical value.

Thanks

EDIT:

Based on comments below here is what is taking shape.

  1. Have students implement vanilla EditDistance (which there seems to be some disagreement about which algorithms are named what, so let's say insertions and deletions only, which I would call Longest Common Subsequence LCS). Then a variant that also does alignment (i.e. full Levenshtein distance computation, which I would call EditDistance, but Wikipedia calls the Needleman-Wunsch algorithm with a gap penalty of 1), then maybe Needleman-Wunsch with different gap penalties (if someone tells me what would make sense biologically).
  2. Have students implement basic heirarchical clustering / phylogenetic tree generation algorithms a la https://www.ncss.com/wp-content/themes/ncss/pdf/Procedures/NCSS/Hierarchical_Clustering-Dendrograms.pdf.
  3. Have students run their sequence alignment variants and different clustering algorithms on SARS-COV-2 sequences and report on how the choices of parameters in 1 and 2 change the result and therefore potentially the analysis.
  4. Ask some open ended written response questions on what this might mean for society, whether this introduces ethical considerations for an algorithms designer or are they doing just the math, etc.

My learning objectives (as they are now shaping up) are:

  1. Students will understand that just because their algorithm comes with a proof of correctness, it doesn't mean it's the correct algorithm for the job.
  2. Students will understand that different models / parameters to a model result in different outcomes, and thus even computational problems are not purely computational.
  3. Doing theoretical computer science / mathematics is not devoid of ethical considerations.

I would very much appreciate thoughts on the above.

$\endgroup$
6
  • $\begingroup$ Hi John, if I get a bit of time over the weekend I will answer question. My apologies I can't do this right now. $\endgroup$ – M__ Jul 27 '20 at 18:00
  • $\begingroup$ @Michael Thanks! I look forward to it. I'm realizing how awesome it would be to have a good dataset where students could see, e.g. that the NYC cases originated from Europe, but I don't know enough to get this dataset put together myself, I don't think. Going to poke at it this week though. $\endgroup$ – John Jul 27 '20 at 18:45
  • 1
    $\begingroup$ I'm assuming what you downloaded is actually a full RNA genome. It is one of many isolates. You could download the rest and do comparisons across them. You can look at also look directly at the RNA (transcription) or convert it into a different space such as amino acid sequence (translation). Here is an example of what that would look like: reddit $\endgroup$ – story Jul 28 '20 at 9:07
  • 1
    $\begingroup$ Hi John, if you are interested in alignment in general, I would recommend not to take a viral sequence. AFAIK viruses have their own special alignment problems. I think using some eukaryotic gene sequences would do a better job for a class about algorithms. $\endgroup$ – Kamil S Jaron Jul 28 '20 at 21:06
  • $\begingroup$ I think hemoglobin genes are the bio-informatics 101 go-to for such phylogeny/alignment/evolution introductions :) $\endgroup$ – Pallie Jul 29 '20 at 13:51
3
$\begingroup$

Your understanding of FASTA format is about right. The type of basic problem you're eluding to we term "sequence alignment"- edit distance might be okay for teaching but in practise we use other algorithms, e.g. you might be interested in the Needleman–Wunsch or Smith–Waterman algorithms. Richard Durbin et al. wrote a great book that covers these any much more https://www.amazon.com/Biological-Sequence-Analysis-Probabilistic-Proteins/dp/0521629713

Tracking mutations etc. requires more than just alignment though, see "phylogenetics" (i.e. building genetic trees) and "variant calling". Also checkout what the nextstrain team is doing https://nextstrain.org/ncov/global

In general, looking for practical applications for your algorithms is great, but be very careful before drawing any real world conclusions about the coronavirus outbreak from such analyses

$\endgroup$
4
  • $\begingroup$ Thanks! Yes, I certainly wouldn't draw any real conclusions from a basic analysis. I just want students to get a sense of algorithms in the wild, we could even discuss the differences between basic EditDistance and Needleman-Wunsch and Smith-Waterman, and potentially even bring in ethical issues, like asking how choice of algorithm (naive vs. better designed, for example) could have negative societal impacts if used incorrectly... $\endgroup$ – John Jul 28 '20 at 13:16
  • $\begingroup$ And I did not know about those, so thanks for the references :)! $\endgroup$ – John Jul 28 '20 at 13:16
  • $\begingroup$ I just looked at that book and its first procedure (UPGMA) for building phylogenetic trees looks to be about the same as the hierarchical clustering algorithm that I was thinking of having students implement in this project as well. So here's a quick follow up question: I would assume that the choice of tree construction algorithm can have drastic effects on the output tree. How is it that biologists validate which algorithm to use? $\endgroup$ – John Jul 28 '20 at 13:22
  • $\begingroup$ @John Good question re trees. Simulated data might validate an algorithm but it's tricky. A bioinformatian might use a tool that has several models and compare them, e.g. see iqtree.org $\endgroup$ – Chris_Rands Jul 28 '20 at 15:32
1
$\begingroup$

The correct method is laborious and it is better to give the students a ready made tree at GISAID to investigate the dispersion of COVID-19 into Europe.

However, a quick approach to getting to the alignment and drawing a tree is easy and will readily complement your established teaching method. What this will give you is a very different phylogeny from edit distances and you would explain the matrix differences between the approaches. I suspect NCBI use Jukes Cantor distances.

  1. Go to blast.ncbi.nlm.nih.gov
  2. Select nucleotides
  3. Paste "MN988669" and hit return
  4. This will produce 100 hits
  5. On the menu page select the "draw tree option"
  6. This will produce a reasonable nucleotide tree for 100 COVID-19 sequences
  7. Select "neighbor-joining" rather than "minimum evolution" (this is hierarchical clustering geared to towards mutation rate heterogeneity between taxa)
  8. There are various point and click options including "examine alignment"
  9. You can then select "minimum evolution" and see the changes in the tree (and there are changes) - TEACHING OBJECTIVE 1 & 2
  10. If you want to examine COVID-19 from the European perspective then select a European isolate, e.g. French isolates and input this into the blast. However, European isolates are basically Wuhan original.

I have provided an example below, which I "rerooted" and represents the closest 100 to you sequence using collapsed clade format (your students can undo this, to examine the contents of a "collapsed clade"). The tree shows the dispersion of strains from the Wuhan seafood market.

There's lots of flexibility and the students can do everything inside ½ hour easily and this would complement your approach. The advantage of my approach to teaching phylogeny and regardless of what you do and how you do it Blast is central to rapidly obtaining alignment data for students and investigators alike. We use different blast options but blasting through is prerequisite to understand the diversity and clean some information on the population structure.

enter image description here


Also, are there any recommended data sets where we could do something like track mutations in the virus (and see, e.g., that the NYC outbreak originated from Europe and not China)?

Yes there are, today this would be Mesquite available here. In my opinion this is a bit advanced. You can track amino acid mutations, which in my view is easier.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.