CSC 334: Midterm Grading Rubric

Part 1: (10pts)

(a) 3 - choose the overlap with maximum length and no mismatches
(b) 4 - correct de Bruijn graph (should have a loop)
    2 - linear or otherwise incorrect de Bruijn graph
(c) 3 - correct sequence and path
    2 - minor mistake in sequence

Part 2: (25pts)

(a)  5 - correct explanation that links “0’s” and disallowing negative scores
        to being able to start and end a local alignment at any point
     2 - explanation does not link local alignment to algorithm details
(b) 10 - completely correct table and analysis of score(4,4)
     2 - table is for global alignment instead
(c)  5 - best alignment score of 3, correct two tracebacks, correct analysis
         of one of the alignments as a read overlap
     3 - minor errors in alignments or analysis of read overlaps
     1 - global alignments returned
(d)  5 - correct 2 cases (last row to first col) or (last col to first row)
     2 - partially correct (something about last/first row/col)

Part 3: (10pts)

10 - correctly returns BWT of string
(+2) - extra credit for correct reverse BWT (no partial credit)

Part 4: (20pts)

10 - UPGMA correct with all branch lengths labeled
 8 - few incorrect lengths and/or missing lengths
10 - NJ correct with all branch lengths labeled, and correctly identified as
     closer to the truth
 8 - few incorrect lengths and/or missing lengths
 2 - distances from the matrix labeled on the tree

Part 5: (10pts)

10 - correct tree and all steps shown
 8 - missing a step, leading to incorrect tree 

Part 6: (25pts)

(a)  8 - Fitch correct and better solution correct (4 vs. 3 mutations)
     5 - problem with better solution and/or mutations incorrect
(b) 12 - algorithm will correctly minimize the number of mutations for
         any non-binary tree, with notation and explanation of each step
    10 - right idea but minor problem (missing top-down step, etc)
     6 - a valid algorithm but doesn’t minimize the number of mutations
(c)  5 - algorithm works correctly on the example tree (root is C), 6 mutations
     2 - algorithm run but doesn’t return the correct result