Package org.biojava.bio.alignment
Class NeedlemanWunsch
java.lang.Object
org.biojava.bio.alignment.AlignmentAlgorithm
org.biojava.bio.alignment.NeedlemanWunsch
Needleman and Wunsch defined the problem of global sequence alignments, from
the first till the last symbol of a sequence. This class is able to perform
such global sequence comparisons efficiently by dynamic programming. If
inserts and deletes are equally expensive and as expensive as the extension
of a gap, the alignment method of this class does not use affine gap
penalties. Otherwise it does. Those costs need four times as much memory,
which has significant effects on the run time, if the computer needs to swap.
- Since:
- 1.5
- Author:
- Andreas Dräger, Gero Greiner, Mark Schreiber
-
Field Summary
FieldsModifier and TypeFieldDescriptionprotected int[][]
A matrix with the size length(sequence1) times length(sequence2)protected SubstitutionMatrix
A matrix with the size length(alphabet) times length(alphabet) -
Constructor Summary
ConstructorsConstructorDescriptionNeedlemanWunsch
(short match, short replace, short insert, short delete, short gapExtend, SubstitutionMatrix subMat) Constructs a new Object with the given parameters based on the Needleman-Wunsch algorithm The alphabet of sequences to be aligned will be taken from the given substitution matrix. -
Method Summary
Modifier and TypeMethodDescriptionshort
Returns the current expenses of a single delete operation.int
This gives the edit distance according to the given parameters of this certain object.short
Returns the current expenses of any extension of a gap operation.short
Returns the current expenses of a single insert operation.short
getMatch()
Returns the current expenses of a single match operation.short
Returns the current expenses of a single replace operation.protected static int
min
(int x, int y, int z) This just computes the minimum of three integer values.pairwiseAlignment
(SymbolList query, SymbolList subject) Global pairwise sequence alignment of two BioJava-Sequence objects according to the Needleman-Wunsch-algorithm.static String
printCostMatrix
(int[][] CostMatrix, char[] queryChar, char[] targetChar) Prints a String representation of the CostMatrix for the given Alignment on the screen.void
setDelete
(short del) Sets the penalty for a delete operation to the specified value.void
setGapExt
(short ge) Sets the penalty for an extension of any gap (insert or delete) to the specified value.void
setInsert
(short ins) Sets the penalty for an insert operation to the specified value.void
setMatch
(short ma) Sets the penalty for a match operation to the specified value.void
setReplace
(short rep) Sets the penalty for a replace operation to the specified value.void
Sets the substitution matrix to be used to the specified one.Methods inherited from class org.biojava.bio.alignment.AlignmentAlgorithm
alignAll
-
Field Details
-
CostMatrix
A matrix with the size length(sequence1) times length(sequence2) -
subMatrix
A matrix with the size length(alphabet) times length(alphabet)
-
-
Constructor Details
-
NeedlemanWunsch
public NeedlemanWunsch(short match, short replace, short insert, short delete, short gapExtend, SubstitutionMatrix subMat) Constructs a new Object with the given parameters based on the Needleman-Wunsch algorithm The alphabet of sequences to be aligned will be taken from the given substitution matrix.- Parameters:
match
- This gives the costs for a match operation. It is only used, if there is no entry for a certain match of two symbols in the substitution matrix (default value).replace
- This is like the match parameter just the default, if there is no entry in the substitution matrix object.insert
- The costs of a single insert operation.delete
- The expenses of a single delete operation.gapExtend
- The expenses of an extension of a existing gap (that is a previous insert or delete. If the costs for insert and delete are equal and also equal to gapExtend, no affine gap penalties will be used, which saves a significant amount of memory.subMat
- The substitution matrix object which gives the costs for matches and replaces.
-
-
Method Details
-
min
This just computes the minimum of three integer values.- Parameters:
x
-y
-z
-- Returns:
- Gives the minimum of three integers
-
printCostMatrix
Prints a String representation of the CostMatrix for the given Alignment on the screen. This can be used to get a better understanding of the algorithm. There is no other purpose. This method also works for all extensions of this class with all kinds of matrices.- Parameters:
CostMatrix
- The matrix that contains all expenses for swapping symbols.queryChar
- a character representation of the query sequence (mySequence.seqString().toCharArray()
).targetChar
- a character representation of the target sequence.- Returns:
- a String representation of the matrix.
-
getDelete
Returns the current expenses of a single delete operation.- Returns:
- delete
-
getEditDistance
This gives the edit distance according to the given parameters of this certain object. It returns just the last element of the internal cost matrix (left side down). So if you extend this class, you can just do the following:int myDistanceValue = foo; this.CostMatrix = new int[1][1]; this.CostMatrix[0][0] = myDistanceValue;
- Returns:
- returns the edit_distance computed with the given parameters.
-
getGapExt
Returns the current expenses of any extension of a gap operation.- Returns:
- gapExt
-
getInsert
Returns the current expenses of a single insert operation.- Returns:
- insert
-
getMatch
Returns the current expenses of a single match operation.- Returns:
- match
-
getReplace
Returns the current expenses of a single replace operation.- Returns:
- replace
-
pairwiseAlignment
Global pairwise sequence alignment of two BioJava-Sequence objects according to the Needleman-Wunsch-algorithm.- Specified by:
pairwiseAlignment
in classAlignmentAlgorithm
- Parameters:
query
-subject
-- Returns:
- score of the alignment or the distance.
- Throws:
BioException
- See Also:
-
setDelete
Sets the penalty for a delete operation to the specified value.- Parameters:
del
- costs for a single deletion operation
-
setGapExt
Sets the penalty for an extension of any gap (insert or delete) to the specified value.- Parameters:
ge
- costs for any gap extension
-
setInsert
Sets the penalty for an insert operation to the specified value.- Parameters:
ins
- costs for a single insert operation
-
setMatch
Sets the penalty for a match operation to the specified value.- Parameters:
ma
- costs for a single match operation
-
setReplace
Sets the penalty for a replace operation to the specified value.- Parameters:
rep
- costs for a single replace operation
-
setSubstitutionMatrix
Sets the substitution matrix to be used to the specified one. Afterwards it is only possible to align sequences of the alphabet of this substitution matrix.- Parameters:
matrix
- an instance of a substitution matrix.
-