Skip to content

Score all sequence pairs without building alignments (GLOBAL, LOCAL): 27-286x faster getAllPairsScores - #1161

Open
mikepapadim wants to merge 1 commit into
biojava:masterfrom
mikepapadim:perf/all-pairs-scores
Open

mikepapadim wants to merge 1 commit into
biojava:masterfrom
mikepapadim:perf/all-pairs-scores

Conversation

@mikepapadim

Copy link
Copy Markdown

Follow-up to #1158, proposal (1): a CPU-only fast path, no new dependencies.

What

Alignments.getAllPairsScores built a full NeedlemanWunsch/SmithWaterman alignment for every pair, with a traceback matrix of objects per cell, only to read its score. So did the pairwise stage of getMultipleSequenceAlignment. For GLOBAL and LOCAL scoring the score needs only the last row of the dynamic-programming matrix.

The new package-private AllPairsScores scores each pair in linear memory on primitive arrays:

  • It uses the recurrences of AlignerHelper, linear and affine, so the scores are exactly the aligners'.
  • The scorers it returns for the guide tree have the aligners' maximum and minimum scores, hence the same distances and the same MSA.
  • Pairs run on the ConcurrencyTools pool, one task per query sequence, so ConcurrencyTools.setThreadPoolSize still applies.

Other scorer types (*_IDENTITIES, *_SIMILARITIES, KMERS, WU_MANBER), fewer than two sequences, an empty sequence or mixed compound sets take the existing path unchanged. No public API changes.

Speed

getAllPairsScores, BLOSUM62, gaps 10/1, best of 3 after 2 warm-ups. i9-13900K (32 threads), JDK 21, ConcurrencyTools default pool. The machine was also running other jobs, so read the ratios rather than the absolute times. The checksum of all scores is identical on both branches.

Input Pairs master this PR Speed-up
200 random proteins, 100–500 aa, GLOBAL 19,900 13.9 s 0.51 s 27×
same, LOCAL 19,900 13.1 s 0.33 s 40×
Pfam PF00104 (283 sequences), GLOBAL 39,903 552.6 s 1.93 s 286×

On PF00104, master is dominated by allocating and collecting the per-cell traceback objects of long sequences.

Tests

AllPairsScoresTest (8 tests). For every pair it compares score, max, min, distance and similarity against getAllPairsScorers + the aligners. Inputs:

  • random and related (mutated) proteins;
  • rare compounds (X B Z U *);
  • lengths from 1 to 300, including identical sequences;
  • DNA with NUC.4.4;
  • six gap penalties (linear and affine) and three matrices (BLOSUM62, BLOSUM30, PAM250).

It also checks that getMultipleSequenceAlignment gives the same profile as before for GLOBAL and LOCAL.

The whole biojava-alignment suite passes: 135 tests, 0 failures.

A bug this found in the existing path

SmithWaterman with a linear gap penalty throws ArrayIndexOutOfBoundsException for a pair that has no positive substitution score, e.g. W vs MK with BLOSUM62. The exception is in its traceback. getListFromFutures logs and drops the failed future, so runPairwiseScorers returns fewer scores than pairs, and every later score sits at the wrong index. The local score of such a pair is 0. That is what SmithWaterman returns with an affine penalty, and what this PR returns for both. noPositiveLocalCell documents it. I left SmithWaterman itself alone; happy to fix it in a separate PR if you like.

How to run

git fetch https://github.com/mikepapadim/biojava.git perf/all-pairs-scores && git checkout FETCH_HEAD
mvn -pl biojava-alignment -am install -DskipTests
mvn -pl biojava-alignment test -Dtest=AllPairsScoresTest                # parity with the aligners
mvn -pl biojava-alignment test                                          # whole module

To time it yourself, a minimal program (run it against master and this branch):

var seqs = new ArrayList<ProteinSequence>();          // e.g. FastaReaderHelper.readFastaProteinSequence(file).values()
var scores = Alignments.getAllPairsScores(seqs, PairwiseSequenceScorerType.GLOBAL,
        new SimpleGapPenalty(10, 1), SubstitutionMatrixHelper.getBlosum62());
ConcurrencyTools.shutdown();

Alignments.getAllPairsScores, and the pairwise stage of
getMultipleSequenceAlignment, built a full NeedlemanWunsch or SmithWaterman
alignment for every pair, with a traceback matrix of objects per cell, only
to read its score. For GLOBAL and LOCAL scoring the score needs only the last
row of the dynamic programming matrix.

AllPairsScores scores each pair in linear memory on primitive arrays, with
the recurrences of AlignerHelper (linear and affine gap penalties), so the
scores are exactly the aligners'. The scorers it returns for the guide tree
have the aligners' maximum and minimum scores, hence the same distances and
the same multiple alignment. Pairs run on the ConcurrencyTools pool, one task
per query sequence. Other scorer types, a single sequence, an empty sequence
or mixed compound sets take the existing path.

AllPairsScoresTest checks scores, maximum, minimum, distance and similarity
of every pair against the aligners for random and related proteins, rare
compounds, very different lengths, DNA, six gap penalties and three
matrices, and the multiple alignment for GLOBAL and LOCAL.

SmithWaterman with a linear gap penalty throws for a pair with no positive
substitution score (ArrayIndexOutOfBoundsException in its traceback), and
getListFromFutures drops that pair's score, so runPairwiseScorers returns
fewer scores than pairs. The local score of such a pair is 0, which is what
the new path returns; noPositiveLocalCell documents the case.
@josemduarte

Copy link
Copy Markdown
Contributor

Thanks for this, the parity tests are really thorough. I've been working on the same part of the code in #1164, and the two PRs overlap enough that I think we should line them up before merging either.

What #1164 does that touches this PR

  • It speeds up the existing aligners: the substitution scores are looked up in a precomputed table, and the AlignerHelper fill no longer allocates a traceback array per cell. That's about 10–18x for proteins (e.g. SmithWaterman goes from ~122 to ~12 ns/cell).
  • It adds a public PairwiseStatisticsAligner. It computes the score, number of identicals, alignment length and start/end positions, with no traceback and in linear memory. Its statistics match the alignment SmithWaterman/NeedlemanWunsch return, ties included. It's immutable and thread-safe, and sequences can be encoded once for all-against-all use.
  • It fixes the SmithWaterman linear-gap crash you found (nothing scoring above zero), and a crash on an empty query.

Suggestions

  1. Share one kernel. scoreAffine/scoreLinear here are a score-only version of the fill in PairwiseStatisticsAligner. With both PRs in, we'd have three copies of the recurrences. Could AllPairsScores encode each sequence once with PairwiseStatisticsAligner.encode and run the pairs through it? Your per-row task layout on ConcurrencyTools and ComputedScorer would stay as they are.
  2. Cover *_IDENTITIES. getMultipleSequenceAlignment defaults to GLOBAL_IDENTITIES, so the default MSA call doesn't hit the fast path as it stands. FractionalIdentityScorer needs only the number of identicals and the alignment length, which PairwiseStatisticsAligner returns with the same tie-breaking as the traceback. So GLOBAL_IDENTITIES and LOCAL_IDENTITIES could go on the fast path too. *_SIMILARITIES would need one more counter, which I'm happy to add on my side.
  3. Drop the workaround in the test. Once the SmithWaterman fix is in, the ArrayIndexOutOfBoundsException catch in assertSameAsAligners is never reached and can go. noPositiveLocalCell can then compare against SmithWaterman directly for both gap types. The empty-sequence fallback also works now, if you want to keep that in isSupported.
  4. Re-benchmark against the new baseline. With Improving pairwise alignment performance #1164 merged, the old path is a lot faster, so the speed-ups here will be smaller than the current table shows. It would be good to re-measure against that baseline, both for this PR as is and for the version built on PairwiseStatisticsAligner. If the score-only loop is clearly faster for plain GLOBAL/LOCAL, keeping it may be worth the duplicate code. If the difference is small, I'd rather have one kernel.

My suggestion for the order is to merge #1164 first and then rebase this one onto it. Happy to help with the rebase or to pair on the identities path. Let me know what you think.

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.

2 participants