Alignement algorithm

Asked by At

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][0] =  init;
        init --;
    }

    for(i = 0, init = 0; i < sequence2.length()+1; i++){
        matrice[0][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.

Thank you in advance for your help.

2 Answers

0
Gyrotank On

Looks like the second for-loop can run forever because all decrements of i and j it depends on are inside of the optional blocks and there is a risk they won't execute at all. I'd run the program step-by-step in debug mode and check if it's true and if so, when exactly it starts happening. Maybe there is some additional condition missing. Or just additional 'else' block with no conditions which always runs if all the previous checks failed.

0
Gag Baghdasarian On

I think that your code's infinite loop is the last 'FOR' statement. Put the logs into every if statement, and check , if the 'i' or 'j' is/are decreased.