Package org.biojava.bio.alignment
Class SmithWaterman
- java.lang.Object
-
- org.biojava.bio.alignment.SequenceAlignment
-
- org.biojava.bio.alignment.NeedlemanWunsch
-
- org.biojava.bio.alignment.SmithWaterman
-
public class SmithWaterman extends NeedlemanWunsch
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 methodpairwiseAlignment
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
-
-
Field Summary
-
Fields inherited from class org.biojava.bio.alignment.NeedlemanWunsch
alignment, CostMatrix, pairalign, subMatrix
-
-
Constructor Summary
Constructors Constructor Description SmithWaterman(short match, short replace, short insert, short delete, short gapExtend, SubstitutionMatrix matrix)
Constructs the new SmithWaterman alignment object.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description int
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.-
Methods inherited from class org.biojava.bio.alignment.NeedlemanWunsch
alignAll, getAlignment, getAlignmentString, getDelete, getEditDistance, getGapExt, getInsert, getMatch, getReplace, min, printAlignment, printCostMatrix, setSubstitutionMatrix
-
Methods inherited from class org.biojava.bio.alignment.SequenceAlignment
formatOutput
-
-
-
-
Constructor Detail
-
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 Detail
-
setInsert
public void setInsert(short ins)
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.- Overrides:
setInsert
in classNeedlemanWunsch
- Parameters:
ins
- costs for a single insert operation
-
setDelete
public void setDelete(short del)
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.- Overrides:
setDelete
in classNeedlemanWunsch
- Parameters:
del
- costs for a single deletion operation
-
setGapExt
public 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. Reason: internally scores are used instead of penalties so that the value is muliplyed with -1.- Overrides:
setGapExt
in classNeedlemanWunsch
- Parameters:
ge
- costs for any gap extension
-
setMatch
public void setMatch(short ma)
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.- Overrides:
setMatch
in classNeedlemanWunsch
- Parameters:
ma
- costs for a single match operation
-
setReplace
public void setReplace(short rep)
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.- Overrides:
setReplace
in classNeedlemanWunsch
- Parameters:
rep
- costs for a single replace operation
-
pairwiseAlignment
public int 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.- Overrides:
pairwiseAlignment
in classNeedlemanWunsch
- Returns:
- score of the alignment or the distance.
- Throws:
BioRuntimeException
- See Also:
SequenceAlignment.pairwiseAlignment(org.biojava.bio.symbol.SymbolList, org.biojava.bio.symbol.SymbolList)
-
-