(*
CSCI1950L - String Alignment

An Implementation of Smith-Waterman and Needleman-Wunsch with dynamic scoring matrices

Authors: Derek Aguiar and Ryan Tarpine

Instructions: Set your parameters for MATCH, MISMATCH, and GAP scores using the sliders below. Then click Evaluation -> Evaluate Notebook 
*)
(* Make sure all functions are evaluated so we can use them in the notebook. *)

globalm[vi_,wi_,gap_,score_]:=Module[{m},
m[i_,0]:=i *gap;
m[0,j_]:=j *gap;
m[i_,j_]:=m[i,j]=Max[
m[i-1,j-1]+score[vi[[i]],wi[[j]]],
m[i-1,j]+gap,
m[i,j-1]+gap];
m]

localm[vi_,wi_,gap_,score_]:=Module[{m},
m[i_,0]:=0;
m[0,j_]:=0;
m[i_,j_]:=m[i,j]=Max[
0,
m[i-1,j-1]+score[vi[[i]],wi[[j]]],
m[i-1,j]+gap,
m[i,j-1]+gap];
m]

globalalignment[m_,s_,t_,gap_]:=Module[{n,bt},
bt[0,0]={};
bt[i_,0]:=Map[{s[[#]],"-"}&,Range[1,i]];
bt[0,j_]:=Map[{"-",t[[#]]}&,Range[1,j]];
bt[i_,j_]:=Which[
m[i,j]==m[i-1,j]+gap,Append[bt[i-1,j],{s[[i]],"-"}],
m[i,j]==m[i,j-1]+gap,Append[bt[i,j-1],{"-",t[[j]]}],
True,Append[bt[i-1,j-1],{s[[i]],t[[j]]}]];
bt[Length[s],Length[t]]]

localignment[m_,s_,t_,gap_]:=Module[{n,bt,tab,i0,j0},
bt[i_,j_]/;m[i,j]==0.:={};
bt[i_,j_]:=Which[
m[i,j]==m[i-1,j]+gap,Append[bt[i-1,j],{s[[i]],"-"}],
m[i,j]==m[i,j-1]+gap,Append[bt[i,j-1],{"-",t[[j]]}],
True,Append[bt[i-1,j-1],{s[[i]],t[[j]]}]];
tab=Table[m[i,j],{i,Length[s]},{j,Length[t]}];
{i0,j0}=Position[tab,Max[tab]][[1]];
bt[i0,j0]]

(* Declared variables and functions *)

vi=Characters["atactacggaggg"];

wi=Characters["gaactgaggcgtat"];

(* Initial values *)
g=-1;
match=1;
mismatch=-2;

Manipulate[
p[x_,x_]:=match;
p[x_,y_]/;x≠y:=mismatch;
la=localm[vi,wi,g,p];
ga=globalm[vi,wi,g,p];
If[globalalignment[ga,vi,wi,g]=={}||localignment[la,vi,wi,g]=={},"You have no alignment. Check parameters.",{MatrixForm[Transpose[globalalignment[ga,vi,wi,g]]],MatrixForm[Transpose[localignment[la,vi,wi,g]]]}],
{{g,-1,"Gap Penalty"},-10,10,Appearance->"Labeled"},
{{match,1,"Match Score"},-10,10,Appearance->"Labeled"},
{{mismatch,-2,"Mismatch Score"},-10,10,Appearance->"Labeled"},
LocalizeVariables->False]