Repository navigation
Improving pairwise alignment performance - #1164
Open
josemduarte wants to merge 5 commits into
Open
josemduarte wants to merge 5 commits into
josemduarte wants to merge 5 commits into
Conversation
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]>
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
Faster pairwise alignment, a statistics-only aligner, and two crash fixes
Performance (no change in results)
AbstractPairwiseSequenceAlignerprecomputes the substitution scores of each alignment. Previously every matrix cell calledSimpleSubstitutionMatrix.getValue, which does twoList.indexOfscans.AlignerHelperno 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:
PairwiseStatisticsAlignerSubstitutionMatrix.SmithWaterman/NeedlemanWunschreturn, ties included, and the tests check exactly that.Bug fixes (each with regression tests)
SmithWatermanwith a linear gap penalty threwArrayIndexOutOfBoundsExceptionwhen no cell scored above zero.SmithWatermanandNeedlemanWunschthrewArrayIndexOutOfBoundsExceptionon an empty query.Benchmark
ns per matrix cell, single thread, BLOSUM62, gaps 11/1, related protein pairs:
SmithWaterman, masterSmithWaterman, this PRPairwiseStatisticsAlignerNeedlemanWunschspeeds 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.SimpleAlignedSequencehas no location for a sequence that is all gaps.🤖 Generated with Claude Code