Genome 540 Homework Assignment 2

Due Sunday Jan. 27

1. Write a program to find a highest-weight path in a weighted directed acyclic graph. This program should
   • read in an input file that contains a representation of the graph in the following form:
     • a list of vertices, with each vertex on a separate line. The line should consist of
       1. a label (arbitrary string of up to 10 characters) for the vertex, which should be unique, i.e. different for different vertices.
       2. the string "START" if the path is to be constrained to start at this vertex
       3. the string "END" if the path is to be constrained to end at this vertex
       At most one vertex should be designated the START and at most one vertex should be designated the END. If none are, the path is assumed to be unconstrained. You may assume that parents precede children in the file, and then use this order in implementing the dynamic programming algorithm.
     • a list of edges, with each edge on a separate line. The line should consist of
       1. a label for the edge (which need not be unique -- i.e. different edges can have the same label);
       2. the label of the edge's beginning vertex;
       3. the label of its ending vertex;
       4. the numerical weight attached to the edge.
   • use dynamic programming to find the highest weight path (with additive, not multiplicative, path weights).
   • output:
     • the path score
     • the label of the beginning vertex on the path
     • the label of the ending vertex on the path
     • (in order) the labels for all the edges that occur on this path. For example, if the graph is a sequence graph and labels correspond to nucleotides in the sequence, the list of labels would correspond to the sequence of the highest scoring segment of the sequence.
2. Write a program that
   • reads in 2 input files:
     • a FASTA file containing a DNA sequence, and
     • a 'scoring scheme' file that indicates a score to be attached to each possible base (A, C, G, T, or other)
   • creates the sequence graph for the sequence, as described in lecture (i.e. a 'linked list' with one edge per residue).
     • the labels attached to successive vertices should be successive integers, represented as character strings (the first vertex being '0', the second being '1', the third being '2', and so on);
     • the label attached to each edge should be the corresponding residue;
     • the weight attached to an edge should be the score for that residue, as specified in the scoring scheme file.
   • outputs this graph in a file that has the appropriate input format for the program described in #1 above (with no vertices designated START or END).
3. For a graphic depiction of a WDAG:
   • Convert (by hand) the graph into an input file having the format described in #1 above.
   • Run your program in #1 above on this input file.
4. For a genome sequence:
   • Run the program in #2 above, using as input files the .fna file for that genome and a scoring scheme file that attaches -1.49 to an A or T nucleotide, and 0.74 to a G or C (and assigns 0 to any ambiguity characters in the sequence). Then run your program in #1 above on the resulting output file in order to find the highest scoring segment (= path) of the sequence.
   Your final output should include
   • the name and first line of the .fna file
   • the location (the first and last nucleotide positions, as deduced from the vertex labels), the sequence (as indicated by the edge labels), and score of the highest-scoring segment.
5. For the homework assignment, you should run your programs on the graph depicted here, constraining the path to start at the node 'i' and end at the node 'x'; AND on the genome sequence of Methanothermobacter thermautotrophicus (NC_000916.1). To test whether your program is working correctly, run it first on the test example graph, constraining the path to start at 'vii' and end at 'i'; and on the test genome sequence Pyrococcus furiosus to see whether you get the right answer (below). In the depicted graphs, the shape of the triangle indicates the direction in which the edge is pointing.
6. You must turn in your results and your computer program, using the template (file format) described below. Use this file as a template -- you can use the DTD definition to validate the format of your results file. 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 Will (wsheffle (at) u.washington.edu).