/*****************************************************************************/ // travail : TP1 Q5 // auteur : Marc Blouin // description : permettre de trouver les alignements locaux de deux sequences // indentiques. // date : 28 jan 2003 // cours : ift3290 /*****************************************************************************/ // Utilisation java tp1b asdff asdff public class tp1b { private int tab[][]; String mySeq1, mySeq2; int nbSolPos =0; int myValMax=0; int myMatch=2; int myMis=-2; //les misMatch sont mis à -2 pour obtenir la solution TTATTC et TTACTC //pour l'exemple de la question 5 public static void main(String[] args) { if (args.length != 2){ System.out.println("il faut 2 parm vous avez : " + args.length); return; } tp1b unTp = new tp1b(args[0],args[1]); } public tp1b(String seq1, String seq2){ tab = new int[seq2.length() + 1][seq1.length() + 1]; mySeq1 = seq1; mySeq2 = seq2; remplirTout();//remplir le tableau de PD imprimer();//imprimer le tableau System.out.println("\n la valeur maximum est : " + myValMax); remonter(); //remonter pour trouver les solutions optimals } //imprime le tableau de PD public void imprimer(){ System.out.println(" " + mySeq1); for (int i = 0 ; i <= mySeq2.length();i++){ if (i != 0){ System.out.print("\n" + mySeq2.charAt(i-1) + " "); } else { System.out.print("\n "); } for (int j = 0 ; j <= mySeq1.length();j++){ System.out.print(" " + tab[i][j]); } } } //remonte le tableau au complet public void remonter(){ nbSolPos = 0; for (int i = 0 ; i <= mySeq2.length();i++){ for (int j = 0 ; j <= mySeq1.length();j++){ if (tab[i][j] == myValMax){ System.out.println("avec i = " + i + " et j = " + j ); remonte(i,j,"",""); } } } System.out.println("\nle nb sol opt : " + nbSolPos); } //remonte recursivement le tableau pour trouver tous les valeurs optimals public void remonte(int pos1, int pos2, String aStr1, String aStr2){ if (pos1 == 0 && pos2 == 0 || tab[pos1][pos2] == 0){ System.out.println("une solution possible : "); System.out.println(" chaine 1 : " + aStr1); System.out.println(" chaine 2 : " + aStr2 + "\n"); nbSolPos++; } else { if (pos1 != 0 && tab[pos1][pos2] == tab[pos1-1][pos2] + myMis){ remonte(pos1-1, pos2, (" ").concat(aStr1), (mySeq2.substring(pos1-1, pos1)).concat(aStr2)); } //ici on remarque le pos1 != pos2, pour ne pas permettre de faire //d'association avec sa prope valeur. if (pos1 != 0 && pos2 != 0 && pos1 != pos2 && (tab[pos1][pos2] == tab[pos1-1][pos2-1] + myMis || (tab[pos1][pos2] == tab[pos1-1][pos2-1] + myMatch && mySeq1.charAt(pos2-1) == mySeq2.charAt(pos1-1)) ) ){ remonte(pos1-1, pos2-1, (mySeq1.substring(pos2-1, pos2)).concat(aStr1), mySeq2.substring(pos1-1, pos1).concat(aStr2)); } if (pos2 != 0 && tab[pos1][pos2] == tab[pos1][pos2-1] + myMis){ remonte(pos1, pos2-1, (mySeq1.substring(pos2-1, pos2)).concat(aStr1), (" ").concat(aStr2)); } } } //remplit les côtés du tableau avec des zeros. public void remplirCote(){ tab[0][0] = 0; for (int i = 1 ; i <= mySeq1.length(); i++){ tab[0][i] = 0; } for (int i = 1 ; i <= mySeq2.length(); i++){ tab[i][0] = 0; } } //remplit chacune des cases avec la valeur optimal public void remplir(int pos1, int pos2){ int valmax = 0; if (tab[pos1-1][pos2] + myMis > valmax){ valmax = tab[pos1-1][pos2] + myMis; } if (tab[pos1][pos2-1] + myMis > valmax){ valmax = tab[pos1][pos2-1] + myMis; } int isMatch = myMis; //ici aussi on ne permet pas de faire un match entre deux caractère à la même //position (pos1 != pos2) if (mySeq1.charAt(pos2-1) == mySeq2.charAt(pos1-1) && pos1 != pos2){ isMatch = myMatch; } if (tab[pos1-1][pos2-1] + isMatch > valmax){ valmax = tab[pos1-1][pos2-1] + isMatch; } tab[pos1][pos2] = valmax; if (myValMax < valmax){ myValMax = valmax; } } //remplit le tableau de PD public void remplirTout(){ remplirCote(); for (int i = 1 ; i <= mySeq2.length();i++){ for (int j = 1 ; j <= mySeq1.length();j++){ remplir(i,j); } } } }