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.

Note: There is no biology prereq for this course. The class focuses primarily on algorithms, only referencing biology as the motivation for certain problems.

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)
  • EECS126 might be helpful (for Continuous time Markov Chains / probability in general)

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

  • Fa18: 6 problem sets, with 1.5-2 weeks per pset
  • This class is rigorous mathematically, with lots of probability.
  • Fa18: 1 programming project on DNA Alignment assigned near the end of the semester, with ~4 weeks to complete
  • In general, the class is like a more laid back version of cs170

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: Summer 2020