Computer Science 176 — Algorithms for Computational Biology (4 Units)

Course Overview

Summary

In 176, we study algorithms and data structures for many applications in Computational Biology. We discuss everything from genome searching, DNA alignment, evolutionary tree of life, and detecting coding regions.

Prerequisites

  • CS170 is a pretty hard prereq. Unless you know trees, greedy, and dynamic programming down SOLID, make sure you take 170 first.
  • CS70 and CS61B concepts come back again, so make sure you understand them well.
  • CS188 might be helpful (for HMMs)

Topics Covered

  • Exact String Matching (Z Algorithm, Suffix Tree, Suffix Arrays, Burrows-Wheeler Transform)
  • String alignment (Needleman-Wunsch, Hirschberg, Affine Gap, Smith-Waterman)
  • Network Alignment (specific to Yosef, who will probably teach for the next few years)
  • Phylogeny (UPGMA, Neighbor Join, Fitch, Sankoff, Perfect Phylogeny, 4-gametes)
  • Hidden Markov Models (Forward/Backward Algorithm, Viterbi, Expectation-Maximization)

Workload

Course Work

  • Fa15: 5 problem sets, 2 of which had significant programming components
  • This class is rigorous mathematically, with lots of probability.
  • Not a project-based course

Time Commitment

Although there is variation across semesters and students, expect to spend around 10 hours outside of class per week on this class.

Choosing the Course

When to take

If you are interested in biology and computing, this is the class for you. Additionally, if you really enjoyed the algorithm designs in CS170 (greedy, dynamic programming in particular), then you would enjoy CS176. CS 189 and CS 164 may also be helpful.

Note that this course is typically only offered in the Fall.

What's next?

For computational biology, research or internships. If you enjoyed the data structures, possibly CS270 and CS274. If you enjoyed the machine learning, maybe CS189. If you enjoyed the statistics CS281.

Usefulness for Research or Internships

In the field of computational biology, this class is very useful. In general, though algorithms covered may be useful for research, this class is not applicable to most research/internships. The course covers more of the theoretical work that has laid the groundwork for computational biology. Current research and work in computational biology tends to be more statistical and/or systems oriented.

Last edited: Spring 2017