Create a function called memoAlignScore$($S$1,$ S$2,$ gap, substitutionMatrix,memo$)$

We have already developed a function alignScore that computes the alignment score.

def alignScore$($S$1,$ S$2,$ gap, substitutionMatrix$)$:

$\text{'}\text{'}\text{'}$ Returns the sequence alignment score for S$1$ and S$2.\text{'}\text{'}\text{'}$

if S$1==""$: return gap $*$ len$($S$2)$

elif S$2==""$ : return gap $*$ len$($S$1)$

else:

option$1=$ substitutionMatrix$[($S$1[0],$ S$2[0])]+$ alignScore$($S$1[1$:$],$ S$2[1$:$],$ gap, substitutionMatrix$)$

option$2=$ gap $+$ alignScore$($S$1[1$:$],$ S$2,$ gap $,$ substitutionMatrix$)$

option$3=$ gap $+$ alignScore$($S$1,$ S$2[1$:$],$ gap $,$ substitutionMatrix$)$

return max$($option$1,$ option$2,$ option$3)$

Your first task is to implement a memoized version of alignScore, memoAlignScore$($S$1,$ S$2,$ gap, substitutionMatrix,memo$),$ where memo is a dictionary. You can start it off as $\{\}.$

Test your memoAlignScore function carefully. Here are some examples of the memoAlignScore function in action:

$>>>$ memoAlignScore$(\text{'}\text{'},\text{'}\text{'},-9,$blosum$62,\{\})$

$0$

$>>>$ memoAlignScore$(\text{'}\text{'},\text{'}$FGTSK$\text{'},-9,$blosum$62,\{\})$

$-45$

$>>>$ memoAlignScore$(\text{'}$IVEKGYY$\text{'},$'AVEYY',$-9,$blosum$62,\{\})$

$4$

$>>>$ memoAlignScore$(\text{'}$CIEAFGTSKQKRALNSRRMNAVGNDIVSTAVTKAAADVIDAKGVTALIQDVAQD$\text{'},$'RDLPIWTSVDWKSLPATEIFNKAFSQGSDEAMYDYMAVYKKSCPQTRR',$-9,$blosum$62,\{\})$

$-48$