HuntMacllory Algorithm Java Implementation

	package com.company.samples.way8;
	import java.util.Arrays;
	/**
	* G C A C G C T G G C A C G C T G <= SJ
	* 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
	* G 0 1 1 1 1 1 1 1 1 G 0 1 1 0 0 0 0 0 0
	* A 0 1 1 2 2 2 2 2 2 A 0 0 0 1 0 0 0 0 0
	* C 0 1 2 2 3 3 3 3 3 C 0 0 0 0 1 0 0 0 0
	* G 0 1 2 2 3 4 4 4 4 SI=> G 0 0 0 0 0 1 0 0 0
	* C 0 1 2 2 3 4 5 5 5 C 0 0 0 0 0 0 1 1 0
	* G 0 1 2 2 3 4 5 5 6 G 0 0 0 0 0 0 0 0 1
	* C 0 1 2 2 3 4 5 5 6 C 0 0 0 0 0 0 0 0 1
	* G 0 1 2 2 3 4 5 5 6 G 0 0 0 0 0 0 0 0 1
	*
	S-i : G-ACGC-GCG
	S-j : GGCACGGC--
	*
	*/
	public class HuntMacllury {
	public static void main (String[] args) {
	String si = "GACGCGCG";
	String sj = "GCACGCTG";
	int[][] matrix = new int[si.length () + 1][sj.length () + 1];
	for (int i = 1; i < si.length () + 1; i++) {
	for (int j = 1; j < sj.length () + 1; j++) {
	if (si.charAt (i - 1) == sj.charAt (j - 1)) {
	matrix[i][j] = matrix[i - 1][j - 1] + 1;
	} else {
	matrix[i][j] = matrix[i - 1][j] > matrix[i][j - 1] ? matrix[i - 1][j] : matrix[i][j - 1];
	}
	}
	}
	printMatrix (matrix);
	int[][] directionMatrix = createDirectionMatrix (matrix);
	directionMatrix = getIncrementalDiagonalMatrix (matrix, directionMatrix, matrix.length - 1, matrix[0].length - 1);
	printMatrix (directionMatrix);
	printStringI (si, directionMatrix);
	printStringJ (sj, directionMatrix);
	}
	private static void printStringJ (String sj, int[][] directionMatrix) {
	System.out.print ("S-j : ");
	for (int j = 1; j < directionMatrix[0].length; j++) {
	boolean charPrinted = false;
	for (int i = 1; i < directionMatrix.length; i++) {
	if (directionMatrix[i][j] == 1) {
	if (!charPrinted) {
	System.out.print (sj.charAt (j - 1));
	} else {
	System.out.print ("-");
	}
	charPrinted = true;
	}
	}
	}
	System.out.println ("");
	}
	private static void printStringI (String si, int[][] directionMatrix) {
	System.out.print ("S-i : ");
	for (int i = 1; i < directionMatrix.length; i++) {
	boolean charPrinted = false;
	for (int j = 1; j < directionMatrix[0].length; j++) {
	if (directionMatrix[i][j] == 1) {
	if (!charPrinted) {
	System.out.print (si.charAt (i - 1));
	} else {
	System.out.print ("-");
	}
	charPrinted = true;
	}
	}
	}
	System.out.println ("");
	}
	private static void printMatrix (int[][] matrix) {
	for (int i = 0; i < matrix[0].length; i++) {
	for (int j = 0; j < matrix[0].length; j++) {
	System.out.print (matrix[i][j] + " ");
	}
	System.out.println ("");
	}
	System.out.println ("");
	}
	private static int[][] getIncrementalDiagonalMatrix (int[][] matrix, int[][] directionMatrix, int starti, int startj) {
	directionMatrix[starti][startj] = 1;
	if (starti == 1 && startj == 1) {
	return directionMatrix;
	}
	int i = starti;
	int j = startj;
	int left = matrix[i][j - 1];
	int up = matrix[i - 1][j];
	int diagon = matrix[i - 1][j - 1];
	if (diagon >= up && diagon >= left) {
	i--;
	j--;
	return getIncrementalDiagonalMatrix (matrix, directionMatrix, i, j);
	} else if (up > diagon && up > left) {
	i--;
	return getIncrementalDiagonalMatrix (matrix, directionMatrix, i, j);
	} else if (left > diagon && left > up) {
	j--;
	return getIncrementalDiagonalMatrix (matrix, directionMatrix, i, j);
	}
	return directionMatrix;
	}
	private static int[][] createDirectionMatrix (int[][] matrix) {
	int[][] directionMatrix = new int[matrix.length][matrix[0].length];
	for (int i = 0; i < matrix.length; i++) {
	Arrays.fill (directionMatrix[i], 0);
	}
	return directionMatrix;
	}
	}

view raw HuntMacllory hosted with ❤ by GitHub