CS 5984 Fall 2000 Homework Assignment 8

50 Points
Due: 10/30/00 at 5:00PM

The point value of each problem is shown in square brackets [ ]. Your solutions must be prepared with LaTeX or other word processing system and submitted as a stapled printout to a box outside the instructor's office (McBryde 638). This homework is due at 5:00PM on October 30, 2000. No late homework will be accepted. Be certain to write your solutions in COMPLETE SENTENCES.

  1. [25] Use the dynamic programming paradigm to compute the similarity of S1 = TCAGTGCAATG and S2 = CGTTGCATC, assuming the following symmetric s table:

    s A C G T _
    A 2 -2 -3 -1 -4
    C   1 -1 -1 -1
    G     1 -1 -2
    T       2 -8
    _         0

    In particular, (1) identify the subproblems; (2) write the recurrence that computes the optimal value for each subproblem; (3) draw and fill in the table, including appropriate arrows; and (4) give the optimal value for S1 and S2 and an optimal global alignment that demonstrates this optimal value.

  2. [25] Let S1 = TCAGTGCAATG and S2 = CGTTGCATC. Use dynamic programming to solve the end-space free variant of the similarity computation (Section 11.6.4 in Gusfield), using the s table in problem 1.

    In particular, (1) identify the subproblems; (2) write the recurrence that computes the optimal value for each subproblem; (3) draw and fill in the table, including appropriate arrows; and (4) give the optimal value for S1 and S2 and an optimal global alignment that demonstrates this optimal value.

Please report any problems found in these pages to:

CS5984 Class Account (algnbio@courses.cs.vt.edu)