Algorithm explanation

[Akilah712]

Hi,

I am writing a program for a bioinformatics class. I have to implement a certain algorithm. I am a biologist and my background in programming is not that great. I have found the algorithm online that I want to implement but I need it explained in regular terms. The algorithm is as follows:

for i=0 to length(A)-1
    F(i,0) <- d*i
  for j=0 to length(B)-1
    F(0,j) <- d*j
  for i=1 to length(A)
    for j = 1 to length(B)
    {
      Choice1 <- F(i-1,j-1) + S(A(i-1), B(j-1))
      Choice2 <- F(i-1, j) + d
      Choice3 <- F(i, j-1) + d
      F(i,j) <- max(Choice1, Choice2, Choice3)
    }

[lucky1981_iway]

Post full algorithm so we can explain you correctly.
In the above snippet , if i'm understanding correctly then you are drawing something with this on screen. For that you are assigning coordinates values.

1) In 1st for loop you are setting x-coordinates keeping y constant

f(0,0) = d * 0
f(1,0) = d * 1
.
.
.
f((length(A)-1) , 0) =  d * (length(A)-1)

2) in 2nd for loop you are doing same as step 1 but here you are keeping x constant and setting valus for y coordinates

f(0,0) = d * 0
f(0,1) = d * 1
.
.
.
f(0 , (length(B)-1)) =  d * (length(B)-1)

3) The 3rd and 4th for loop you will be using simultaneously to assign values to points between X and Y axis . If you look at the 1st and 2 nd steps then you will find that first you traversed through X axis ( i.e. Y = 0) and then along Y axis ( i.e X = 0). Now you are traversing between X( x >= 1 and x< length(A-1)) and Y( Y >= 1 and Y< length(B-1)) axis.

For each value of X( from 1 to length(A) -1) do
Begin
   For each value of Y( from 1 to length(B) -1) do
   Begin
       1 ) get value of choice 1, choice 2 & choice 3 
       2)  find maximum form choice 1 , choice 2 and choice 3 
       3) assign maximum value to f(i,j)
   End
End

Hope it will be helpful to you.

[Akilah712]

Thanks that helped a lot. I am just not used to the short hand stuff yet.

The rest of the algorithm is as follows:

AlignmentA <- ""
  AlignmentB <- ""
  i <- length(A)
  j <- length(B)
  while (i > 0 AND j > 0)
  {
    Score <- F(i,j)
    ScoreDiag <- F(i - 1, j - 1)
    ScoreUp <- F(i, j - 1)
    ScoreLeft <- F(i - 1, j)
    if (Score == ScoreDiag + S(A(i-1), B(j-1)))
    {
      AlignmentA <- A(i-1) + AlignmentA
      AlignmentB <- B(j-1) + AlignmentB
      i <- i - 1
      j <- j - 1
    }
    else if (Score == ScoreLeft + d)
    {
      AlignmentA <- A(i-1) + AlignmentA
      AlignmentB <- "-" + AlignmentB
      i <- i - 1
    }
    otherwise (Score == ScoreUp + d)
    {
      AlignmentA <- "-" + AlignmentA
      AlignmentB <- B(j-1) + AlignmentB
      j <- j - 1
    }
  }
  while (i > 0)
  {
    AlignmentA <- A(i-1) + AlignmentA
    AlignmentB <- "-" + AlignmentB
    i <- i - 1
  }
  while (j > 0)
  {
    AlignmentA <- "-" + AlignmentA
    AlignmentB <- B(j-1) + AlignmentB
    j <- j - 1
  }