CS 466: Introduction to Bioinformatics
Jump to: description | schedule | homework | project
Semester |
Fall 2019 |
Instructor |
Prof. Mohammed El-Kebir |
TA |
Ashwin Ramesh (aramesh7) |
Time |
WF 2:00-3:15 PM |
Location |
0216 Siebel Center |
Office hours |
Wednesdays 3:15-4:15 PM in 3216 Siebel Center |
TA office hours |
Fridays 11-11:59 AM in 3405 Siebel Center |
Course description
This course introduces fundamental problems and algorithmic approaches in computational biology. Covered topics include:
- sequence alignment,
- genome assembly,
- phylogenetics,
- pattern matching,
- cancer genomics.
This course will
not teach you how to run popular bioinformatics tools. Rather, we will focus on the underlying algorithmic ideas and the issues that arise when translating a biological problem into a computational problem and ultimately an accurate tool for biologists to use. In addition, this course will teach you how to read scientific papers and how to propose and conduct independent research.
Book: Jones and Pevzner,
An Introduction to Bioinformatics Algorihms.
Prerequisites
Programming skills (equivalent to CS 225) for doing the mini-project. No background in biology is required. If you did not take CS 225 and its prerequisites at UIUC, you will need to get permission from me to stay in the course.
Grading
Undergraduates will receive 3 undergraduate credits; graduate students can enroll for 3 or 4 graduate credits.
3-credit students:
- Five problem sets (30%)
- Midterm (25%)
- Final (25%)
- Team-based (3-4 people) mini-project and report (20%)
4-credit students:
- Five problem sets (20%)
- Midterm (25%)
- Final (25%)
- Small team-based (1-2 people) mini-project and indivual report (30%)
Course schedule
Date |
Presenter |
Slides |
Reading |
08/28/2019 |
Mohammed El-Kebir |
Introduction [slides] [jupyter] |
- Jones and Pevzner: Chapters 2.1, 2.3, 2.4 and 6.2
- Biology for Computer Scientists -- Lawrence Hunter [link]
|
08/30/2019 |
Mohammed El-Kebir |
Sequence alignment I [slides] |
- Jones and Pevzner: Chapters 2.7-2.9 and 6.1-6.4
- Lecture notes on Big Oh [link]
|
09/04/2019 |
Mohammed El-Kebir |
Sequence alignment II [slides] |
- Jones and Pevzner: Chapters 6.6, 6.8 and 6.9.
- Lecture notes [link]
|
09/06/2019 |
Mohammed El-Kebir |
Sequence alignment III [slides] |
- Jones and Pevzner: Chapters 6.7-6.9
- Affine gap penalties example [link]
- Lecture notes [link]
|
09/11/2019 |
Mohammed El-Kebir |
Sequence alignment IV [slides] |
- Jones and Pevzner: Chapters 7.1-7.4
- Lecture notes [link]
|
09/13/2019 |
Mohammed El-Kebir |
Multiple Sequence Alignment I [slides] |
- Jones and Pevzner: Chapter 6.10
|
09/18/2019 |
Mohammed El-Kebir |
Multiple Sequence Alignment II [slides] |
|
09/20/2019 |
Mohammed El-Kebir |
Multiple Sequence Alignment III [slides] |
|
09/25/2019 |
Mohammed El-Kebir |
Multiple Sequence Alignment IV [slides] |
|
9/27/2019 |
Mohammed El-Kebir |
Midterm review |
|
10/02/2019 |
Ashwin Ramesh |
Midterm review |
|
10/04/2019 |
|
Midterm |
|
10/09/2019 |
Mohammed El-Kebir |
RNA Secondary Structure Prediction [slides] |
|
10/11/2019 |
Mohammed El-Kebir |
Protein Structure Alignment [slides] |
|
10/16/2019 |
Mohammed El-Kebir |
Phylogeny I [slides] |
- Jones and Pevzner: Chapter 10.2, 10.5-10.8
|
10/18/2019 |
Mohammed El-Kebir |
Phylogeny II [slides] |
- Jones and Pevzner: Chapter 10.2, 10.5-10.9
|
10/23/2019 |
Mohammed El-Kebir |
Phylogeny III [slides] |
|
10/25/2019 |
Mohammed El-Kebir |
Phylogeny IV [slides] |
|
10/30/2019 |
Mohammed El-Kebir |
Cancer Phylogenetics I [slides] & [slides] |
|
11/01/2019 |
Mohammed El-Kebir |
Cancer Phylogenetics II [slides] [slides] |
|
11/06/2019 |
Mohammed El-Kebir |
HMM I [slides] |
- Jones and Pevzner: Chapter 11.1-11.3
- Lecture notes [link]
|
11/08/2019 |
Mohammed El-Kebir |
HMM II |
- Jones and Pevzner: Chapter 11.1-11.3
- Lecture notes [link]
|
11/13/2019 |
Mohammed El-Kebir |
HMM III |
- Jones and Pevzner: Chapter 11.1-11.3
- Lecture notes [link]
|
11/15/2019 |
Canceled |
Canceled |
|
11/20/2019 |
Mohammed El-Kebir |
Genome Assembly I [slides1] [slides2] |
- Jones and Pevzner: Chapter 8.1-8.4
- Handout [link]
|
11/22/2019 |
Mohammed El-Kebir |
Genome Assembly II [slides1] [slides2] |
- Jones and Pevzner: Chapter 8.1-8.4
|
12/04/2019 |
Students |
Project presentations |
|
12/06/2019 |
Students |
Project presentations |
|
12/11/2019 |
TBD |
Final review |
|
Homework
- Homework 1 will be released on 9/11/2019 and will be due on 9/18/2019.
- Homework 2 will be released on 9/25/2019 and will be due on 10/2/2019.
- Homework 3 will be released on 10/25/2019 and will be due on 11/2/2019.
- Homework 4 will be released on 11/15/2019 and will be due on 11/22/2019.
- Homework 5 will be released on 12/2/2019 and will be due on 12/9/2019.
Late policy:
- Students may request one 3-day extension in the semester for full credit.
- Otherwise, late submission within 3 days results in at most 80% of
credits. Submission later than 3 days results in 0% of credits.
Project
There are three kinds of projects.
- Implement an algorithm discussed in class, and make it available on Github.
- Benchmark algorithms discussed in class that solve the same problem on simulated or real data. Write a report about your findings.
- Write a small survey paper, summarizing state-of-the-art algorithms for a specific computational biology problem.
Some implementation-based project ideas:
- Extend Needleman-Wunsch aligner to support fitting alignments and local alignments. [link] [Github]
- Extend Needleman-Wunsch aligner to support affine gap penalties. [link] [Github]
- Implement linear space global alignment algorithm.
- Implement Nussinov algorithm.
- Benchmark current multiple sequence alignment algorithms.
- Study, implement and extend HMM described in Shihab, H. A., Gough, J., Cooper, D. N., Day, I. N. M. & Gaunt, T. R. Predicting the functional consequences of cancer-associated amino acid substitutions. Bioinformatics 29, 1504–1510 (2013).
Deadlines:
- The project proposal will be due on 11/3/2019.
- The project report will be due on 12/22/2019.