Programming Assignment 1

Programming Assignment 1

Due Date: July 7, 2016

The Longest Common Subsequence Problem

For this assignment you will solve/implement the Longest Common Subsequence (LCS) problem using dynamic programming. Please follow these steps:

• Study the LCS problem, section 15.4 from the textbook
• Implement a dynamic programming algorithm that solves the LCS problem
  • Input: two DNA sequences
  • Output: the LCS of the input sequences
• The LCS of strings \(S_1\) and \(S_2\) is a third string \(S_3\) in which the bases of \(S_3\) appear in each of \(S_1\) and \(S_2\). These bases must appear in the same order but not necessarily consecutively.
  • \(S_1 = ACCGGTCGAGTGCGCGGAAGCCGGCCGAA\)
  • \(S_2 = GTCGTTCGGAATGCCGTTGCTCTGTAAA\)
  • \(S_3 = GTCGTCGGAAGCCGGCCGAA\)