Announcements
- The first lecture will be held on August 25th, 2009.
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-90 and COMP790-90. 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 homework, two quizzes, 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://compgen.unc.edu/Courses/index.php?title=Comp_590-090 |
| Prerequisite: | COMP 401 or equivalent Some background in algorithms and data structures is helpful. |
Course Instructors
| Instructor: | Wei Wang | Instructor: | Leonard McMillan | |
| Office: | SN316 | Office: | SN319 | |
| email: | weiwang@cs.unc.edu | email: | mcmillan@unc.edu |
Office Hours: Thursdays 10:00-12:00am (Held in SN317)
(One, if not both of us, will be available at that time and place.)
Schedule
| Date | Lecture Topic | Reading Assignment | Homework |
| August 25 | Introduction (pdf) | Chapter 1 | |
| August 27 | High-throughput Biology (pdf) | Chapter 3 | |
| September 1 | Algorithms and Complexity (pdf) | Chapter 2 | Problem Set #1 |
| September 3 | DNA Restriction Mapping (pdf) | Chapter 4.1-4.3 | |
| September 8 | Finding Regulatory Motifs (pdf) Code: SearchTrees.py, Score.py, MotifSearch.py, MedianSearch.py |
Chapter 4.4-4.9 | |
| September 10 | Greedy Algorithms (pdf) Code: SimpleReversalSort.py |
Chapter 5.1-5.2 | |
| September 15 | Genome Rearrangements (pdf) | Chapter 5.3-5.5 | |
| September 17 | Dynamic Programming Preliminaries (pdf) | Chapter 6.1-6.3 | Problem Set #2 |
| September 22 | Sequence Alignments (pdf) | Chapter 6.4-6.8 | |
| September 24 | Class Canceled | ||
| September 29 | Local Sequence Alignment (pdf) | Chapter 6.8-6.10 | |
| October 1 | Gene Prediction (pdf) | Chapter 6.11-6.14 | |
| October 6 | Divide and Conquer Algorithms (pdf) | Chapter 7.1-7.4 | |
| October 8 | Divide and Conquer Algorithms (continued) | ||
| October 13 | Quiz #1 (Extra Credit) | ||
| October 15 | Graph Algorithms (pdf) | Chapter 8.1-8.8 | |
| October 20 | DNA Sequencing (pdf) | Chapter 8.9 | Problem Set #3 |
| October 22 | Fall Break (No Class) | ||
| October 27 | More DNA Sequencing | (Not in book) | |
| October 29 | Protein Sequencing (pdf) | Chapter 8.10-8.15 | |
| November 3 | Combinatorial Pattern Matching (pdf) (Suffix Trees) | Chapter 9.1-9.5 | Problem Set #4 |
| November 5 | Approximate Pattern Matching (pdf) | Chapter 9.6-9.8 | |
| November 10 | Graph Representations (pdf) | Chapter 10.1-10.3 | |
| November 12 | Clustering (pdf) | Chapter 10.4-10.8 | |
| November 17 | Clustering and Evolution (pdf) | Chapter 10.4-10.8 | Problem Set #5 |
| November 19 | Tree Construction (pdf) | Chapter 10.9-10.11 | |
| November 24 | Quiz #2 | ||
| November 26 | Thanksgiving Break (No Class) | ||
| December 1 | Hidden Markov Models (pdf) | Chapter 11 | |
| December 3 | Randomized Algorithms (pdf) | Chapter 12 | |
| December 8 | Review and Wrap-up (pdf) | ||
| December 17 | Final Exam, 12:00-3:00pm | ||