BandedPlusAligner

Basic Usage

bandedplusaligner.sh <query> <ref>
bandedplusaligner.sh <query> <ref> <map>
bandedplusaligner.sh <query> <ref> <map> <iterations> <simd>

The tool accepts sequences directly as command-line arguments or as paths to FASTA files. For simple alignment identity calculation, only query and reference are required. Additional parameters enable visualization output, benchmarking, and SIMD acceleration.

Parameters

Parameters are provided as positional arguments in the order listed below. The tool uses a streamlined interface focused on essential alignment parameters.

Examples

bandedplusaligner.sh "ATCGATCGATCG" "ATCGATCGATCG"

bandedplusaligner.sh query.fasta reference.fasta

bandedplusaligner.sh query.fasta ref.fasta alignment_matrix.txt

bandedplusaligner.sh "ATCGATCG" "ATCGATCG" null 1000

bandedplusaligner.sh long_query.fasta long_ref.fasta matrix.txt 1 true

Algorithm Details

BandedPlusAligner2 implements traceback-free banded dynamic programming alignment using mathematical constraint solving for exact Average Nucleotide Identity calculation. The implementation uses dual rolling arrays and 64-bit bit-packed scoring to achieve O(n) space complexity.

Dynamic Bandwidth Calculation

The decideBandwidth() method (lines 58-64) calculates optimal band width by analyzing substitution patterns in sequence prefixes. The formula Math.min(60+(int)Math.sqrt(rLen), 4+Math.max(qLen, rLen)/8) provides initial bandwidth, then early mismatch detection counts substitutions using (query[i]!=ref[i] ? 1 : 0) to return Math.min(subs+1, bandwidth) for high-identity optimization.

Dual Rolling Array Implementation

Uses prev[rLen+1] and curr[rLen+1] arrays (line 96) with array swapping temp=prev; prev=curr; curr=temp (lines 163-165) achieving O(n) space complexity instead of traditional O(mn). The BAD=Long.MIN_VALUE/2 sentinel value prevents out-of-band access.

64-Bit Bit-Packed Encoding

Each scoring cell packs three values into a single 64-bit long using bit field constants:

• POSITION_BITS=21: Reference start coordinates (bits 0-20, mask POSITION_MASK=(1L<<21)-1)
• DEL_BITS=21: Deletion event counting (bits 21-41, mask DEL_MASK=((1L<<21)-1)<<21)
• SCORE_SHIFT=42: Alignment scores (bits 42-63, mask SCORE_MASK=~(POSITION_MASK|DEL_MASK))

Score constants include MATCH=1L<<42, SUB=(-1L)<<42, and DEL_INCREMENT=(1L<<21)+DEL for deletion tracking.

Long Array Sequence Encoding

Sequences are converted using Factory.encodeLong() with query N-threshold=15 and reference N-threshold=31. This encoding enables efficient bitwise comparisons using (q|r)>=15 for N-base detection (line 129) and q==r for exact matches (line 128).

SIMD Vectorization Integration

When Shared.SIMD is enabled, the algorithm calls shared.SIMDAlign.alignBandVectorDel(q, ref, bandStart, bandEnd, prev, curr) (line 120) for hardware-accelerated alignment processing. Falls back to scalar branchless scoring loop (lines 124-144) with conditional expressions for CPU pipeline optimization.

Mathematical Constraint System

The postprocess() method (lines 181-236) solves exact operation counts without traceback using three equations:

• M + S + I = qLen (query sequence consumption)
• M + S + D = refAlnLength (reference alignment span)
• Score = M - S - I - D (scoring relationship)

Implementation extracts values: deletions=(int)((maxScore&DEL_MASK)>>POSITION_BITS), calculates insertions=Math.max(0, qLen+deletions-refAlnLength), solves matches=(rawScore+qLen+deletions)/2f, and derives final identity.

Sequence Length Optimization

When posVector==null, sequences are swapped using if(query0.length>ref0.length) (lines 75-79) ensuring query ≤ reference for memory optimization and reducing complexity from O(nm) to O(min(n,m)*max(n,m)).

Implementation Performance

• Memory Usage: 200MB base allocation (line 51 in shell script) plus linear sequence length scaling
• Space Complexity: O(n) using dual arrays vs O(nm) traditional dynamic programming
• Sequence Limit: 2,097,151 bp enforced by assert(ref.length<=POSITION_MASK) (line 84)
• Band Processing: bandStart=Math.max(1, Math.min(i-bandWidth, rLen-bandWidth)) restricts computation to diagonal bands

Output Format

The tool outputs alignment results to standard output in a structured format:

• Identity: Floating-point value from 0.0 to 1.0 representing sequence similarity
• Reference Start: Zero-based starting position of optimal alignment in reference
• Reference Stop: Zero-based ending position of optimal alignment in reference
• Matrix Map: Optional detailed visualization file showing dynamic programming matrix exploration

Technical Notes

N-Base Scoring Implementation

Ambiguous nucleotides are handled using bitwise detection hasN=((q|r)>=15) (line 129). N-bases are scored using N_SCORE=0L (line 286) providing neutral scoring, while standard mismatches use SUB=(-1L)<. The encoding threshold separates standard nucleotides (values 0-14) from N-bases (15+).