NeedlemanWunschAligner
in package
implements
NeedlemanWunschAlignerInterface
The classic Needleman-Wunsch algorithm : a (firstLength+1) x (secondLength+1) matrix is filled so that cell (i, j) holds the best score of aligning the first i symbols of the first sequence against the first j symbols of the second one, then the alignment itself is recovered by walking that matrix back from its bottom-right corner to (0, 0). Only a linear (per-gap-symbol) gap penalty is supported ; an affine, opening-versus-extension penalty would need a second matrix and is not implemented here.
When two or three predecessor cells tie for the best score, the diagonal (substitution) move is preferred over an "up" move (a gap in the second sequence), itself preferred over a "left" move (a gap in the first sequence) ; this is an arbitrary but deterministic choice, made so the same input always produces the same alignment. Class NeedlemanWunschAligner
Tags
Table of Contents
Interfaces
- NeedlemanWunschAlignerInterface
- Interface NeedlemanWunschAlignerInterface - computes the optimal end-to-end (global) alignment of two sequences under a linear gap penalty.
Methods
- align() : PairwiseAlignmentResult
- buildMatrix() : array<string|int, array<string|int, int>>
- traceback() : array<string|int, string>
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, array<string|int, int>>
Parameters
- $sFirst : string
- $sSecond : string
- $iFirstLength : int
- $iSecondLength : int
- $oScoring : SubstitutionScoringInterface
- $iGapPenalty : int
Return values
array<string|int, array<string|int, int>>traceback()
private
traceback(array<string|int, array<string|int, int>> $aMatrix, string $sFirst, string $sSecond, int $iFirstLength, int $iSecondLength, SubstitutionScoringInterface $oScoring, int $iGapPenalty) : array<string|int, string>
Parameters
- $aMatrix : array<string|int, array<string|int, int>>
- $sFirst : string
- $sSecond : string
- $iFirstLength : int
- $iSecondLength : int
- $oScoring : SubstitutionScoringInterface
- $iGapPenalty : int
Return values
array<string|int, string> —[alignedFirst, alignedSecond]