SemiGlobalAligner.php
Semi-global (overlap) pairwise sequence alignment by dynamic programming Freely inspired by BioPHP's project biophp.org Created 30 September 2026 Last modified 7 October 2026
Table of Contents
Classes
- SemiGlobalAligner
- 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.