Repository navigation
Conversation
In the striped inner loop E'/F' read max(M,F)/max(M,E) rather than the reduced H'(i,j). As the gap open o>=0 the term dropped from each is always dominated, so the recurrence is unchanged (score- and CIGAR-exact). This breaks the e/f updates' dependency on the fully reduced H'(i,j) and shortens the loop-carried F chain, speeding mate rescue by ~1.15x on arm64. x86 keeps the original recurrence, which is faster there.
nh13
pushed a commit
that referenced
this pull request
Jul 19, 2026
1. In bwa-mem, mapq_se is not changed if it is higher than mapq_pe. This is supposed to take care of the case where one read is highly unique and the mate falls in TRs. However, there is another case: read1 mapped at NM=1 and read2 at NM=0, versus, read1 at NM=0 and read2 at NM=1. The pair should get mapq 0. With this PR, mapq_se is only allowed to be higher if the read has only one hit. This may be relaxed. 2. Even if the unpaired alignment is preferred, its mapq should be adjusted against the best pair. Bwa and older minibwa does not have this mechanism. 3. Add a heuristic learned from dragmap: somewhat cap mapq_pe by considering the second best hit of each end. Effectively, we penalize repetitive reads even if there is only one good paired alignment, because the second best pair is more likely to be missing. Minibwa already implemented two other heuristics but the new heuristic still plays a role in rare cases. This PR addresses z20 and z21 in #6
Owner
Author
|
@coderabbitai pause |
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.
ksw_ll_u8_core/ksw_ll_i16_core(the striped kernel used for paired-end mate rescue) update each cell withE'(i+1,j)=max(E'-r, H'-q)andF'(i,j+1)=max(F'-r, H'-q), whereH'=max(M,E',F')andq=o+e>=e=r. Sinceo>=0, theE'term ofH'-qis dominated byE'-rand theF'term byF'-r, soE'only needsmax(M,F)-qandF'only needsmax(M,E)-q. Reading those in place of the reducedH'(i,j)is score- and CIGAR-exact, but drops the gap updates' dependency on the final three-way max and shortens the loop-carriedFchain.This wins on arm64 (NEON) and loses on x86 (the extra max per cell outweighs the shorter chain), so it sits under
#if defined(__ARM_NEON)and x86 keeps the original recurrence. Both the 8- and 16-bit cores are converted.Checked with a standalone harness that builds the old and new
ksw_ll_{u8,i16}_coreside by side and compares them per pair: 120000 pairs identical over qlen 64..250, 8- and 16-bit;minibwa map -x sron HG002 WGS PE gives byte-identical SAM. Kernel throughput (candidate/baseline): Graviton4 1.13-1.17x, Apple NEON ~1.1-1.2x; x86, gated off, measured 0.90-0.92x on Sapphire Rapids and 0.95-0.98x on Zen3. End-to-end single-thread wall is ~2% on WGS short-read PE, where mate rescue is ~1/5 of the work.