|
NeoBio API | ||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Object | +--neobio.alignment.PairwiseAlignmentAlgorithm | +--neobio.alignment.CrochemoreLandauZivUkelson | +--neobio.alignment.CrochemoreLandauZivUkelsonLocalAlignment
This class implements the local 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:
createBlock
and its variants);
computeOutputBorder
;
locateScore
;
buildOptimalAlignment
.
This algorithm works essentially in the same way as the global alignment version. The main differences is that an aptimal path can either be contained entirely in a block (called C-path) or be a block-crossing path. A block-crossing path consists of a (possibly empty) S-path (a path that starts inside a block and ends in its output border), followed by any number of paths that cross a block from its input border to its output border, and ending in an E-path (a path that starts in the input border of a block and ends inside the block).
Therefore, it is necessary to compute extra information to keep track of these possibilities. This is accomplished by using an instance of a LocalAlignmentBlock (which extends the AlignmentBlock class) for every block in the block table.
CrochemoreLandauZivUkelson
,
CrochemoreLandauZivUkelsonLocalAlignment
Field Summary | |
protected int |
max_col
The column index of a block (in the block table) where the high scoring local alignment ends. |
protected byte |
max_path_type
The type of the high scoring local alignment found. |
protected int |
max_row
The row index of a block (in the block table) where the high scoring local alignment ends. |
protected int |
max_score
The score of the high scoring local alignment found. |
protected int |
max_source_index
If the high scoring local alignment ends in an E-path at a block B, this field contains the index of the entry in the input border of B that where the E-path starts. |
protected static byte |
TYPE_C_PATH
A constant that indicates that the high scoring path ending in a given block is a C-path, i.e. one that starts inside the block. |
protected static byte |
TYPE_CROSSING_PATH
A constant that indicates that the best path ending at a given entry of the output border is a block-crossing path (one that starts outside the block). |
protected static byte |
TYPE_E_PATH
A constant that indicates that the high scoring path ending in a given block is an E-path, i.e. one that starts at its input border. |
protected static byte |
TYPE_S_PATH
A constant that indicates that the best path ending at a given entry of the output border is a S-path (one that starts inside the block). |
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 | |
CrochemoreLandauZivUkelsonLocalAlignment()
|
Method Summary | |
protected PairwiseAlignment |
buildOptimalAlignment()
Builds an optimal local alignment between the loaded sequences after the block table has been computed by tracing a path back in the block table. |
protected void |
computeOutputBorder(LocalAlignmentBlock 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 column of the block table. |
protected AlignmentBlock |
createRootBlock(Factor factor1,
Factor factor2)
Creates the root block. |
protected int |
locateScore()
Returns the score of the high scoring local alignment in the block table. |
protected void |
traverseBlockCrossingPath(LocalAlignmentBlock block,
java.lang.StringBuffer gapped_seq1,
java.lang.StringBuffer tag_line,
java.lang.StringBuffer gapped_seq2)
Traverses a series of block crossing paths to retrieve an optimal alignment. |
protected void |
traverseS_Path(LocalAlignmentBlock block,
java.lang.StringBuffer gapped_seq1,
java.lang.StringBuffer tag_line,
java.lang.StringBuffer gapped_seq2)
Traverses an S-path of a block to retrieve a part of an optimal alignment from the new vertex of a block to entry in its input border. |
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 |
Field Detail |
protected static final byte TYPE_CROSSING_PATH
protected static final byte TYPE_S_PATH
protected static final byte TYPE_C_PATH
protected static final byte TYPE_E_PATH
protected int max_score
protected int max_row
protected int max_col
protected byte max_path_type
protected int max_source_index
Constructor Detail |
public CrochemoreLandauZivUkelsonLocalAlignment()
Method Detail |
protected AlignmentBlock createBlock(Factor factor1, Factor factor2, int row, int col) throws IncompatibleScoringSchemeException
computeOutputBorder
method to compute the block's output border. It
also computes all S, C and E-paths of this block. Finally, it checks if the C-path
of this block is higher than the highest score found so far.
createBlock
in class CrochemoreLandauZivUkelson
factor1
- factor of the first sequencefactor2
- factor of the second sequencerow
- row index of the block in the block tablecol
- column index of the block in the block table
IncompatibleScoringSchemeException
- if the scoring scheme is not compatible
with the sequences being alignedprotected AlignmentBlock createRootBlock(Factor factor1, Factor factor2)
createBlock
method. No information is actually computed.
createRootBlock
in class CrochemoreLandauZivUkelson
factor1
- factor of the first sequencefactor2
- factor of the second sequence
protected AlignmentBlock createFirstRowBlock(Factor factor1, Factor factor2, int col) throws IncompatibleScoringSchemeException
createBlock
method.
createFirstRowBlock
in class CrochemoreLandauZivUkelson
factor1
- factor of the first sequencefactor2
- factor of the second sequencecol
- column index of the block in the block table
IncompatibleScoringSchemeException
- if the scoring scheme is not compatible
with the sequences being alignedcreateBlock
protected AlignmentBlock createFirstColumnBlock(Factor factor1, Factor factor2, int row) throws IncompatibleScoringSchemeException
createBlock
method.
createFirstColumnBlock
in class CrochemoreLandauZivUkelson
factor1
- factor of the first sequencefactor2
- factor of the second sequencerow
- row index of the block in the block table
IncompatibleScoringSchemeException
- if the scoring scheme is not compatible
with the sequences being alignedcreateBlock
protected void computeOutputBorder(LocalAlignmentBlock block, int row, int col, int dim, int lc, int lr)
However, it also check if there is a better path starting inside the block (an S path) and oupdate the output border accordingly. It also checks if this block has any path of score higher than the maximum score found so far.
block
- the block for which the output border is to be computedrow
- row index of the block in the block tablecol
- column index of the block in the block tabledim
- dimension of the output borderlc
- number of columns of the blocklr
- number of row of the blockprotected PairwiseAlignment buildOptimalAlignment() throws IncompatibleScoringSchemeException
buildOptimalAlignment
in class CrochemoreLandauZivUkelson
IncompatibleScoringSchemeException
- If the scoring scheme is not compatible
with the loaded sequences.CrochemoreLandauZivUkelson.traverseBlock(neobio.alignment.AlignmentBlock, int, java.lang.StringBuffer, java.lang.StringBuffer, java.lang.StringBuffer)
protected void traverseBlockCrossingPath(LocalAlignmentBlock block, java.lang.StringBuffer gapped_seq1, java.lang.StringBuffer tag_line, java.lang.StringBuffer gapped_seq2) throws IncompatibleScoringSchemeException
block
- the block to be traversedgapped_seq1
- the StringBuffer to where the gapped sequence 1 is written totag_line
- the StringBuffer to where the tag_line is written togapped_seq2
- the StringBuffer to where the gapped sequence 2 is written to
IncompatibleScoringSchemeException
- If the scoring scheme is not compatible
with the loaded sequences.protected void traverseS_Path(LocalAlignmentBlock block, java.lang.StringBuffer gapped_seq1, java.lang.StringBuffer tag_line, java.lang.StringBuffer gapped_seq2) throws IncompatibleScoringSchemeException
traverseBlock
. The only difference is that it uses
the information of the S_direction field
of the
LocalAlignmentBlock
class.
block
- the block to be traversedgapped_seq1
- the StringBuffer to where the gapped sequence 1 is written totag_line
- the StringBuffer to where the tag_line is written togapped_seq2
- the StringBuffer to where the gapped sequence 2 is written to
IncompatibleScoringSchemeException
- If the scoring scheme is not compatible
with the loaded sequences.protected int locateScore()
locateScore
in class CrochemoreLandauZivUkelson
|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |