// Programme d'alignement classique // (C) 2004 Michel Van Caneghem // Version 1 du dimanche 21 novembre 2004 import java.io.*; import java.util.*; /* * static void definitSimilarite() * Construit la matrice P et définit le gap * static StringBuffer lireSequence(String fileName) * Lecture d'une séquence d'ADN au format FASTA * static StringBuffer randomDNA(int n) { * Génération d'une séquence de longueur n aléatoire * static void verifieEtEcrit(String as, String at) * On recalcule le score et on écrit le résultat * static int calculeScore() * On calcule le score max, pour un alignement global entre s et t * On obtient comme résultat la matrice des scores * static void aligne0(int i, int j, String as, String at) { * L'alignement entre 2 séquences s et * A la fin de l'alignement, la procédure écrit est appelé * static void aligne() { * Aligne les 2 séquences s et t * Compteur et compteurMax servent à controler le nombre de solutions imprimées */ public class align { static Random alea= new Random(314159); static int[][] P; // Matrice de similarité static int gap; // Le coût du gap // Variables pour l'alignement static int scoreMax = 0; static int compteur = 0, compteurMax = 0; static String s, t; static int[][] A; // la matrice des scores // Construit la matrice P et définit le gap static void definitSimilarite() { P = new int[256][256]; gap = -8; for (int i = 0; i < 256; i++) for (int j = 0; j < 256; j++) P[i][j] = -1000000; P[(int)'A'][(int)'A'] = 5; P[(int)'C'][(int)'A'] = -4; P[(int)'A'][(int)'C'] = -4; P[(int)'C'][(int)'C'] = 5; P[(int)'A'][(int)'G'] = -4; P[(int)'C'][(int)'G'] = -4; P[(int)'A'][(int)'T'] = -4; P[(int)'C'][(int)'T'] = -4; P[(int)'A'][(int)'N'] = -2; P[(int)'C'][(int)'N'] = -2; P[(int)'G'][(int)'A'] = -4; P[(int)'T'][(int)'A'] = -4; P[(int)'G'][(int)'C'] = -4; P[(int)'T'][(int)'C'] = -4; P[(int)'G'][(int)'G'] = 5; P[(int)'T'][(int)'G'] = -4; P[(int)'G'][(int)'T'] = -4; P[(int)'T'][(int)'T'] = 5; P[(int)'G'][(int)'N'] = -2; P[(int)'T'][(int)'N'] = -2; P[(int)'N'][(int)'A'] = -2; P[(int)'N'][(int)'C'] = -2; P[(int)'N'][(int)'G'] = -2; P[(int)'N'][(int)'T'] = -2; P[(int)'N'][(int)'N'] = -1; } // Lecture d'une séquence d'ADN au format FASTA static StringBuffer lireSequence(String fileName) { StringBuffer s= new StringBuffer(""); String ligne, titre = ""; try { BufferedReader in= new BufferedReader(new FileReader(fileName)); titre= in.readLine(); // On saute la première ligne while ((ligne= in.readLine()) != null) { s= s.append(ligne); } in.close(); } catch (IOException e) { System.err.println(e); return new StringBuffer("error"); } //Statistiques sur la chaine lue System.out.println("\n" + titre); System.out.println("longueur = " + s.length()); int[] cumul= new int[5]; for (int i= 0; i < s.length(); i++) { char c= s.charAt(i); switch (c) { case 'A' : cumul[0]++; break; case 'C' : cumul[1]++; break; case 'G' : cumul[2]++; break; case 'T' : cumul[3]++; break; default : cumul[4]++; } } System.out.println("Nombre de A = " + cumul[0]); System.out.println("Nombre de C = " + cumul[1]); System.out.println("Nombre de G = " + cumul[2]); System.out.println("Nombre de T = " + cumul[3]); System.out.println("Autres = " + cumul[4]); return s; } // Génération d'une séquence de longueur n aléatoire static StringBuffer randomDNA(int n) { char[] bases= { 'A', 'C', 'G', 'T' }; StringBuffer adn = new StringBuffer(n); adn.setLength(n); System.out.println(adn.length()); for (int i= 0; i < adn.length(); i++) adn.setCharAt(i,bases[alea.nextInt(4)]); return adn; } // Le max de 3 valeurs private static int max3(int v1, int v2, int v3) { int max = v1; if (v2 > max) max = v2; if (v3 > max) max = v3; return max; } // On recalcule le score et on écrit le résultat static void verifieEtEcrit(String as, String at) { // on recalcule le score, pour vérifier si on n'a pas fait d'erreur int score = 0, nbGaps = 0, nbIdent = 0; for (int i = 0; i < as.length(); i++) { if (as.charAt(i) == '-' || at.charAt(i) == '-') {score += gap; nbGaps++;} else score += P[(int)as.charAt(i)][(int)at.charAt(i)]; if (as.charAt(i) == at.charAt(i)) nbIdent++; } if(score != scoreMax) System.out.println("Erreur : le score de l'alignement est faux"); System.out.println("score = " + score); System.out.println("Longueur de l'alignement = " + as.length()); System.out.println("Nombre d'identités = "+ nbIdent + " (" + (100*nbIdent/as.length()) +"%)"); System.out.println("Nombre de gaps = " + nbGaps + " (" + (100*nbGaps/as.length())+ "%)"); // Il faut ecrire les chaines à l'endroit maintenant int lineSize = 60; for (int i = 0; i < as.length(); i = i + lineSize) { String debut = i + " "; System.out.println(); System.out.print(debut.substring(0,5)); if (i + lineSize > as.length()) System.out.println(as.substring(i)); else System.out.println(as.substring(i, i + lineSize)); System.out.print(" "); for (int j = 0; j < lineSize && i + j < as.length(); j++) if (as.charAt(i+j) == at.charAt(i+j)) System.out.print(":"); else System.out.print(" "); System.out.println(); System.out.print(" "); if (i + lineSize > at.length()) System.out.println(at.substring(i)); else System.out.println(at.substring(i, i + lineSize)); } System.out.println(); } // On calcule le score max, pour un alignement global entre s et t // On obtient comme résultat la matrice des scores static int calculeScore() { int m = s.length(); int n = t.length(); // On calcule la valeur du score en construisant la matrice A for (int i = 0; i <= m; i++) A[i][0] = i * gap; for (int j = 0; j <= n; j++) A[0][j] = j * gap; for (int i = 1; i <= m; i++) for (int j = 1; j <= n; j++) A[i][j] = max3( A[i - 1][j] + gap, A[i- 1][j - 1] + P[(int)s.charAt(i - 1)][(int)t.charAt(j - 1)], A[i][j - 1] + gap); return A[m][n]; } // L'alignement entre 2 séquences s et // A la fin de l'alignement, la procédure écrit est appelé // Compteur et compteurMax servent à controler le nombre de solutions imprimées static void aligne0(int i, int j, String as, String at) { if (compteur >= compteurMax) return; if (i==0 && j==0) {verifieEtEcrit(as, at); compteur++; return;} // Cas 1 if (i > 0 && A[i][j] == A[i - 1][j] + gap) aligne0(i - 1, j, s.charAt(i-1) + as, "-" + at); // Cas 2 if (i > 0 && j > 0 && A[i][j] == A[i - 1][j - 1] + P[(int)s.charAt(i-1)][(int)t.charAt(j-1)] ) aligne0(i - 1, j - 1, s.charAt(i-1) + as, t.charAt(j-1) + at); // Cas 3 if (j > 0 && A[i][j] == A[i][j-1] + gap) aligne0(i, j - 1, "-" + as, t.charAt(j-1) + at); } // Aligne les 2 séquences s et t static void aligne() { A = new int[s.length() + 1][t.length() + 1]; // Matrice des scores scoreMax = calculeScore(); compteur = 0; compteurMax = 1; // On va se limiter au premier alignement aligne0(s.length(), t.length(), "", ""); } public static void main(String[] args) { definitSimilarite(); // Construit la matrice P et définit le gap s= lireSequence(args[0]).toString(); t= lireSequence(args[1]).toString(); aligne(); // aligne les séquence s et t } }