# Alignement algorithm

I have a code to write for school, based on Needleman&Wunsch alignment algorithm. I wrote the algorithm based on what the teacher told us, so maybe not 100% same as Needleman&Wunsch algorithm.

I connect to a database, get 2 strings, and work with them. I'm creating a matrix, size [n+1][n+1] first row and line initialized with gaps (-1).

``````public  String[] AlgoNeedWunsch(){ //construction de la matrice (initialisation des gap puis comparaison)
int i,j, init = 0;
StringBuilder aligne1 = new StringBuilder();
StringBuilder aligne2 = new StringBuilder();

matrice = new int[sequence1.length()+1][sequence2.length()+1];

for(i = 0; i < sequence1.length()+1; i++){
matrice[i] =  init;
init --;
}

for(i = 0, init = 0; i < sequence2.length()+1; i++){
matrice[i] = init;
init --;
}

for(i = 1; i <= sequence1.length(); i++){
for(j = 1; j <= sequence2.length(); j++){
if(sequence1.charAt(i-1) == sequence2.charAt(j-1)){
matrice[i][j] = matrice[i-1][j-1] + 1; // si match, on ajoute le socre diag +1
}
else{
if(matrice[i-1][j] > matrice[i][j-1])
matrice[i][j] = matrice[i-1][j]-1;
else
matrice[i][j] = matrice[i][j-1]-1;
}
}
}

//debut de l'alignement

for(i = sequence1.length(), j = sequence2.length(); i > 0 || j > 0;){
if(i > 0 && matrice[i][j] == matrice[i-1][j] + 1){
aligne1.append(sequence1.charAt(i-1));
aligne2.append("-");
i--;

}
else if(j > 0 && matrice[i][j] == matrice[i][j-1] + 1){
aligne2.append(sequence2.charAt(j-1));
aligne1.append("-");
j--;

}
else if(i > 0 && j > 0 && matrice[i][j] == matrice[i-1][j-1]){
aligne1.append(sequence1.charAt(i-1));
aligne2.append(sequence2.charAt(j-1));
i--;
j--;
}
}

return new String[]{aligne1.reverse().toString(), aligne2.reverse().toString()};
}
}
``````

But when i try to run this, it looks like it never ends. I'm beginner in Java so i don't know if i'm missing something, or is it just a problem in my algorithm. On On