neobio.alignment
Class CrochemoreLandauZivUkelsonGlobalAlignment

java.lang.Object
  |
  +--neobio.alignment.PairwiseAlignmentAlgorithm
        |
        +--neobio.alignment.CrochemoreLandauZivUkelson
              |
              +--neobio.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.

Author:

Sergio A. de Carvalho Jr.

See Also:

CrochemoreLandauZivUkelson, CrochemoreLandauZivUkelsonLocalAlignment

Field Summary

Fields inherited from class neobio.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 neobio.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 neobio.alignment.CrochemoreLandauZivUkelson

assembleDistMatrix, assembleInputBorder, computeBlockTable, computePairwiseAlignment, computeScore, getDiagonalPrefix, getLeftPrefix, getTopPrefix, loadSequencesInternal, traverseBlock, unloadSequencesInternal

Methods inherited from class neobio.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(neobio.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