// Path: src/main/java/jaligner/matrix/Matrix.java
// public class Matrix implements Serializable {
// 	/**
// 	 * 
// 	 */
// 	private static final long serialVersionUID = 3833742170619524400L;
// 	
// 	/**
// 	 * The size of the scoring matrix. It is the number of the characters in the
// 	 * ASCII table. It is more than the 20 amino acids just to save the
// 	 * processing time of the mapping.
// 	 */
// 	public static final int SIZE = 127;
// 
// 	/**
// 	 * Matrix id (or name)
// 	 */
// 	private final String id;
// 
// 	/**
// 	 * Scores
// 	 */
// 	private final float[][] scores;
// 
// 	public Matrix(String id, float[][] scores) {
// 		this.id = id;
// 		this.scores = scores;
// 	}
// 
// 	/**
// 	 * @return Returns the id.
// 	 */
// 	public String getId() {
// 		return this.id;
// 	}
// 
// 	/**
// 	 * @return Returns the scores.
// 	 */
// 	public float[][] getScores() {
// 		return this.scores;
// 	}
// 
// 	/**
// 	 * 
// 	 * @param a
// 	 * @param b
// 	 * @return score
// 	 */
// 	public float getScore(char a, char b) {
// 		return this.scores[a][b];
// 	}
// }


import jaligner.matrix.Matrix;
/*
 * $Id: NeedlemanWunsch.java,v 1.4 2006/02/09 12:23:24 ahmed Exp $
 * 
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * as published by the Free Software Foundation; either version 2
 * of the License, or (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
 */

package jaligner;


/**
 * An implementation of the Needleman-Wunsch algorithm for biological global
 * pairwise sequence alignment.
 * 
 * <br>
 * Reference: <a
 * href="http://www.sbc.su.se/~per/molbioinfo2001/dynprog/adv_dynamic.html">Advanced
 * Dynamic Programming Tutorial</a>.
 * 
 * 
 * @author <a href="ahmed@users.sf.net">Ahmed Moustafa</a>
 */

public final class NeedlemanWunsch {
    /**
     * Hidden constructor
     */
    private NeedlemanWunsch() {
        super();
    }

    /**
     * Aligns two sequences by Needleman-Wunsch (global)
     * 
     * @param s1
     *            sequene #1 ({@link Sequence})
     * @param s2
     *            sequene #2 ({@link Sequence})
     * @param matrix
     *            scoring matrix ({@link Matrix})
     * @param gap
     *            open gap penalty
     * @return alignment object contains the two aligned sequences, the
     *         alignment score and alignment statistics
     * @see Sequence
     * @see Matrix
     */
    public static Alignment align(Sequence s1, Sequence s2, Matrix matrix,
            float gap) {
        float[][] scores = matrix.getScores();

        int m = s1.length() + 1;
        int n = s2.length() + 1;

        byte[][] pointers = new byte[m][n];

        // Initializes the element (0,0) of the traceback matrix to STOP.
        pointers[0][0] = Directions.STOP;

        // Initializes the boundaries of the traceback matrix.
        for (int i = 1; i < m; i++) {
            pointers[i][0] = Directions.UP;
        }
        for (int j = 1; j < n; j++) {
            pointers[0][j] = Directions.LEFT;
        }

        Cell cell = construct(s1, s2, scores, gap, pointers);
        Alignment alignment = traceback(s1, s2, matrix, pointers, cell);

        alignment.setOriginalSequence1(s1);
        alignment.setOriginalSequence2(s2);
        alignment.setMatrix(matrix);
        alignment.setOpen(gap);
        alignment.setExtend(gap);

// Path: src/main/java/jaligner/matrix/Matrix.java
// public class Matrix implements Serializable {
// 	/**
// 	 * 
// 	 */
// 	private static final long serialVersionUID = 3833742170619524400L;
// 	
// 	/**
// 	 * The size of the scoring matrix. It is the number of the characters in the
// 	 * ASCII table. It is more than the 20 amino acids just to save the
// 	 * processing time of the mapping.
// 	 */
// 	public static final int SIZE = 127;
// 
// 	/**
// 	 * Matrix id (or name)
// 	 */
// 	private final String id;
// 
// 	/**
// 	 * Scores
// 	 */
// 	private final float[][] scores;
// 
// 	public Matrix(String id, float[][] scores) {
// 		this.id = id;
// 		this.scores = scores;
// 	}
// 
// 	/**
// 	 * @return Returns the id.
// 	 */
// 	public String getId() {
// 		return this.id;
// 	}
// 
// 	/**
// 	 * @return Returns the scores.
// 	 */
// 	public float[][] getScores() {
// 		return this.scores;
// 	}
// 
// 	/**
// 	 * 
// 	 * @param a
// 	 * @param b
// 	 * @return score
// 	 */
// 	public float getScore(char a, char b) {
// 		return this.scores[a][b];
// 	}
// }


// Path: src/main/java/jaligner/NeedlemanWunsch.java
import jaligner.matrix.Matrix;

/*
 * $Id: NeedlemanWunsch.java,v 1.4 2006/02/09 12:23:24 ahmed Exp $
 * 
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * as published by the Free Software Foundation; either version 2
 * of the License, or (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
 */

package jaligner;


/**
 * An implementation of the Needleman-Wunsch algorithm for biological global
 * pairwise sequence alignment.
 * 
 * <br>
 * Reference: <a
 * href="http://www.sbc.su.se/~per/molbioinfo2001/dynprog/adv_dynamic.html">Advanced
 * Dynamic Programming Tutorial</a>.
 * 
 * 
 * @author <a href="ahmed@users.sf.net">Ahmed Moustafa</a>
 */

public final class NeedlemanWunsch {
    /**
     * Hidden constructor
     */
    private NeedlemanWunsch() {
        super();
    }

    /**
     * Aligns two sequences by Needleman-Wunsch (global)
     * 
     * @param s1
     *            sequene #1 ({@link Sequence})
     * @param s2
     *            sequene #2 ({@link Sequence})
     * @param matrix
     *            scoring matrix ({@link Matrix})
     * @param gap
     *            open gap penalty
     * @return alignment object contains the two aligned sequences, the
     *         alignment score and alignment statistics
     * @see Sequence
     * @see Matrix
     */
    public static Alignment align(Sequence s1, Sequence s2, Matrix matrix,
            float gap) {
        float[][] scores = matrix.getScores();

        int m = s1.length() + 1;
        int n = s2.length() + 1;

        byte[][] pointers = new byte[m][n];

        // Initializes the element (0,0) of the traceback matrix to STOP.
        pointers[0][0] = Directions.STOP;

        // Initializes the boundaries of the traceback matrix.
        for (int i = 1; i < m; i++) {
            pointers[i][0] = Directions.UP;
        }
        for (int j = 1; j < n; j++) {
            pointers[0][j] = Directions.LEFT;
        }

        Cell cell = construct(s1, s2, scores, gap, pointers);
        Alignment alignment = traceback(s1, s2, matrix, pointers, cell);

        alignment.setOriginalSequence1(s1);
        alignment.setOriginalSequence2(s2);
        alignment.setMatrix(matrix);
        alignment.setOpen(gap);
        alignment.setExtend(gap);

        if (s1.getId() != null) {