org.jscience.biology.alignment
Class CrochemoreLandauZivUkelsonGlobalAlignment

java.lang.Object
  extended by org.jscience.biology.alignment.PairwiseAlignmentAlgorithm
      extended by org.jscience.biology.alignment.CrochemoreLandauZivUkelson
          extended by org.jscience.biology.alignment.CrochemoreLandauZivUkelsonGlobalAlignment

public class CrochemoreLandauZivUkelsonGlobalAlignment
extends CrochemoreLandauZivUkelson

This class implements the global pairwise sequence alignment algorithm (with linear gap penalty function) due to Maxime Crochemore, Gad Landau and Michal Ziv-Ukelson (2002).

This implementation derives from the paper of M.Crochemore, G.Landau and M.Ziv-Ukelson, A Sub-quadratic Sequence Alignment Algorithm for Unrestricted Scoring Matrices (available here as PDF or Postscript).

For a general description of the algorithm, please refer to the specification of the abstract CrochemoreLandauZivUkelson superclass.

This class consist mainly of methods that:

  • create and compute all information of a block (see createBlock and its variants);
  • compute the output border of a block (see computeOutputBorder;
  • locate the score of a high scoring global alignment in the block table (see locateScore;
  • build an optimal global alignment from the information stored in the block table (see buildOptimalAlignment.

    See Also:
    CrochemoreLandauZivUkelson, CrochemoreLandauZivUkelsonLocalAlignment

    Field Summary
     
    Fields inherited from class org.jscience.biology.alignment.CrochemoreLandauZivUkelson
    block_table, DIAGONAL_DIRECTION, LEFT_DIRECTION, num_cols, num_rows, out_matrix, seq1, seq2, smawk, STOP_DIRECTION, TOP_DIRECTION
     
    Fields inherited from class org.jscience.biology.alignment.PairwiseAlignmentAlgorithm
    alignment, APPROXIMATE_MATCH_TAG, GAP_CHARACTER, GAP_TAG, MATCH_TAG, MISMATCH_TAG, score, score_computed, scoring, sequences_loaded, use_match_tag
     
    Constructor Summary
    CrochemoreLandauZivUkelsonGlobalAlignment()
               
     
    Method Summary
    protected  PairwiseAlignment buildOptimalAlignment()
              Builds an optimal global alignment between the loaded sequences after the block table has been computed.
    protected  void computeOutputBorder(AlignmentBlock block, int row, int col, int dim, int lc, int lr)
              Computes the output border of a block.
    protected  AlignmentBlock createBlock(Factor factor1, Factor factor2, int row, int col)
              Creates and computes all information of an alignment block.
    protected  AlignmentBlock createFirstColumnBlock(Factor factor1, Factor factor2, int row)
              Creates and computes all information of an alignment block of the first column of the block table.
    protected  AlignmentBlock createFirstRowBlock(Factor factor1, Factor factor2, int col)
              Creates and computes all information of an alignment block of the first row of the block table.
    protected  AlignmentBlock createRootBlock(Factor factor1, Factor factor2)
              Creates the root block.
    protected  int locateScore()
              Locate the score of the highest scoring global alignment in the block table.
     
    Methods inherited from class org.jscience.biology.alignment.CrochemoreLandauZivUkelson
    assembleDistMatrix, assembleInputBorder, computeBlockTable, computePairwiseAlignment, computeScore, getDiagonalPrefix, getLeftPrefix, getTopPrefix, loadSequencesInternal, traverseBlock, unloadSequencesInternal
     
    Methods inherited from class org.jscience.biology.alignment.PairwiseAlignmentAlgorithm
    getPairwiseAlignment, getScore, loadSequences, max, max, max, scoreDeletion, scoreInsertion, scoreSubstitution, setScoringScheme, unloadSequences, useMatchTag
     
    Methods inherited from class java.lang.Object
    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
     

    Constructor Detail

    CrochemoreLandauZivUkelsonGlobalAlignment

    public CrochemoreLandauZivUkelsonGlobalAlignment()
    Method Detail

    createBlock

    protected AlignmentBlock createBlock(Factor factor1,
                                         Factor factor2,
                                         int row,
                                         int col)
                                  throws IncompatibleScoringSchemeException
    Creates and computes all information of an alignment block. Its main job is to compute the DIST column for the block. It then request the computeOutputBorder method to compute the block's output border.

    Specified by:
    createBlock in class CrochemoreLandauZivUkelson
    Parameters:
    factor1 - factor of the first sequence
    factor2 - factor of the second sequence
    row - row index of the block in the block table
    col - column index of the block in the block table
    Returns:
    the computed block
    Throws:
    IncompatibleScoringSchemeException - if the scoring scheme is not compatible with the sequences being aligned

    createRootBlock

    protected AlignmentBlock createRootBlock(Factor factor1,
                                             Factor factor2)
    Creates the root block. This is a special case of the createBlock method. No information is actually computed.

    Specified by:
    createRootBlock in class CrochemoreLandauZivUkelson
    Parameters:
    factor1 - factor of the first sequence
    factor2 - factor of the second sequence
    Returns:
    the root block

    createFirstRowBlock

    protected AlignmentBlock createFirstRowBlock(Factor factor1,
                                                 Factor factor2,
                                                 int col)
                                          throws IncompatibleScoringSchemeException
    Creates and computes all information of an alignment block of the first row of the block table. This is a special case of the createBlock method.

    Specified by:
    createFirstRowBlock in class CrochemoreLandauZivUkelson
    Parameters:
    factor1 - factor of the first sequence
    factor2 - factor of the second sequence
    col - column index of the block in the block table
    Returns:
    the computed block
    Throws:
    IncompatibleScoringSchemeException - if the scoring scheme is not compatible with the sequences being aligned
    See Also:
    createBlock

    createFirstColumnBlock

    protected AlignmentBlock createFirstColumnBlock(Factor factor1,
                                                    Factor factor2,
                                                    int row)
                                             throws IncompatibleScoringSchemeException
    Creates and computes all information of an alignment block of the first column of the block table. This is a special case of the createBlock method.

    Specified by:
    createFirstColumnBlock in class CrochemoreLandauZivUkelson
    Parameters:
    factor1 - factor of the first sequence
    factor2 - factor of the second sequence
    row - row index of the block in the block table
    Returns:
    the computed block
    Throws:
    IncompatibleScoringSchemeException - if the scoring scheme is not compatible with the sequences being aligned
    See Also:
    createBlock

    computeOutputBorder

    protected void computeOutputBorder(AlignmentBlock block,
                                       int row,
                                       int col,
                                       int dim,
                                       int lc,
                                       int lr)
    Computes the output border of a block. This is performed in five steps:

  • Retrieve the block's input border;
  • Retrieve the block's complete DIST matrix;
  • Create an interface to the OUT matrix from the input border and DIST matrix;
  • Use SMAWK to compute all column maxima of the OUT matrix (SMAWK finds the index of the row that contains the maximum value of a column);
  • Assemble the output border by extracting the maximum values of each column of the OUT matrix using the information obtained in the previous step.

    Parameters:
    block - the block for which the output border is to be computed
    row - row index of the block in the block table
    col - column index of the block in the block table
    dim - dimension of the output border
    lc - number of columns of the block
    lr - number of row of the block

  • buildOptimalAlignment

    protected PairwiseAlignment buildOptimalAlignment()
                                               throws IncompatibleScoringSchemeException
    Builds an optimal global alignment between the loaded sequences after the block table has been computed. This method traces a path back in the block table, from the last block to the first.

    Specified by:
    buildOptimalAlignment in class CrochemoreLandauZivUkelson
    Returns:
    an optimal global alignment
    Throws:
    IncompatibleScoringSchemeException - If the scoring scheme is not compatible with the loaded sequences.
    See Also:
    CrochemoreLandauZivUkelson.traverseBlock(org.jscience.biology.alignment.AlignmentBlock, int, java.lang.StringBuffer, java.lang.StringBuffer, java.lang.StringBuffer)

    locateScore

    protected int locateScore()
    Locate the score of the highest scoring global alignment in the block table. This value is found in the output border of the last block (last row, last column).

    Specified by:
    locateScore in class CrochemoreLandauZivUkelson
    Returns:
    the score of the highest scoring global alignment