Fundamentals of Stringology
Lecture 1: Fundamentals of Stringology I: Recap on Exact Pattern Matching and Alignment Algorithms
Lecture 2: Fundamentals of Stringology II: Probability and Statistics for Sequence Alignment
Lecture 3: Fundamentals of Stringology III: Suffix Tress and Suffix Arrays
Lecture 4: Fundamentals of Stringology IV: The Burrows-Wheeler Transform
This series of talks is part of the Algorithmic Challenges in Genomics Boot Camp.
Speaker: Dan Gusfield (UC Davis) & Mike Waterman (University of Southern California)
The purpose of these lectures is to give a quick, but rigorous introduction to the most fundamental and general algorithmic techniques that arise in biological sequence analysis, and to review open problems in the probability of sequence alignment. Some specific computer programs or services might be mentioned in passing, but the lectures are not intended to give advice on current computer programs. The topics covered are:
Mini course 1: Linear-time exact pattern matching using the Z-algorithm. Use of k-mers. Dynamic Programming for alignment (both global and local) of two sequences, extension of the biological model to gaps.
Mini course 2: Key open problems in probability and statistics for sequence alignment.
Mini course 3: Suffix trees, suffix arrays and their many uses in genomics, and linear time construction of suffix arrays without building suffix trees.
Mini course 4: The Burrows-Wheeler transform: its relationship to suffix arrays, pattern matching, its modern use in compression and in solving a range of biological sequence problems.