ÌÇÐÄVlogÊÓƵ

String Algorithms

Course Number: 02-614

Provides an in-depth look at modern algorithms used to process string data, particularly those relevant to genomics. The course will cover the design and analysis of efficient algorithms for processing enormous amounts of collections of strings. Topics will include string search; inexact matching; string compression; string data structures such as suffix trees, suffix arrays, and searchable compressed indices; and the Borrows-Wheeler transform. Applications of these techniques in genomics will be presented, including genome assembly, transcript assembly, whole-genome alignment, gene expression quantification, read mapping, and search of large sequence databases.

Course Relevance: Graduate students who have interest in algorithm techniques for large-scale string and sequence processing. Graduate students in computational biology.

Key Topics: 

• string search
• inexact matching
• string compression
• string data structures such as suffix trees, suffix arrays, and searchable compressed indices
• the Burrows-Wheeler transform
• locality sensitive hashing
• de Brujin Graphs

Background Knowledge: 

• Equivalent of 15-210 (“Parallel & Sequential Data Structures and Algorithms”) or 150351/15-650/02-613 (“Algorithms & Advanced Data Structures”)
• Equivalent of 15-151 or 21-127
• Programming proficiency

Units: 12
Prerequisite(s): 15127 or 21128 or 15151

Textbook(s):

Learning Resources: 

Autolab, Piazza, Gradescope

Learning Objectives

• Learn various algorithmic techniques and data structures for efficient processing of string data, including suffix trees,
• suffix arrays, Borrows-Wheeler transforms.• Understand the why these algorithms and data structures work.
• Learn to apply and extend these algorithms and data
  structures.
• Learn about the practical application of these techniques,
  especially in genomics
• At the end of this class, you should be familiar with much of the state-of-the-art in algorithms for strings, have familiarity with their use in practice, and have experience applying them to new problems.

Assessment Structure: 

• Homework assignments (35%)
• 2 Midterm exams (15% each)
• Final exam (25%)
• Class participation and quizzes (10%)

Equivalent of 15-210 (“Parallel & Sequential Data Structures and Algorithms”) or 15-351/15-650/02-613 (“Algorithms & Advanced Data Structures”).
Equivalent of 15-151 or 21-127.

Notes: No knowledge of biology assumed