COMPSCI 260: Introduction to Computational Genomics

Overview

A computational perspective on the exploration and analysis of genomic and genome-scale information. Provides an integrated introduction to genome biology, algorithm design and analysis, and probabilistic and statistical modeling. Topics include genome sequencing, genome sequence assembly, local and global sequence alignment, sequence database search, gene and motif finding, phylogenetic tree building, and gene expression analysis. Methods include dynamic programming, indexing and hashing, hidden Markov models, and elementary supervised and unsupervised machine learning. Development of practical experience with handling, analyzing, and visualizing genomic data using the computer language Python.

The course will require students to program often in Python. Students coming in to the course should know how to program in some computer language, but it need not be Python. Students should be comfortable with mathematical formulas and should have had some exposure to basic probability and molecular or cellular biology; however, the course has no formal course prerequisites, and significant background will be provided. Please speak to the instructor if you are unsure about your background. This course is a valid elective in both biology and computer science.

Instructor

Professor Alex Hartemink

Office hours

Alex Hartemink, Instructor

Jianling Zhong, TA

Michael Mayhew, TA

Anna Liu, UTA

Chinmay Patwardhan, UTA

Thanh-ha Nguyen, UTA

If these office hours do not work for you, please post questions via Piazza, or send any of us an email to schedule an alternate time.

Logistics

The class meets on Tuesdays and Thursdays 10:05–11:20AM in 116 Old Chemistry (on the Main West Quad, near Bostock Library).

Course schedule

Note: The course schedule may change subtly from time to time. Always check the web page for the most up-to-date schedule.

AH: Alex Hartemink

GENSCAN paper

• GENSCAN: Burge and Karlin 1997; as an aside, the senior author of the GENSCAN paper, Samuel Karlin, is the same fellow that helped develop the significance statistics for BLAST database searching

Tree of life papers

• Wolf et al.
• Doolittle and Bapteste

Suffix trees

• Our summary writeup of the basics
• A detailed description of Ukkonnen's linear time construction algorithm

Genome sequencing technology papers

• Multi-technology DNA sequencing review from 2008
• Illumina Solexa overview from 2007
• Roche 454 overview
• Duke sequencing facility tour slides

Papers debating the merits of shotgun sequencing the whole human genome

• Pro 1997
• Con 1997
• Pro 1999

Papers reporting a newly sequenced genome

• Fly genome
• Fly genome assembly
• Fly genome comparison to worm and yeast
• Human genome (HGP)
• Human genome assembly (HGP)
• Human genome (Celera)
• Reflecting on process (HGP perspective)
• Reflecting on process (Celera rebuttal)

Seminal papers developing sequence alignment and database search

• Needleman and Wunsch (1970)
• Sankoff (1972)
• Waterman, Smith, and Beyer (1976)
• Smith and Waterman (1981)
• Gotoh (1982)
• Lipman and Pearson (1985)
• Pearson and Lipman (1988)
• Altschul, Gish, Miller, Myers, and Lipman (1990)
• Descriptive comparison of FASTA and BLAST

Graph search

An overview of the DFS and BFS algorithms for visiting the nodes of a graph.

Closest pair of points

A careful description of the algorithm for finding the closest pair of points in O(n log n) time. This is from the 2nd edition of "Introduction to Algorithms" (fondly known as CLRS).

Severe acute respiratory syndrome (SARS)

Here is the SARS genome handout from class. Here is a text file containing the SARS genome (Tor2 isolate). Have fun parsing it! You can also find it, and a lot more information about it, in GenBank: visit the Genbank entry and see what else you can learn.

Cool site for visualizing execution of Python code

If you want a little more clarity about how Python creates variables, populates them, and passes them around, or if you want to visualize your code in action for debugging purposes, check out this cool site. You can study their code examples, or paste in your own code.

Python tutorial slides

• Python tutorial 1 slides (168 KB); the examples can be snarfed directly into Eclipse.
• Python tutorial 2 slides (256 KB).

For shoring up your biology background

Here are a few different kinds of resources for those with less biology background, ranging from the comprehensive to a basic overview:

• Molecular Biology for Computer Scientists, a short primer by Larry Hunter.
• The Chemistry of Life, a short primer by Michael Behe.
• Molecular Biology of the Cell, a huge classic textbook by Bruce Alberts, et al., is available for free online at NCBI. It is a good resource for biological questions and background, but can only by accessed via a search interface. If you don't understand a term or concept, you can try searching here.

Textbooks mentioned in class

The various books mentioned in class are summarized here; each is linked to Amazon where you can read more (these are not affiliate links). Note that none of these books is compulsory for the class, though you may benefit from one or more. As for the books on Python, many resources are now available free online, even complete textbooks downloadable as PDFs (you'll save trees (unless you print them)).

Introduction to Computational Genomics: A Case Studies Approach

Hahn was a grad student at Duke in the lab of Greg Wray and took this very class once upon a time. I love the case study approach: it makes for very interesting reading. At the end of the day, I decided not to require the book because it's not a perfect match for the course, but in terms of overlap with the course content, it comes the closest of any book to date so it might be useful for some.
http://www.amazon.com/exec/obidos/ASIN/0521671914/

Biological Sequence Analysis: Probabilistic Models of Proteins and Nucleic Acids

This book covers a lot of the material that will be covered in the course and has a distinctly probabilistic focus. It is very well written but is at a fairly advanced level. It is an excellent reference for folks continuing on in this area.
http://www.amazon.com/exec/obidos/ASIN/0521629713/

An Introduction to Bioinformatics Algorithms

This book by Jones and Pevzner covers many of the topics that will be covered in class, but organizes the material around algorithmic methods rather than biological problems. So one chapter presents many problems across bioinformatics that exploit string matching, etc. While not complete for this course, it is a nice, readable, undergraduate textbook and is a bit more approachable than Pevzner's earlier book.
http://www.amazon.com/exec/obidos/ASIN/0262101068/

Directions for setting up Java, Eclipse, Python, and Eclipse plugins

Snarfing and running a sample Python program

Let's try snarfing and running your first Python program in Eclipse.

First, ensure that you have the right perspective in Eclipse. The Python perspective will give you a less cluttered set of windows with the smaller PyDev Package Explorer on the left and the main editor window on the right.

1. Select "Window > Open Perspective > Other..."
2. Select "PyDev", then hit OK.
3. You should now see a "Python" box highlighted in the upper right corner of your window. If in the future, your screen setup looks odd, ensure you are in the Python perspective.

The Ambient plug-in allows you to browse for and download code online using a tool called Snarf. For each problem set, we will provide you with some code as a framework and possibly some data files, and Snarf will allow you to import these files into your local copy of Eclipse. To snarf your first program, follow the directions below.

1. Snarf in the Snarfing Sample project
   • Open Eclipse
   • Select "Ambient > Download (Snarf) a Project..."
   • This should open a new tab at the bottom called "Snarfer Site Browser". If it does not:
     • Select "Window > Show View > Other..."
     • Click "Ambient" then select "Snarfer Site Browser" and hit OK
   • Right-click within the "Snarfer Site Browser" window, and select "New Site"
   • In the window, type "http://www.cs.duke.edu/courses/fall13/compsci260/snarf/"
   • Expand the project site "COMPSCI 260, Fall 2013" and then the "Samples" folder to find "Snarfing Sample (1.0)", and double click on it
   • Click the "Install Project" button, and in the window that pops up, check the "use default workspace location" box, and click "Finish"
   • The "Import project" window will come up; leave the fields unchanged (in particular, leave "Use the downloaded .project file" selected) and click "Finish"
   • Expand the "Snarfing Sample" project in the "PyDev Package Explorer" pane on the left side, and double-click "python.intro.pl" to open it up in the editor pane
2. Try running the simple Python program that you snarfed
   • Click on the "Run" icon on the toolbar (the green circle with the white triangle pointing right) to run the program; this should create a "Console" tab in the bottom right pane and the results of the program should be printed in it. If the console does not appear:
     • Select "Window > Show View > Other..."
     • Click "General" then select "Console" and hit OK
   • Alternatively, select "Run" from the Run menu
   • Alternatively, right-click anywhere within the body of the program to see the context menu and then click on "Run As > Python Run"

You can repeat step 2 every time you edit and save the program.

For each assignment, we will provide a codebase for you to work from, which you will always be able to import by snarfing it into Eclipse.

You should also notice that simple Python documentation is available from within Eclipse: just hover over a Python keyword and a tooltip will pop up with a short description.

Editing a sample Python program and submitting a project

Now modify the program and then submit the code from within Eclipse.

1. Modify the file "python.intro.py" to change the output in some way
2. Save and re-run the program to confirm the output changed as expected
3. Now test submitting your new program along with the other files in the project:
   • Select "Ambient > Submit a Project for Grading..." to bring up the submit window
   • First, you must choose the class and assignment folder you wish to submit to, so click on "compsci260" and select the "test" folder as your destination; then click "Next"
   • Select "Submit a single project", choose the project you wish to submit (in this case "Snarfing Sample"), and then hit "Next"; alternatively, if you do not want to submit the entire project, you can choose "Submit from the file system" and then you'll have an option to select and deselect the various files in the project (or elsewhere)
   • Once you've got the project and/or files that you want selected, choose "Finish"; you will be asked to enter your Duke NetID and password.
   • Congratulations, you have submitted your project!

You can submit as many times as you like, and everything will be stored on the server each time. Thus, if you realize that you did something wrong at the last minute, you can simply resubmit and we'll have both. In general, we will only look at your last submission, so when you resubmit a project, please resubmit all the relevant files, not just the ones you modified.

Academic integrity

All students are expected to abide by generally accepted standards of academic integrity. This includes all the various aspects of Duke's Community Standard. Violations of academic integrity will be taken very seriously. In particular, be reminded that it is not acceptable to take the ideas/work of another and pass it off as one's own, even if paraphrased. Ideas taken from others, whether peers in the class or not, must always be appropriately cited.

Collaboration policy

Unless expressly granted in the problem set, all problems should be completed individually; no collaboration is permitted. However, if you have worked for a while on a particular problem and have encountered a mental wall, and if you have banged your head against said wall for a while, we provide mechanisms where you can consult others to make progress, rather than giving up entirely. Your first course of action is to post a question on Piazza, or to speak to the instructor or TAs. If for any reason you consult your peers outside of Piazza, it should remain understood that such an interaction must be one of consultation and not collaboration: hints to help overcome a small obstacle rather than answers—after consultation, it is expected that you should still have plenty of thinking to do. In addition, if you happen to consult with another student, both of you must cite this.

Extension policy

Students generally have two weeks to work on problem sets—not because two weeks are generally required to finish, but 1) to allow students who start early sufficient time to reflect/ruminate on problems where an impasse has been reached (the thought process through which students go while solving a problem often includes some gestation period before things become clear) and 2) to provide flexibility as to when students complete their work while they juggle other requirements and commitments during the semester.

Given this latter point, students should not request extensions for turning in their work beyond the two weeks already allotted. However, this rule has two exceptions:

1. Everyone invariably has some two-week interval that is especially tough, so students are allowed, once during the semester, to use an extra 48 hours to turn in their work. If you are exercising this option for a specific problem set, please indicate such when you turn in your work. It is entirely up to you when you want to use this one free extension; when you do, you are trusted to not consult the solutions if they happen to be posted before you turn in your work.
2. If you are ill for a non-trivial length of time, you may choose to submit a short-term illness notification to the deans; I am notified during this process, at which point we can work out a possible extension if one is necessary.

If you turn in work after the deadline but have already used your free extension, or if you are using your free extension but turn in work after the extension deadline itself, we will take off 10 points for every 12 hours late (rounded up). So if you're 0-12 hours late, that's -10; if you're 12-24 hours late, that's -20, etc.

Grading policy

Problem sets: 84%

All students will be expected to complete seven problem sets over the semester, each contributing about equally to this component of the grade.

Participation: 16%

Students are expected to attend class regularly and participate in discussions. They are also expected to be engaged via Piazza, posting questions or notes, as well as helping each other as questions arise, or raising interesting points for further conversation. Students should feel comfortable asking questions at any point in class—whether the material is unclear, or simply if it leads you to wonder about a new connection. The instructor encourages an interactive classroom so if something is troubling or exciting you, do not hesitate to speak up about it.

Grades

Grades for all work will be recorded and available to students via the course Sakai site. Posting grades will be our only use of Sakai.

Piazza

This term we will be using Piazza for course announcements, communication, and discussion. The Piazza system is highly catered to getting you help quickly and efficiently from classmates, the TAs, and the instructor. Rather than emailing questions to the teaching staff, please post your questions on Piazza so everyone can benefit from the responses.

You can find our class posting page at: https://piazza.com/class#fall2013/compsci260.