Skip to content

Improving pairwise alignment performance - #1164

Open
josemduarte wants to merge 5 commits into
biojava:masterfrom
josemduarte:jd/align-perf
Open

josemduarte wants to merge 5 commits into
biojava:masterfrom
josemduarte:jd/align-perf

Conversation

@josemduarte

Copy link
Copy Markdown
Contributor

Faster pairwise alignment, a statistics-only aligner, and two crash fixes

Performance (no change in results)

  • AbstractPairwiseSequenceAligner precomputes the substitution scores of each alignment. Previously every matrix cell called SimpleSubstitutionMatrix.getValue, which does two List.indexOf scans.
  • The fill loops in AlignerHelper no longer allocate a traceback pointer array per cell, and they keep references to the current rows.

On 24 benchmark cases (protein and DNA, local and global, affine and linear gaps), the scores and alignments are byte-identical to master.

New: PairwiseStatisticsAligner

  • Returns only the score, the number of identicals, the length and the 1-based start and end positions, without traceback, in memory linear in the target length.
  • Local or global, with affine, constant or linear gaps, and any SubstitutionMatrix.
  • The statistics are carried along the same predecessor choices that the traceback pointers record. So they equal those of the alignment SmithWaterman/NeedlemanWunsch return, ties included, and the tests check exactly that.
  • Immutable and thread-safe. Sequences can be encoded once for all-against-all use.

Bug fixes (each with regression tests)

  • SmithWaterman with a linear gap penalty threw ArrayIndexOutOfBoundsException when no cell scored above zero.
  • SmithWaterman and NeedlemanWunsch threw ArrayIndexOutOfBoundsException on an empty query.

Benchmark

ns per matrix cell, single thread, BLOSUM62, gaps 11/1, related protein pairs:

~150 aa ~300 aa ~550 aa
SmithWaterman, master 125.3 122.2 121.2
SmithWaterman, this PR 14.5 12.1 11.4
PairwiseStatisticsAligner 8.4 8.3 8.3

NeedlemanWunsch speeds up by a similar 10–18x for proteins; DNA gains are smaller, about 5–7x.

Known remaining issue

In biojava-core, not fixed here: with exactly one empty sequence, NeedlemanWunsch.getPair() cannot count identicals or print. SimpleAlignedSequence has no location for a sequence that is all gaps.

🤖 Generated with Claude Code

josemduarte and others added 5 commits November 16, 2026 12:50
With a linear gap penalty, the local traceback assumed the best cell was
reached by a substitution. When no cell scores above zero the best cell
is (0,0), so the traceback stepped to index -1 and threw an
ArrayIndexOutOfBoundsException. Now it returns an empty alignment, as
the affine case already did.

Co-Authored-By: Claude Opus 5.5 <[email protected]>
SimpleSubstitutionMatrix.getValue scans the matrix's row and column
compound lists with indexOf on every call, and the pairwise aligners call
it once per cell of the score matrix. Map each distinct compound of the
query and target to a small index once per alignment and look each
distinct pair up only once.

Co-Authored-By: Claude Opus 5.5 <[email protected]>
The fill loops allocated a new traceback pointer array for every cell
and indexed the three-dimensional score array from the top on every
access. Now they reuse shared, immutable pointer arrays (one per
combination of pointers) and keep references to the current and
previous rows. The recurrence and tie breaking are unchanged.

Co-Authored-By: Claude Opus 5.5 <[email protected]>
For all-against-all comparisons, such as clustering sequences, only the
score, the number of identical positions, the length and the start and
end of the alignment are needed, not the alignment itself.
PairwiseStatisticsAligner computes them with memory linear in the length
of the target, carrying the statistics forward in the dynamic
programming instead of keeping a traceback matrix.

It computes the same recurrence as SmithWaterman (local) and
NeedlemanWunsch (global), with affine, constant or linear gap penalties,
and carries the statistics along the same predecessor choices that their
traceback pointers record, so the statistics are those of the alignment
their traceback returns, also where several alignments are optimal. The
tests check this against both aligners for related, unrelated and
low-complexity proteins with BLOSUM62 and PAM250, DNA with NUC.4.4, and
four gap penalties.

An aligner is immutable and can be shared between threads. Sequences can
be encoded once and aligned many times, and the substitution scores are
looked up once per aligner.

Co-Authored-By: Claude Opus 5.5 <[email protected]>
When the score matrix is not stored, as by default, AbstractMatrixAligner
allocates the two rows it keeps. With an empty query the matrix has only
one row, so the second allocation threw an
ArrayIndexOutOfBoundsException. Now SmithWaterman aligns empty
sequences to an empty alignment, and NeedlemanWunsch scores them.

NeedlemanWunsch still cannot count identicals or print the pair when
exactly one sequence is empty: SimpleAlignedSequence in biojava-core has
no location for a sequence that is all gaps.

Co-Authored-By: Claude Opus 5.5 <[email protected]>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

None yet

Projects

None yet

Development

Successfully merging this pull request may close these issues.

1 participant