org.biojava.bio.alignment

Class SmithWaterman

java.lang.Object

org.biojava.bio.alignment.AlignmentAlgorithm

org.biojava.bio.alignment.SmithWaterman

public class SmithWaterman
extends AlignmentAlgorithm

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

Constructors

Constructor and Description
SmithWaterman() Default constructor.
SmithWaterman(short match, short replace, short insert, short delete, short gapExtend, SubstitutionMatrix matrix) Constructs the new SmithWaterman alignment object.

Method Summary

Methods

Modifier and Type	Method and Description
short	getDelete()
short	getGapExt()
short	getInsert()
short	getMatch()
short	getReplace()
SubstitutionMatrix	getSubMatrix()
AlignmentPair	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

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

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 given SubstitutionMatrix equals the alphabet of both the query and the target Sequence. The alignment parameters here are expenses and not scores as they are in the NeedlemanWunsch 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 match

replace - expenses for a replace operation

insert - expenses for a gap opening in the query sequence

delete - expenses for a gap opening in the target sequence

gapExtend - expenses for the extension of a gap which was started earlier.

matrix - the SubstitutionMatrix object to use.

Method Detail

getDelete

public short getDelete()

Returns:

the delete

getGapExt

public short getGapExt()

Returns:

the gapExt

getInsert

public short getInsert()

Returns:

the insert

getMatch

public short getMatch()

Returns:

the match

getReplace

public short getReplace()

Returns:

the replace

getSubMatrix

public SubstitutionMatrix 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 class AlignmentAlgorithm

Returns:

score of the alignment or the distance.

Throws:

BioRuntimeException

See Also:

AlignmentAlgorithm.pairwiseAlignment(org.biojava.bio.symbol.SymbolList, org.biojava.bio.symbol.SymbolList)

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.

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.

Parameters:

ge - costs for any gap extension

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.

Parameters:

ins - costs for a single insert operation

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.

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.

Parameters:

rep - costs for a single replace operation

setSubMatrix

public void setSubMatrix(SubstitutionMatrix subMatrix)

Parameters:

subMatrix - the subMatrix to set