CS 481: Bioinformatics Algorithms

Fall 2013

Instructor: Can Alkan

Office hours: Tuesdays and Thursdays 14:00-15:00 in EA-509

TA: Shatlyk Ashyralyev

Office hours: TBA

Class hours: Tue 15:40-17:30; Fri 13:40-15:30
Class room: EB102

NOTE: Some biology, molecular biology, genetics background would help, but not required. Basics regarding the topic will be covered in class.

Prerequisites: Elementary discrete mathematics, basic algorithms and data structures, and programming proficiency with, e.g., C/C++/Java will be expected. Knowledge of elementary combinatorics and probability, fundamental algorithms for sorting, searching, hashing and dynamic programming, elementary graph algorithms would be very helpful.

Textbook: An Introduction to Bioinformatics Algorithms (Computational Molecular Biology), Neil Jones and Pavel Pevzner, MIT Press, 2004

Recommended Material

Biological Sequence Analysis: Probabilistic Models of Proteins and Nucleic Acids, Richard Durbin, Sean R. Eddy, Anders Krogh, Graeme Mitchison, Cambridge University Press

Bioinformatics: The Machine Learning Approach, Second Edition, Pierre Baldi, Soren Brunak, MIT Press

Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology, Dan Gusfield, Cambridge University Press

Grading: There will be one midterm exam (25%) and a final exam (35%). A further 20% of the final grade will be based on homework assignments, and 20% will be based on quizzes.

Course material

Note: Some slides are adapted from http://www.bioalgorithms.info

Lecture slides	Recommended reading
A brief introduction to molecular biology concepts and algorithmic problems in computational biology. Week 1, Lectures 1-2 A brief introduction to computational complexity and algorithm design techniques Week 1, Lecture 3	EBI's Introduction to Biology JGI's Introduction to Genomics Chapter 3 of the textbook Chapter 2 of the text book
DNA mapping & motif search Week 2, Lectures 1-2 Exact sequence search algorithms Week 2, Lecture 3	Chapter 4 of the text book
Rabin-Karp algorithm, finite automata, pattern matching, suffix trees Week 3, Lectures 1-2 Shift-and algorithm, Aho-Corasick algorithm, suffix arrays Week 3, Lecture 3	Chapter 9 of the text book
Elements of dynamic programming, Manhattan tourist problem, introduction to sequence alignment Week 4, Lectures 1-2 Global alignment, local alignment, affine gap penalties Week 4, Lecture 3	Chapter 6 of the text book
Approximate string matching, divide and conquer algorithms, Four-Russians trick Week 5, Lectures 1-2 Week 5, Lecture 3: Quiz 2	Chapters 7 and 9 of the text book
Multiple sequence alignment Week 6, Lectures 1-2 Week 6, Lecture 3 canceled due to holidays	Chapter 6 of the text book
Gene finding Week 7, Lectures 1-2 Heuristic sequence search Week 7, Lecture 3	Chapter 6 of the text book
Spaced seeds for heuristic spaced seeds, introduction to Hidden Markov Models Week 8, Lectures 1-2 Hidden Markov Models, Viterbi algorithm, Forward/Backward algorithm, profile HMMs Week 8, Lecture 3	Chapters 9 and 11 of the text book
Week 9, Lectures 1-2 are canceled Hidden Markov Models, Viterbi training, Baum-Welch algorithm Week 9, Lecture 3	Chapter 11 of the text book
Phylogenetic tree construction Week 10, Lectures 1-2 Week 10, Lecture 3	Chapter 10 of the text book
Clustering algorithms Week 11, Lectures 1-2 CAST algorithm, introduction to genome rearrangements Week 11, Lecture 3	Chapter 10 of the text book
Genome rearrangements, sorting by reversal Week 12, Lectures 1-2	Chapter 5 of the text book
RNA folding Week 13, Lectures 1-2 Week 13, Lecture 3 is canceled.