Homework 1: String Alignment
Due: Tuesday, Sept. 22, 11:59pm on Moodle
The goal of this assignment is to implement the string alignment algorithm we've been discussing class, also known as Needleman-Wunsch (variation: Smith-Waterman algorithm).
def match(b1, b2):
def align(s1, s2):which will print the optimal alignment between string s1 and s2 (i.e. s1 = 'GAGTAC' and s2 = 'GTAGCA'), and return the optimal score. First set up the dynamic programming (DP) table. What should the dimensions be for this table? You are welcome to use numpy arrays, or any other data structure you like.
hw1_first_last.py(first and last name), and submit it on Moodle.
Note: you can receive full credit for this assignment without doing the extension.
UPDATE: Biology direction option: instead of implementing backtracing, run your program on the following three sequences from three different species (run pairs at a time). From this output, what tree do you think relates these species? You can put your answer as a comment in your code, along with the scores for each pair.
species 1: ATTAGATCGTACCACTATAAGTTTAC
species 2: CTTAGATCGTTCCACACATATAC
species 3: ATTAGATCGTACCACATATATTA