globalAlignment=function(seq1,seq2){
 #score values
  matchVal=2
  missmatchVal=-2
  indelVal=-1

 
  
  if (!is.character(seq1) || (!is.character(seq1))){
    cat("Error input sequences\n")
    return
  }
  size1=length(seq1)+1
  size2=length(seq2)+1
  #creating score matrix
  score=matrix(rep(0,size2*size1),nrow=size1,ncol=size2)
  #creating backpointer matrix
  backpointer=matrix(rep('-',size2*size1),nrow=size1,ncol=size2)
  
  for (i in 1:size1){
    for (j in 1:size2){
      tempscore=c(-.Machine$integer.max,-.Machine$integer.max,-.Machine$integer.max)
      #case position 1 1
      if ((i==1) & (j==1)){
        score[i,j]=0
      }
      else{
        # caso match or missmatch
        if ((i!=1) & (j!=1)){
          tempscore[1]=score[i-1,j-1]
          
          if (seq1[i-1]==seq2[j-1])#match
            tempscore[1]=tempscore[1]+matchVal
          else#missmatch
            tempscore[1]=tempscore[1]+missmatchVal
        }
        #case horizontal move
        if (i>1)
          tempscore[2]=score[i-1,j]+indelVal
        #case vertical move
        if(j>1)
          tempscore[3]=score[i,j-1]+indelVal
        #select the best incoming edge
        score[i,j]=max(tempscore)
        #store backpointer using the following encoding: 1 --> match/mismatch 2--> insertion 3 --> deletion
        backpointer[i,j]=which(tempscore==max(tempscore))[1]
        }
    }
    
  }
  #printing the backpointer matrix in which 1--> diagonal 2-->horizontal 3--> vertical
  print(backpointer)
  #printing the score matrix
  print(score)
  #calling the function that prints the optimal alignment
  printAlignment(backpointer,seq1,seq2)
}


printAlignment=function(backpointer,seq1,seq2){
  
  size1=length(seq1)+1
  size2=length(seq2)+1 
  
  #starting from the bottom right corner
  i=size1
  j=size2
  #string vectors use to store the alignment
  output1=NULL
  output2=NULL
  while (i!=1 || j!=1){
    #case match or mismatch
    if (backpointer[i,j]==1){
      output1=c(seq2[j-1],output1)
      output2=c(seq1[i-1],output2)
      i=i-1
      j=j-1
    }
    else
      #case insertion
      if(backpointer[i,j]==2){
        output1=c("-",output1)
        output2=c(seq1[i-1],output2)
        i=i-1
      }
    else{
      #case delition
      output1=c(seq2[j-1],output1)
      output2=c("-",output2)
      j=j-1
    }  
    
  } 
  #print the alignment
  cat("\n",output1,"\n",output2,"\n")
}