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)
}``````

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.

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
}``````
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.