CMSC 423, Fall 2011: Bioinformatic Algorithms, Databases, and Tools
Homework solutions
  1. pdf
  2. pdf
Project
  1. Global multiple sequence alignment with affine gaps
    • Call your class containing public static void main(String [] argv) "Main".
    • Parse score.matrix, in.fasta.
    • Find global alignments (with affine gaps) for every pair of sequences.
    • For each sequence, calculate the sum of its alignment scores (from above). Pick the one for which the sum is minimal (S_c).
    • Starting with S_c, progressively align it with other sequences.
    • To submit the project, export it as a .jar. Make sure that java msa.jar score.matrix in.fasta out.fasta works.
  2. Coming
Programming advice
Before you write any code for your projects, come up with a few test cases: think about the output you would expect to see; think of corner cases; come up with examples where your algorithm may generate multiple optimal solutions.
On dynamic programming:
(examples, techniques, and why it is not always the same as the recursion)
S. Dasgupta, C. H. Papadimitriou, and U. V. Vazirani. Algorithms, chapter 6. July 18, 2006. Online.