CS 5984 Fall 2000 Homework Assignment 9

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

  1. [25] Here are two amino acid (protein) sequences: 
    S1 = MEGKEENMRRGSHKFPERQSV
S2 = DVANPI

    Use the PAM30 substitution matrix to find an optimal global alignment of these two sequences. I strongly urge you to write a program to do this (in Perl, Java, or C; no C++ please!).

    Turn in and score an optimal global alignment. Also submit the filled-in dynamic programming table and explain how you extracted the alignment from the table.

  2. [25] Let S1 and S2 be the same as in problem 1. Let Wg=7 be the weight for opening a gap, and let Wg=1 be the weight for a space. Solve the gapped alignment problem as in Section 11.8.6, except take the score for a match or mismatch from the BLOSUM45 substitution matrix.

    Turn in and score an optimal global gapped alignment. Also submit the filled-in dynamic programming table (with the E(i,j), F(i,j), G(i,j), and V(i,j) values) and explain how you extracted the alignment from the table.

    Compare your results from problems 1 and 2 in a few sentences.

Please report any problems found in these pages to:

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