CPS 160: 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 machine learning. Development of practical experience with handling, analyzing, and visualizing genomic data using the scripting language Perl.

The course will require students to program in Perl. Students coming in to the course should know how to program in some computer language, but it need not be Perl. Students should also have had some exposure to basic probability, statistics, 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

Michael Mayhew

Daphne Ezer

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 Wednesdays and Fridays from 10:05 until 11:20 in LSRC, Room D243.

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, RG: Raluca Gordân, DW: Debbie Winter, LB: Lisa Bukovnik

Perl tutorial slides

• Perl tutorial 1 slides (25.9MB); all the examples can be snarfed directly into Eclipse.
• Perl tutorial 2 slides (20.1MB); all the examples can be snarfed directly into Eclipse.

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 by Larry Hunter.
• The Chemistry of Life 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.

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 you can learn.

Textbooks mentioned in class

The various books mentioned in class are all listed in the "External Links" section within Blackboard; each is linked to Amazon where you can read more.

Finding spliced genes in genomes of higher eukaryotes

As discussed in class, the GENSCAN tool was first described in this paper, which you may enjoy reading (or at least skimming). To guide you, the most interesting parts (from the point of view of CPS 160) are the methods, which in biology papers are located at the very end, after the introduction, results, and discussion (why this is done is a matter for another time). So you may want to start with the right column of page 85.

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.

Online Perl resources

• Beginner's introduction to Perl
• Perl FAQ (frequently asked questions)
• Beginning Perl, a highly regarded online textbook
• Essential Perl, a 23 page introduction to the main features of Perl from Stanford CS Education Library

More help on specific topics:

• Referencing/dereferencing cheat sheet: A cheat sheet from Abrita Chakravarty with examples for referencing and dereferencing arrays and hashes
• References: Short tutorial on the syntax of references in Perl
• Common Perl data structures: A completely excellent guide on how to use arrays of arrays, arrays of hashes, hashes of hashes, and hashes of arrays in Perl (the table of contents is particularly helpful to pointing you to just what you need if you only want a quick reference)
• Regular expressions:
  1. Quick refresher on Perl regular expressions
  2. Detailed tutorial on Perl regular expressions
• Debugging:
  1. Short pieces on common syntax errors, logic errors and using the strict option to prevent undefined variables.
  2. Using the Perl debugger in EPIC
  3. A tutorial on using the Perl debugger from command line.

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

Snarfing and running a sample Perl program

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

First ensure that you have the right perspective in Eclipse. The Perl perspective will give you a less cluttered set of windows with the smaller Navigator and Outline on the left and the main editor window on the right.

• Select "Window > Open Perspective > Other..."
• Select "Perl", then hit OK.
• You should see a "Perl" box highlighted in the upper right corner of your window. If in the future, your screen setup looks odd, try to ensure you are in the Perl 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/fall11/cps160/snarf/"
• Expand the project site "CPS 160, Fall 2011" and click through the list by expanding the folders until you find "Sanrfing 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"
• You can then double click the "Snarfing Sample" project in the "Navigator" window, on the upper left of the main editor window and then double click "first.pl"
2. Now we will try running the simple Perl 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 > Perl Local"

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".

You should also notice that PerlDoc is available from within Eclipse. Just select any Perl keyword in your program (for example, you can select "print") and then choose "Help > Perldoc" (or use the associated key shortcut). This will open a tab "PerlDoc" that contains the help page for the print function. Once the PerlDoc window is open, you can search for other keywords right in the PerlDoc window.

Editing a sample Perl program and submitting a project

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

1. Modify the file "first.pl" to print out both the minimum and the maximum value:
   • Add another line: print "The maximum value is: $maxval.\n";
   • Save the file
   • Run "first.pl" again, to see if it prints out the maximum.
2. 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 you wish to submit to, so click on "cps160", select the "test.of.submit" folder as your destination, and 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, without overwriting previous submissions. Thus, if you realize that you did something wrong at the last minute, you can simply resubmit. 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, you should consult others to make progress—that is better than giving up entirely. Your first course of action is to speak to the instructor or TAs, or to post a question on Piazza. 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 rather than answers; after consultation, it is expected that you should still have some 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, 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 will often include some gestation period before things become clear) and 2) to provide flexibility as to when students complete their work while they juggle requirements and commitments of many sorts 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. 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 an extension if necessary.
2. 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, just 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 on Blackboard before you turn in your work.

Grading policy

Problem sets: 84%

All students will be expected to complete seven problem sets over the semester, each contributing 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.

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 page at: http://www.piazza.com/duke/fall2011/cps160.