Introduction

In class we worked on LCSBacktrack() to align two DNA sequences. There's an implementation in the align.ipynb notebook. We mentioned that this function only counts matches between sequences, potentially leading to the insertion of spurious gaps. We mentioned one possible solution: penalizing gaps and mismatches in the alignment.

Assignment

Implement a function GlobalAlign(u,v) that returns the best alignment matrix for sequences u and v using a score matrix. You may use a scoring matrix that uses +1 for matches, -1 for mismatches and -4 for gaps, as described in the text. You can use LCSBacktrack as a template for your new function.