Genome 540 Homework Assignment 2

Due Sunday Jan. 23

  1. Write a program to find a highest-weight path in a weighted directed acyclic graph. This program should
  2. Write a program that
  3. For a graphic depiction of a WDAG:
  4. For a genome sequence: Your final output should include
  5. For the homework assignment, you should run your programs on the graph depicted here AND on the genome sequence of Thermocrinis albus DSM 14484. For the graph, initially find the maximum weighted path without start/end constraints. Then repeat the analysis constraining the path to start at node 'i' and end at node 'xiv'. Do not use any start/end constraint for the genome sequence analysis. To test whether your program is working correctly, run it first on the test example graph (both without constraint and requiring the path start at node 'vii' and end at node 'i'); and on the test genome sequence of Pyrococcus furiosus DSM 3638 to see whether you get the right answers (see the results template below).
  6. You must turn in your results and your computer program, using the template (file format) described below. Use this file as a template. The data definition at the top of the file allows you to validate the format of your results file. To check that you have valid XML syntax you can simply open the XML file with a browser like firefox. To do a more comprehensive validation (i.e. check that you have all of the required elements) use an online XML validator. Wrap your source code between the <file> elements with a CDATA definition (as in the results template) so special characters in the code (e.g. <) can be ignored by the XML parser. Please put everything into ONE plain text file - do not send an archive of files or a tar file, or a word processing document file. Compress it (using either Unix compress, or gzip -- if you don't have access to either of these programs let us know), and send it as an attachment to both Phil (phg (at) u.washington.edu) and Rupali (rpatward (at) u.washington.edu).