SemiGlobalAligner
in package
implements
SemiGlobalAlignerInterface
The third classic pairwise alignment shape, between NeedlemanWunschAligner (global : every gap, including leading and trailing ones, is penalized) and SmithWatermanAligner (local : a whole sub-region can be abandoned mid-alignment). Here, the matrix borders start at zero exactly like Smith-Waterman's, so leading gaps are free, but unlike Smith-Waterman the recurrence itself is never floored at zero : once the alignment leaves the border it is never allowed to bail out mid-way, only to finish at either the last row or the last column, which is what makes trailing gaps free too without ever discarding an interior stretch the way local alignment would. The alignment is recovered by walking back from the best-scoring cell among the last row and the last column (never from an interior cell, since only those two represent "one of the two sequences has been fully consumed"), until reaching either i = 0 or j = 0 - whichever comes first - leaving the other sequence's unconsumed prefix as a free leading gap that contributes nothing to the score and is not part of the reported alignment.
As in the other two aligners, only a linear gap penalty is supported, and a tie between predecessor or candidate-endpoint cells prefers diagonal over up over left, and the last row over the last column, so the same input always produces the same alignment. Class SemiGlobalAligner
Tags
Table of Contents
Interfaces
- SemiGlobalAlignerInterface
- Interface SemiGlobalAlignerInterface - aligns two sequences without penalizing gaps at either end of either sequence, so a short sequence fully contained in a longer one (a primer inside a vector, an overlap between two fragments to assemble) scores as if the longer sequence's untouched flanks were never there.
Methods
- align() : PairwiseAlignmentResult
- buildMatrix() : array<string|int, mixed>
- traceback() : array<string|int, mixed>
Methods
align()
public
align(AbstractMolecularSequence $oFirst, AbstractMolecularSequence $oSecond, SubstitutionScoringInterface $oScoring, int $iGapPenalty) : PairwiseAlignmentResult
Parameters
- $oFirst : AbstractMolecularSequence
- $oSecond : AbstractMolecularSequence
- $oScoring : SubstitutionScoringInterface
- $iGapPenalty : int
Return values
PairwiseAlignmentResultbuildMatrix()
private
buildMatrix(string $sFirst, string $sSecond, int $iFirstLength, int $iSecondLength, SubstitutionScoringInterface $oScoring, int $iGapPenalty) : array<string|int, mixed>
Parameters
- $sFirst : string
- $sSecond : string
- $iFirstLength : int
- $iSecondLength : int
- $oScoring : SubstitutionScoringInterface
- $iGapPenalty : int
Return values
array<string|int, mixed> —[int[][] matrix, int bestI, int bestJ, int bestScore]
traceback()
private
traceback(array<string|int, array<string|int, int>> $aMatrix, string $sFirst, string $sSecond, int $iBestI, int $iBestJ, SubstitutionScoringInterface $oScoring, int $iGapPenalty) : array<string|int, mixed>
Parameters
- $aMatrix : array<string|int, array<string|int, int>>
- $sFirst : string
- $sSecond : string
- $iBestI : int
- $iBestJ : int
- $oScoring : SubstitutionScoringInterface
- $iGapPenalty : int
Return values
array<string|int, mixed> —[string alignedFirst, string alignedSecond, int firstStart, int secondStart]