CS 5984 Fall 2000 Homework Assignment 7

50 Points
Due: 10/23/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 23, 2000. No late homework will be accepted. Be certain to write your solutions in COMPLETE SENTENCES.

  1. [10] Show by an infinite set of instances for the Edit Distance Problem that the number of optimal solutions may be exponential in the size of the instance.

  2. [20] Let S1 = TCAGTGCAATG and S2 = CGTTGCATC.

    1. Build the complete dynamic programming table (as in Figure 11.3) for these strings.

    2. What is the edit distance between S1 and S2?

    3. List all optimal global alignments between S1 and S2.

  3. [20] Redo problem 2 with the editing costs revised to be 0 for matches, 3 for insertions or deletions, and 1 for mismatches.

Please report any problems found in these pages to:

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