All assignments are to be submitted by email to Prof. Salzberg at salzberg@tigr.org. Assignments are due by
midnight on the due date.

Assignment 1, due Sept. 29.

Setubal and Meidanis: Chapter 2, problems 3, 5, 9.

Programming problem:
1. Implement the semiglobal sequence alignment algorithm from section 3.2.3 of SM. The algorithm
should find the optimal local alignment between its two input sequences. The beginnings and ends
of the sequences should not be penalized for gaps. Using a match score of +5, a mismatch penalty of -4,
and a gap penalty of -3, run your algorithm and align the DNA sequences CACGTAGCTACGAGCAGTCA and TAGCTGCTACAGAAG. Show the alignment in an easily readable format and print out its score.

2. Modify your solution to problem 1 to allow affine gap penalties, as explained in section 3.3.3. of SM. The algorithm should still run in time O(nm).