This course is part of Genomic Data Science Specialization [6 courses] (Johns Hopkins) | Coursera.
It covers the math and practical implementation of algorithms for DNA sequence alignment and assembly.
- Naive Exact Matching: Coding example - Colab notebook to play with
- Boyer-Moore Matching Algorithm: the art of giving up. Coding example - Colab notebook to play with.
- Indexing The Genome - Pattern Matching, Kmer, Sorted List and Hash Table
- Approximate Matching - Hamming and Edit Distance and Pigeonhole Principle
- Edit Distance Calculation - Recursive Edit Distance of Prefixes: calculate edit distance by reducing the problem to smaller sub-problems of edit distance, and calculate recursively.
- Smith-Waterman dynamics programming for calculating edit distance: remembering the answer of the smaller sub-problems to massively reduce repetitive calculations.
Related: Introduction to Genomics is another course within the same pack.