Assignment 2: Longest common subsequences (100 points)

Due at Feb 18 (Mon) 11:59pm

Objective: To implement the dynamic programming approach for finding the longest common subsequence of two strings.

Input: Two files (e.g. seq1 and seq2) with each containing a string (to be exact, a protein sequence) in FASTA format. In the FASTA format, the first line starts with > followed by the name of the string. The second line contains the string.

Output: The optimal alignment of the two sequences that gives the longest common subsequence, and the score of the alignment.

Note 0: Your program should ask users to input the names of the two files that contain the strings.

Note 1: Your program should be robust. It should work for any two strings given in the FASTA format.

Note 2: Your program should be user-friendly. Should any errors occur in the input (e.g. wrong file name), the program should prompt sufficient details of the errors instead of just crashing down with a black screen or looping forever.

Note 3: Practice good habits and professional styles in coding. Your codes should come with sufficient documentation and neat indentation.

Note 4: In the traceback table, if there is a tie between several choices, then you can randomly pick one.

Note 2: Implement your codes using c#, c/c++, Java, Python or Perl.

Note 3: Submit a detailed README file that shows instructions on how to compile and run your program. Specify the programming language and IDE (including version) you use and the operating system under which you have tested your codes.

Note 4: Submit a file showing the output you obtain on the test input files.

Note 5: Submit the codes and executable files. DO NOT submit any other junk files!