Dynamic Programming

README.md

Built with blockbuilder.org

index.html

//The two sequences to compare
	var sequence1 = "GAATTCAGTTA"
	var sequence2 = "GGATCGA"

//Creates multi-dimensional array dependent on sequence lengths
  var arr = new Array(sequence2.length+1)
  	for(i=0;i<sequence2.length+1;i++){
      arr[i] = new Array(sequence1.length+1);
    }

//Fills array with 0s
  for(i=0;i<arr.length;i++){
    var col = i;
    for(j=0;j<arr[col].length;j++){
      arr[col][j]=0;
    }
  }

//Matrix Fill
for(i=1;i<arr.length;i++){
  var col = i;
  for(j=1;j<sequence1.length+1;j++){
    if(arr[col][j-1]>arr[col][j]){
      arr[col][j]=arr[col][j-1]
    }
    if(arr[col-1][j]>arr[col][j]){
      arr[col][j]=arr[col-1][j];
    }
    var match = 0;
    if(sequence2[col-1]==sequence1[j-1]){
      match = 1;
    }
    if((arr[col-1][j-1]+match)>arr[col][j]){
      arr[col][j]=(arr[col-1][j-1])+match;
    }
  } 
}

console.table(arr);