The aim of this course is to provide a more detailed look into algorithms in computational molecular biology than CS181. The course is organized into six chapters:
- BLAST and Karlin-Altschul Statistics
- Genome Assembly and Lander-Waterman Statistics
- Coalescent Theory and Ancestral Recombination Graphs
- Hidden Markov Models - The Learning Problem
- Clustering Theory and Spectral Clustering
- Protein Folding Algorithms
Each chapter is devoted to a class of fundamental computational problems in genomics related to the analysis of DNA, RNA, protein sequences and structures, and their molecular biological functions. Our journey in each chapter is driven by a set of beautiful algorithms, presented together with their theoretical foundations, in comprehensive analytical detail. ”Beautiful” algorithms are rigorous, practical and elegant, yet intuitive enough to be successfully implemented. The algorithms in each chapter are presented together with their underlying data structures, the mathematical analysis of their performance, and at times, the
exciting story of the researchers quest for algorithmic optimality (speed). The overall work in the class will help in providing an algorithmically and mathematically advanced journey through today’s most indispensable software genomics tools.
FAQ
Who takes the course?
CS182 is the sequel to CS181, but tends to attract not only students from the computational biology concentration, but also those in computer science, biology, and applied mathematics. This course assumes in-depth knowledge of a programming language of your choice (python is strongly recommended). Be sure to talk to one of the course staff if you are unsure whether the course is a good fit for you!
What biology background is needed?
There are no biology prerequisites, and no prior biology knowledge is assumed; the material that you need to know will be covered in class.
What computer science and mathematics background is needed?
In order to take this course, you must have taken CS181 in a past semester. From CS181, recall that students in the course generally have some prior exposure to basic concepts of discrete math (graphs, recurrence relations), discrete probability (random variables, independence), and algorithms (big-O notation, pseudocode).
What programming background is needed?
This class is more programming intensive than CS181, so if you had the programming prerequisites for CS181 waived, make sure you spend some time brushing up on your programming skills before the semester starts. If you are at all worried that any of these requirements will be a barrier during the semester, please reach out to one of the course staff – we would love to have everyone interested feel comfortable taking the course!
I am interested in learning how to analyze *-Seq data from my (advisor's) lab.
Will this course help me?
CS182 follows a similar conceptual theme to CS181, and is, in many ways, a direct extension of CS181. With that said, the goals of CS182 are to teach the algorithmic concepts that underlie a wide variety of software that is used to analyze biological data, particularly in genetics, genomics, and proteomics. The course will not teach you how to use any particular biological software package. Rather, you will learn how this software works, and more importantly for the long-term, how to think about biological problems in a computational way. Thus, when the latest and greatest technology for measuring DNA/RNA/protein is released in 5 or 10 years' time, you will have some algorithmic skills to work with this data, without waiting for the rest of the community to develop tools. If your interests are more narrowly focused on a particular, near-term application, another course might be more appropriate.
Can I get graduate credit for this course?
Yes! Just as in CS281, you will need to complete a significant final project, which includes both a programming and written component. You will need to meet with Professor Istrail sometime during late March or early April to solidify a plan for your project, which will culminate in a presentation and submission early in May. If you are an undergraduate pursuing graduate credit, please speak with Professor Istrail before registering for CS282. Professor Istrail would love to hear ideas that tie both the course content and research of your own into one beautiful project!