Package org.biojava.bio.alignment
Class SmithWaterman
java.lang.Object
org.biojava.bio.alignment.AlignmentAlgorithm
org.biojava.bio.alignment.SmithWaterman
Smith and Waterman developed an efficient dynamic programming algorithm to
perform local sequence alignments, which returns the most conserved region of
two sequences (longest common substring with modifications). This algorithm
is performed by the method
pairwiseAlignment
of this class. It
uses affine gap penalties if and only if the expenses of a delete or insert
operation are unequal to the expenses of gap extension. This uses
significantly more memory (four times as much) and increases the runtime if
swapping is performed.- Since:
- 1.5
- Author:
- Andreas Dräger, Gero Greiner, Mark Schreiber
-
Constructor Summary
ConstructorsConstructorDescriptionDefault constructor.SmithWaterman
(short match, short replace, short insert, short delete, short gapExtend, SubstitutionMatrix matrix) Constructs the new SmithWaterman alignment object. -
Method Summary
Modifier and TypeMethodDescriptionshort
short
short
short
getMatch()
short
pairwiseAlignment
(SymbolList query, SymbolList subject) Overrides the method inherited from the NeedlemanWunsch and performs only a local alignment.void
setDelete
(short del) Overrides the method inherited from the NeedlemanWunsch and sets the penalty for a delete operation to the specified value.void
setGapExt
(short ge) Overrides the method inherited from the NeedlemanWunsch and sets the penalty for an extension of any gap (insert or delete) to the specified value.void
setInsert
(short ins) Overrides the method inherited from the NeedlemanWunsch and sets the penalty for an insert operation to the specified value.void
setMatch
(short ma) Overrides the method inherited from the NeedlemanWunsch and sets the penalty for a match operation to the specified value.void
setReplace
(short rep) Overrides the method inherited from the NeedlemanWunsch and sets the penalty for a replace operation to the specified value.void
setSubMatrix
(SubstitutionMatrix subMatrix) Methods inherited from class org.biojava.bio.alignment.AlignmentAlgorithm
alignAll
-
Constructor Details
-
SmithWaterman
public SmithWaterman()Default constructor. -
SmithWaterman
public SmithWaterman(short match, short replace, short insert, short delete, short gapExtend, SubstitutionMatrix matrix) Constructs the new SmithWaterman alignment object. Alignments are only performed, if the alphabet of the givenSubstitutionMatrix
equals the alphabet of both the query and the targetSequence
. The alignment parameters here are expenses and not scores as they are in theNeedlemanWunsch
object. scores are just given by multiplying the expenses with(-1)
. For example you could use parameters like "-2, 5, 3, 3, 0". If the expenses for gap extension are equal to the cost of starting a gap (delete or insert), no affine gap penalties are used, which saves memory.- Parameters:
match
- expenses for a matchreplace
- expenses for a replace operationinsert
- expenses for a gap opening in the query sequencedelete
- expenses for a gap opening in the target sequencegapExtend
- expenses for the extension of a gap which was started earlier.matrix
- theSubstitutionMatrix
object to use.
-
-
Method Details
-
getDelete
- Returns:
- the delete
-
getGapExt
- Returns:
- the gapExt
-
getInsert
- Returns:
- the insert
-
getMatch
- Returns:
- the match
-
getReplace
- Returns:
- the replace
-
getSubMatrix
- Returns:
- the subMatrix
-
pairwiseAlignment
public AlignmentPair pairwiseAlignment(SymbolList query, SymbolList subject) throws BioRuntimeException Overrides the method inherited from the NeedlemanWunsch and performs only a local alignment. It finds only the longest common subsequence. This is good for the beginning, but it might be better to have a system to find more than only one hit within the score matrix. Therefore, one should only define the k-th best hit, where k is somehow related to the number of hits.- Specified by:
pairwiseAlignment
in classAlignmentAlgorithm
- Parameters:
query
-subject
-- Returns:
- score of the alignment or the distance.
- Throws:
BioRuntimeException
- See Also:
-
setDelete
Overrides the method inherited from the NeedlemanWunsch and sets the penalty for a delete operation to the specified value. Reason: internally scores are used instead of penalties so that the value is muliplyed with -1.- Parameters:
del
- costs for a single deletion operation
-
setGapExt
Overrides the method inherited from the NeedlemanWunsch and sets the penalty for an extension of any gap (insert or delete) to the specified value. Reason: internally scores are used instead of penalties so that the value is muliplyed with -1.- Parameters:
ge
- costs for any gap extension
-
setInsert
Overrides the method inherited from the NeedlemanWunsch and sets the penalty for an insert operation to the specified value. Reason: internally scores are used instead of penalties so that the value is muliplyed with -1.- Parameters:
ins
- costs for a single insert operation
-
setMatch
Overrides the method inherited from the NeedlemanWunsch and sets the penalty for a match operation to the specified value. Reason: internally scores are used instead of penalties so that the value is muliplyed with -1.- Parameters:
ma
- costs for a single match operation
-
setReplace
Overrides the method inherited from the NeedlemanWunsch and sets the penalty for a replace operation to the specified value. Reason: internally scores are used instead of penalties so that the value is muliplyed with -1.- Parameters:
rep
- costs for a single replace operation
-
setSubMatrix
- Parameters:
subMatrix
- the subMatrix to set
-