CS 466: Introduction to Bioinformatics

Jump to: description | schedule | homework | project | mental health statement

Semester	Fall 2021
Instructor	Prof. Mohammed El-Kebir
TA	Yuanyuan Qi (yq7), Leah Weber (leahlw2)
Time	WF 2:00-3:15 PM
Location	1302 Everitt Lab, or Zoom: [link] (only accessible with Illinois Zoom account)
Instructor office hours	Wednesdays 3:30-4:30 PM in 3216 Siebel Center, or Zoom: [link] (only accessible with Illinois Zoom account)
TA office hours	Mondays, 4-5 PM (Leah); Fridays 9-10 AM (Yuanyuan) on Zoom [link]
Piazza	[link]

Course description

This course introduces fundamental problems and algorithmic approaches in computational biology. Covered topics include:

1. sequence alignment,
2. genome assembly,
3. phylogenetics,
4. pattern matching,
5. 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 report (30%)

Course schedule

This is a tentative schedule and subject to change.

Date	Presenter	Slides	Reading
08/25/2021	Mohammed El-Kebir	Introduction [slides] [recording] [jupyter]	Jones and Pevzner: Chapters 2.1, 2.3, 2.4 and 6.2 Biology for Computer Scientists -- Lawrence Hunter [link]
08/27/2021	Mohammed El-Kebir	Sequence alignment I [slides] [recording]	Jones and Pevzner: Chapters 2.7-2.9 and 6.1-6.4 Lecture notes [link]
09/01/2021	Mohammed El-Kebir	Sequence alignment II [slides] [recording]	Jones and Pevzner: Chapters 6.6, 6.8 and 6.9. Lecture notes [link]
09/03/2021	Mohammed El-Kebir	Sequence alignment III [slides] [recording]	Jones and Pevzner: Chapters 6.7-6.9 Affine gap penalties example [link] [recording] Lecture notes [link]
09/08/2021	Mohammed El-Kebir	Sequence alignment IV [slides] [recording]	Jones and Pevzner: Chapters 7.1-7.4 Lecture notes [link]
09/10/2021	Mohammed El-Kebir	Multiple Sequence Alignment I [slides] [recording]	Jones and Pevzner: Chapter 6.10
09/15/2021	Mohammed El-Kebir	Multiple Sequence Alignment II [slides] [recording I] [recording II]	Lecture notes [link]
09/17/2021	Mohammed El-Kebir	Multiple Sequence Alignment III [slides] [recording]	Lecture notes [link]
09/22/2021	Mohammed El-Kebir	Multiple Sequence Alignment IV [slides] [recording]	Lecture notes [link]
09/24/2021	Mohammed El-Kebir	Multiple Sequence Alignment V [recording]
09/29/2021	Mohammed El-Kebir	Research talk [recording]
10/01/2021	TBD	Research talk + Midterm review [slides] [recording]
10/06/2021		Midterm (7-10pm CT)
10/08/2021		No class
10/13/2021	Mohammed El-Kebir	Phylogeny I [slides] [recording]	Jones and Pevzner: Chapter 10.2, 10.5-10.8
10/15/2021	Mohammed El-Kebir	Phylogeny II [slides] [recording]	Jones and Pevzner: Chapter 10.2, 10.5-10.8
10/20/2021	Mohammed El-Kebir	Phylogeny III [slides I] [slides II] [recording]	Jones and Pevzner: Chapter 10.2, 10.5-10.8
10/22/2021	Mohammed El-Kebir	Phylogeny IV [slides] [recording]
10/27/2021	Mohammed El-Kebir	Phylogeny V [slides] [recording]	Lecture notes [link]
11/03/2021	Mohammed El-Kebir	RNA Secondary Structure Prediction [slides] [recording]	Lecture notes [link] Nussinov example [link]
11/05/2021	Mohammed El-Kebir	Genome Sequencing [slides] [recording]
11/10/2021	Mohammed El-Kebir	Genome Assembly [slides I] [slides II] [slides III] [recording]	Jones and Pevzner: Chapter 8.1-8.4 Handout [link]
11/12/2021	Mohammed El-Kebir	HMM I [slides] [recording]	Jones and Pevzner: Chapter 11.1-11.3 Lecture notes [link]
11/17/2021	Mohammed El-Kebir	HMM II [slides] [recording]	Jones and Pevzner: Chapter 11.1-11.3 Lecture notes [link]
11/19/2021	Mohammed El-Kebir	HMM III [slides] [recording]	Jones and Pevzner: Chapter 11.1-11.3 Lecture notes [link]
12/01/2021	Students	Project presentations [recording]
12/03/2021	Students	Project presentations [recording]
12/08/2021	Leah Weber	Final review [slides] [recording]
12/10/2021		Final (7-10pm CT)

Homework

1. Homework 1 will be released on 09/08/2021 and will be due on 09/16/2021.
2. Homework 2 will be released on 09/22/2021 and will be due on 09/30/2021.
3. Homework 3 will be released on 10/29/2021 and will be due on 11/06/2021.
4. Homework 4 will be released on 11/10/2021 and will be due on 11/17/2021.
5. Homework 5 will be released on 11/19/2021 and will be due on 12/04/2021.

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.

1. Implement an algorithm discussed in class, and make it available on Github.
2. Benchmark algorithms discussed in class that solve the same problem on simulated or real data. Write a report about your findings.
3. Write a small survey paper, summarizing state-of-the-art algorithms for a specific computational biology problem.

Deadlines:

• Project proposal: 11/12/2021
• Project report: 12/19/2021

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).

Statement on Mental Health

Diminished mental health, including significant stress, mood changes, excessive worry, substance/alcohol abuse, or problems with eating and/or sleeping can interfere with optimal academic performance, social development, and emotional wellbeing. The University of Illinois offers a variety of confidential services including individual and group counseling, crisis intervention, psychiatric services, and specialized screenings at no additional cost. If you or someone you know experiences any of the above mental health concerns, it is strongly encouraged to contact or visit any of the University’s resources provided below. Getting help is a smart and courageous thing to do -- for yourself and for those who care about you.

Counseling Center	217-333-3704	610 East John Street Champaign, IL 61820
McKinley Health Center	217-333-2700	1109 South Lincoln Avenue, Urbana, Illinois 61801