Discussion - 1.0 hours
Summary of Course Content
I. Exact matching using the Z and the Boyer-Moore algorithms
II. Suffix trees and linear time algorithms for computing them
III. Applications of suffix trees in pattern matching and computational biology
IV. Inexact matching, edit distance and alignment
V. Accelerations for inexact matching
VI. Additional alignment models for biological applications of inexact matching. Gap questions.
VII. Hybrid dynamic programming -- integrating suffix trees with inexact matching
VIII. Database searching
IX. Applications of string algorithms in DNA sequencing problems
X. String algorithms in phylogenetic reconstruction
The project involves some computer implementation of an important algorithm or the theoretical development of some new method.
D. Gusfield, Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology, Cambridge Press, 1997
Potential Course Overlap
There is no significant overlap with any other course.