gistfile1.java

import java.util.Arrays;


public class alignment {

	public static int D= 1;
	public static int MATCH = 2;
	public static int MISMATCH = -1;

	public static void main(String[] args){
		//	int[][] foo = computeMatrix(Sequenzen.NP_000913, Sequenzen.NP_246273);
		//	System.out.println(foo[1][1]);
		String seq1 = "IVLTAAHCVSASGEHN";
		String seq2 = "IVVGSAAHCYGEDN";
		int[][] bar = computeMatrix("IVLTAAHCVSASGEHN", "IVVGSAAHCYGEDN");

		System.out.println(bar[1][1]);

		//	printmatrix(bar);



		int[][] foo = new int[seq1.length()][seq2.length()];

		for(int i=0; i<seq1.length(); i++){
			for (int j=0; j<seq2.length(); j++){
				foo[i][j]= bar[i+1][j+1];
			}
		}
		//System.out.println(Arrays.deepToString(foo));

		printAlignment(bar, seq1, seq2);

	}

	public static void printmatrix(int[][]matrix){
		for(int i = 1; i < matrix.length; i++){
			for (int j = 1; j < matrix[1].length; j++){
				System.out.print(matrix[i][j]+"\t");	
			}
			System.out.print("\n");
		}
	}
	public static int[][] computeMatrix(String seq1, String seq2){
		seq1 = " " + seq1;
		seq2 = " " + seq2;
		int[][] matrix = new int[seq1.length()+1][seq2.length()+1];

		for(int i = seq1.length()-1; i>0; i--){
			for(int j=seq2.length()-1; j>0; j--){
				matrix[i][j] = max(matrix, i, j, seq1, seq2);
			}
		}
		return matrix;
	}

	public static int max(int[][] matrix, int i, int j, String seq1, String seq2){
		char[] a = StringToArray(seq1);
		char[] b = StringToArray(seq2);
		int [] foo = {matrix[i][j]+s(matrix, a, b, i, j), matrix[i+1][j] -D , matrix[i][j+1] -D};

		Arrays.sort(foo);
		return foo[foo.length-1];
	}

	public static char[] StringToArray(String s){
		char[] foo = new char[s.length()+1];
		for(int i=0; i<s.length();i++){
			foo[i+1] = s.charAt(i);
		}
		return foo;
	}

	private static int s(int[][] matrix, char[] seq1, char[] seq2, int i, int j) {
		if(seq1[i] == seq2[j]){
			return matrix[i+1][j+1] + MATCH;		
		}
		else {
			return matrix[i+1][j+1] + MISMATCH;
		}

	}

	public static void printAlignment(int[][] matrix, String seq1, String seq2)
	{
		char[] a = StringToArray(seq1);
		char[] b = StringToArray(seq2);
		String alignment1 = "";
		String alignment2 = "";        

		int i = seq1.length()-1;
		int j = seq2.length()-1;

		while (i > 0 && j > 0){
			int score = matrix[i][j];
			int scoreDiag = matrix[i-1][j-1];
			int scoreUp = matrix[i][j-1];
			int scoreLeft = matrix[i-1][j];

			if (score == scoreDiag + s(matrix,a, b, i, j )){
				alignment1 = seq1.charAt(i-1) + alignment1;
				alignment2 = seq2.charAt(j-1) + alignment2;
				i--;
				j--;                
			}
			else if (score == scoreLeft + D){
				alignment1 = seq1.charAt(i-1) + alignment1;
				alignment2 = "_" + alignment2;
				i--;
			}
			else if(score == scoreUp + D){
				alignment1 = "_" + alignment1;
				alignment2 = seq2.charAt(j-1) + alignment2;
				j--;
			} 
		}
		while(i > 0){
			alignment1 = seq1.charAt(i - 1) + alignment1;
			alignment2 = "_" + alignment2;
			i--;            
		}
		while(j > 0){
			alignment1 = "_" + alignment1;
			alignment2 = seq2.charAt(j - 1) + alignment2;
			j--;            
		}
		System.out.println(alignment1);
		System.out.println(alignment2);
	}


}