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

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.

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();