Smith-Waterman for Pharo

A clean, idiomatic implementation of the Smith-Waterman local sequence alignment algorithm in pure Pharo Smalltalk. Finds the optimal local alignment between two sequences using dynamic programming.

Features

• Pure Pharo — no external dependencies, no FFI, runs on any Pharo image.
• Local alignment — finds the best matching substring pair, ignoring unmatched prefixes/suffixes (unlike Needleman-Wunsch global alignment).
• Customizable scoring — match, mismatch, and gap penalties are first-class accessors.
• Polymorphic — works on any SequenceableCollection (strings, arrays, BioSequences, …) via the standard align: with: protocol.
• Reporting — alignment score, identity fraction, CIGAR string, alignment length, matches count, raw DP matrix for inspection.
• Class-side examples — runnable demos for DNA, English words, proteins, no-match, and custom scoring.
• 17 SUnit tests in SmithWaterman-Tests, 100% green.

Installation

Load the baseline via Iceberg or directly:

EpMonitor disableDuring: [ 
	Metacello new	
		baseline: 'SmithWaterman';	
		repository: 'github://hernanmd/smith-waterman/src';	
		load ].

Baseline String

If you want to add the SmithWaterman to your Metacello Baselines or Configurations, copy and paste the following expression:

	" ... "
	spec
		baseline: 'SmithWaterman' 
		with: [ spec repository: 'github://hernanmd/smith-waterman/src' ];
	" ... "

Quick start

| aligner |
aligner := ALSmithWaterman new.
aligner align: 'TTACGTACGTACGTACGTACG' with: 'GGTTACGTCGTACGTACGTACGTACGTACGT'.
aligner firstSequence.    "=> 'TACGTACGTACGTACGTACG'  (the aligned region of seq1)"
aligner secondSequence.   "=> 'TACGTACGTACGTACGTACG'  (the aligned region of seq2)"
aligner alignmentScore.   "=> 40"
aligner asCIGAR.          "=> '20M'"
aligner identity.         "=> 1.0"

Even shorter — String carries a convenience hook:

'IMPRESIONABLE' alignUsingSWWith: 'IMPRESO'.

How it works

Given two sequences of length m and n, the algorithm builds an (m+1) × (n+1) scoring matrix where every cell holds the best score of any alignment ending at that position, with a hard floor of zero (the local-alignment twist — once a partial alignment goes negative it is abandoned). The traceback starts at the maximum-score cell anywhere in the matrix and walks back diagonally, up, or left, until it reaches a cell with score zero.

H(i,j) = max {
    0,
    H(i-1, j-1) + score(seq1[i], seq2[j]),   "match/mismatch"
    H(i-1, j)   + gapPenalty,                "gap in seq2"
    H(i,   j-1) + gapPenalty                 "gap in seq1"
}

Default scoring is match = +2, mismatch = −1, gap = −2 (overridable). Traceback prefers diagonal moves on ties to keep the result deterministic.

API

Entry points

Message	Notes
anAligner align: seq1 with: seq2	Generic. Dispatches on the receiver's type via alignUsingSW:.
aString alignUsingSWWith: aString	Sugar: returns a new ALSmithWaterman aligned against the argument.
anAligner alignFromSequenceableCollection: seq1 with: seq2	Any SequenceableCollection.
anAligner alignFromString: seq1 with: seq2	String (joins the per-character result back into a String).

Accessors (scoring parameters)

Getter	Setter	Default
matchAward	matchAward:	2
mismatchPenalty	mismatchPenalty:	-1
gapPenalty	gapPenalty:	-2
gapCharacter	gapCharacter:	$-

Reporting

Message	Returns
firstSequence / secondSequence	The aligned subsequence of each input.
alignmentScore	The maximum cell in the DP matrix (0 if no positive alignment was found).
score	The raw PMMatrix for inspection.
alignmentLength	Number of aligned columns (including gaps).
alignmentMatches	Number of columns where both sequences carry the same non-gap character.
identity	Fraction (0..1) of aligned columns that are matches.
asCIGAR	Compact M/I/D/X/P run-length encoding.
asArray	{ firstSequence . secondSequence }.
asAssociation	firstSequence -> secondSequence.

Class-side examples

Run any of these from a Playground:

ALSmithWaterman exampleDNA.        "DNA substring against longer reference"
ALSmithWaterman exampleWords.      "'SIMILARITY' vs 'PILLAR' -> 'LAR'"
ALSmithWaterman exampleProtein.    "BLOSUM-style on 'HEAGAWGHEE' vs 'PAWHEAE'"
ALSmithWaterman exampleNoMatch.    "All-mismatch scoring: graceful empty result"
ALSmithWaterman exampleCustomScoring.

Examples

DNA local alignment

| a |
a := ALSmithWaterman new.
a align: 'TTACGTACGTACGTACGTACG' with: 'GGTTACGTCGTACGTACGTACGTACGTACGT'.
a firstSequence.   "'TACGTACGTACGTACGTACG'"
a secondSequence.  "'TACGTACGTACGTACGTACG'"
a alignmentScore.  "40"
a asCIGAR.         "'20M'"
a identity.        "1.0"

Protein alignment with custom scoring

| a |
a := ALSmithWaterman new.
a matchAward: 3; mismatchPenalty: -2; gapPenalty: -3.
a align: 'HEAGAWGHEE' with: 'PAWHEAE'.
a firstSequence.   "'HEA'"
a alignmentScore.  "9"
a asCIGAR.         "'3M'"

English-word local alignment

ALSmithWaterman new
    align: 'SIMILARITY' with: 'PILLAR';
    asCIGAR.    "=> '3M' (the substring LAR)"

Alignment with insertions and deletions

| a |
a := ALSmithWaterman new.
a matchAward: 2; mismatchPenalty: -1; gapPenalty: -1.
a align: 'ABCDEFGH' with: 'ABXCDYEFGH'.
a firstSequence.   "'AB-CD-EFGH'  (gaps = insertions in seq2)"
a secondSequence.  "'ABXCDYEFGH'"
a asCIGAR.         "'2M1I2M1I4M'"

No positive alignment → empty result

| a |
a := ALSmithWaterman new.
a matchAward: 1; mismatchPenalty: -5; gapPenalty: -5.
a align: 'AAAAAA' with: 'TTTTTT'.
a firstSequence.   "''"
a alignmentScore.  "0"
a asCIGAR.         "''"

Working on non-string collections

ALSmithWaterman new
    align: #($a $b $c $d $e $f) with: #($c $d $f $j $k $l);
    firstSequence.    "=> OrderedCollection($c $d)"

Class hierarchy

ALSmithWaterman is a subclass of ALNeedlemanWunsch and inherits:

• The instance slots matchAward, mismatchPenalty, gapPenalty, firstSequence, secondSequence, gapCharacter.
• The align: with: entry point and the alignUsingSW: dispatch protocol on String and SequenceableCollection.
• The match-score / gap helpers (matchScore:with:).
• The finalize:with: traceback finalization step (overridden in SW to handle the empty-alignment case).
• The asArray, asAssociation, and -> accessors.

It adds only the local-alignment specifics: the score slot for the DP matrix, the Smith-Waterman initialization defaults, the local-alignment core algorithm in alignFromSequenceableCollection:with:, the score / alignmentScore / identity / CIGAR / alignmentLength / alignmentMatches reporters, and the class-side examples.

This means a single, clean inheritance line: if you know ALNeedlemanWunsch, you already know most of ALSmithWaterman — only the local-alignment core is new.

Running the tests

(ALSmithWatermanTest buildSuite) run.
"17 ran, 17 passed, 0 skipped, 0 expected failures, 0 failures, 0 errors, 0 passed unexpected"

The suite covers:

• Initialization & accessors — defaults, setter round-trips.
• Edge cases — empty sequences on either side, both empty, single-character match, single-character mismatch.
• Core algorithm — substring DNA, word similarity, local-alignment-skip, no-positive-alignment graceful empty, identical sequences.
• Scenarios with gaps & mismatches — insertion in seq2 (I), deletion in seq2 (D), mixed mismatches (X).
• Polymorphism — SequenceableCollection of symbols, String extension method.
• CIGAR — mixed operations produce the right run-length encoding.

Baseline structure

The BaselineOfSmithWaterman declares two packages and three groups:

Group	Packages
Core	SmithWaterman
Tests	SmithWaterman, SmithWaterman-Tests
default	Core, Tests

SmithWaterman-Tests requires: #('SmithWaterman').

References

• Smith, T. F. & Waterman, M. S. (1981). Identification of common molecular subsequences. Journal of Molecular Biology, 147(1), 195–197.
• Durbin, R., Eddy, S. R., Krogh, A. & Mitchison, G. (1998). Biological Sequence Analysis: Probabilistic Models of Proteins and Nucleic Acids. Cambridge University Press. Chapter 2.

License

This software is licensed under the MIT License.

Copyright Hernán Morales Durand, 2026.

Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

Authors

Hernán Morales Durand