nw.java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;


public class needlemanwunsch {

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

	public static void main(String[] args){

		int[][] bar = computeMatrix("IVLTAAHCVSASGEHN", "IVVGSAAHCYGEDN");
		//printmatrix(bar);
		printAlignment(bar, "IVLTAAHCVSASGEHN", "IVVGSAAHCYGEDN");
		
		int[][] foo = computeMatrix(Sequenzen.NP_000913, Sequenzen.NP_006194);
		printAlignment(foo,Sequenzen.NP_000913, Sequenzen.NP_006194);
	}

	public static int[][] computeMatrix(String seq1, String seq2){
		int[][] matrix = new int[seq1.length()][seq2.length()];

		
		//init von letzter zeile und spalte von 0 bis -seq length
		int x=0;
		for (int i=seq2.length()-1;i>=0;i--){
			matrix[seq1.length()-1][i]=-x++;
		}
		x=0;
		for (int i=seq1.length()-1;i>=0;i--){
			matrix[i][seq2.length()-1]=-x++;
		}
		


		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){
		ArrayList<Integer> foo = new ArrayList<Integer>();

		if(i==seq1.length()-1 && j==seq2.length()-1){
			return s(seq1, seq2, i, j);
		} else {

			try{
				foo.add((matrix[i+1][j+1]+s(seq1, seq2, i, j)));
			} catch(Exception e){
			}
			
			try{
				foo.add( matrix[i+1][j] -D);
			} catch(Exception e){
			}

			try{
				foo.add( matrix[i][j+1] -D);
			} catch(Exception e){
			}
			
			Collections.sort(foo);
			return foo.get(foo.size()-1);
		}
	}

	private static int s( String seq1, String seq2, int i, int j ) {
		if(seq1.charAt(i) == seq2.charAt(j))
			return MATCH;	
		else 
			return MISMATCH;

	}

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

	public static void printAlignment(int[][] matrix, String seq1, String seq2)
	{

		String alignment1 = "";
		String alignment2 = "";        

		int i = 0;
		int j = 0;

		while (i < seq1.length()-1 && j < seq2.length()-1){
			
			int score = matrix[i][j];
			int scoreDiag = matrix[i+1][j+1];
			int scoreRight = matrix[i][j+1];
			int scoreDown = matrix[i+1][j];

			if (score == scoreDiag + s(seq1, seq2, i, j ) ){
				alignment1 = alignment1 + seq1.charAt(i); 
				alignment2 = alignment2 + seq2.charAt(j) ;
				i++;
				j++;                
			}
			else if (score == scoreDown - D){
				alignment1 =  alignment1+seq1.charAt(i) ;
				alignment2 =   alignment2 + "_"  ;
				i++;
			}
			else if(score == scoreRight - D){
				alignment1 =   alignment1 + "_"  ;
				alignment2 = alignment2+seq2.charAt(j) ;
				j++;
			} 
		}
		
		while(i < seq1.length()){
			alignment1 = alignment1+seq1.charAt(i) ;
			//alignment2 = alignment2+ "_" ;
			i++;            
		}
		while(j < seq2.length()){
		//	alignment1 =  alignment1 + "_";
			alignment2 =  alignment2 + seq2.charAt(j ) ;
			j++;            
		}
		
		System.out.println(alignment1);
		System.out.println(alignment2);
	}


}