Announcements
- Homework #5 is now complete. Note, that I have made some changes to the distance matrix in question #1 if you have previously printed it out (11/29/2011).
- A partial version of Homework #5 is posted. While it is not yet completed, you can go ahead and get started on it.
- Homework #4 has been posted and is due on November 29, 2011.
- I clarified/completed the starred part of question 3 in Homework #3. Moreover this part is now entirely optional. It will be worth at most 10 pts of extra credit.
- Solutions to Homeworks #1 and #2 are posted (see due dates in table below).
- Homework #3 has been posted and is due on October 25, 2011.
- Updated LCS.py code. Fixed and enhanced PrintLCS() function.
- Homework #2 has been posted and is due on October 6, 2011.
- A bug has been fixed in partialDigest.py. It now handles the dataset from the programming problem of homework #1.
- Posted office hours: Tuesdays from 9:00-11:00am
- I posted a revision to problem 3 of homework 1 (September 8, 2011).
- Homework #1 has been posted, and is due on September 22, 2011.
- The first lecture will be held on August 23, 2011.
Course Description
Computational methods are fueling a revolution in the biological sciences. Computers are already nearly as indispensable as microscopes for analyzing and interpreting biological data. As a result, two new multidisciplinary fields, bioinformatics and computational biology, have emerged. This course will explore the computational methods and algorithmic principles driving this revolution. It will cover basic topics in molecular biology, genetics, and proteomics. The course also addresses basic computational theory and algorithms including asymptotic notation, recursion, divide-and-conquer approaches, graph algorithms, dynamic programming, and greedy algorithms. These fundamental concepts from computer science will be taught within the context of motivating problems drawn from contemporary biology. Example biological topics include sequence alignment, motif finding, gene rearrangement, DNA sequencing, protein peptide sequencing, phylogeny, and gene expression analysis.
This course is suitable for both computer science and biology students at both undergraduate and graduate levels, and thus is co-listed as both COMP590-87 and COMP790-87. Students who wish to take this course should have some programming experience in a modern language. Knowledge of data structures, algorithm design, and biology is helpful but not required. There will be 6 problem sets with short programming assignments, a midterm, and a final exam.
Book, Course Information, and Prerequisites
| Textbook: | An Introduction to Bioinformatics Algorithms by Neil C. Jones and Pavel A. Pevzner MIT Press © 2004, ISBN: 0262101068. |
| Credit Hours: | 3 |
| Location: | FB007 |
| Time: | TR 2:00-3:15PM |
| URL: | http://www.csbio.unc.edu/mcmillan/Comp590F11 |
| Prerequisite: | COMP 401, Comp 116, or equivalent Some background in algorithms and data structures is helpful. |
Course Instructors
| Instructor: | Leonard McMillan |
| Office: | SN311 |
| email: | mcmillan@unc.edu |
| Office Hours: | Tuesdays 9:00-11:00am |
Schedule
| Date | Lecture Topic | Reading Assignment | Homework |
| August 23 | Introduction (pdf) | Chapter 1 | |
| August 25 | High-throughput Biology (pdf) | Chapter 3 | |
| August 30 | Algorithms and Complexity (pdf) | Chapter 2 | |
| September 1 | DNA Restriction Mapping (pdf) | Chapter 4.1-4.3 | Homework #1 |
| September 6 | Finding Regulatory Motifs (pdf) | Chapter 4.4-4.9 | |
| September 8 | Greedy Algorithms (pdf) | Chapter 5.1-5.2 | |
| September 13 | Genome Rearrangements (pdf) | Chapter 5.3-5.5 | |
| September 15 | Dynamic Programming Preliminaries (pdf) | Chapter 6.1-6.3 | Homework #2 |
| September 20 | Sequence Alignments (pdf) | Chapter 6.4-6.8 | |
| September 22 | Local Sequence Alignment (pdf) | Chapter 6.8-6.10 | HW #1 Due (solutions) |
| September 27 | Gene Prediction (pdf) | Chapter 6.11-6.14 | |
| September 29 | Divide and Conquer Algorithms (pdf) | Chapter 7.1-7.4 | Homework #3 |
| October 4 | Divide and Conquer Algorithms (continued) | ||
| October 6 | Graph Algorithms (pdf) | Chapter 8.1-8.8 | HW #2 Due (solutions) |
| October 11 | DNA Sequencing (pdf) | Chapter 8.9 | |
| October 13 | Midterm Exam | ||
| October 18 | High-throughput DNA Sequencing (continued) | (Not in book) | |
| October 20 | Fall Break (No Class) | ||
| October 25 | Protein Sequencing (pdf) |
Chapter 8.10-8.15 |
HW #3 Due |
| October 27 | Combinatorial Pattern Matching & Suffix Trees (pdf) |
Chapter 9.1-9.5 |
|
| November 1 | Suffix Arrays & Burrows-Wheeler Transforms (pdf) | (Not in book) | |
| November 3 | Approximate Pattern Matching (pdf) | Chapter 9.6-9.8 | |
| November 8 | Clustering (pdf) | Chapter 10.1-10.3 | |
| November 10 | Clustering and Evolution (pdf) | Chapter 10.4-10.7 | Homework #4 |
| November 15 | Tree Construction(pdf) | Chapter 10.8-10.11 | |
| November 17 | Perfect Phylogenetic Trees(pdf) | (Not in book) | Homework #5 |
| November 22 | Hidden Markov Models (pdf) |
Chapter 11 | |
| November 24 | Thanksgiving Break (No Class) | ||
| November 29 | Hidden Markov Models (continued) | HW #4 Due | |
| December 1 | Randomized Algorithms (pdf) | Chapter 12 | |
| December 6 | Review and Wrap-up (pdf) | HW #5 Due | |
| December 13 | Final Exam, 4:00-7:00pm | ||