Biosequence Algorithms (Spring 2005)

A preliminary syllabus

1. Introduction
   • Overview and Arrangements
   • Basic definitions of strings and sequences
   • Review of molecular sequence data
   • Review of asymptotic complexity measures
2. Exact String Matching
   • Naive, and linear-time pattern matching
   • The Boyer-Moore method
   • Set matching (Aho-Corasick)
   • Seminumerical matching: Shift-And
3. Suffix Trees and their applications
   • Introduction
   • Ukkonen's linear-time construction
   • Applications of suffix trees
4. Approximate Matching, Sequence Alignment, and Sequence Databases
   • String edits and alignments
   • Approximate matching, local alignment, and gaps
   • Introduction to multiple alignments
   • Computing multiple alignments
   • Sequence database searching
5. (Review of the course ?)

To course homepage

Additional information: Pekka Kilpeläinen