Sequence alignment in XSLT 3.0
summary
Implements the Needleman–Wunsch global pairwise algorithm in XSLT 3.0, proving practical viability rather than just restating the topic. Uses anti‑diagonal iteration to avoid deep recursion, stores a cumulative backtrace string per cell so only the current and two preceding diagonals are retained (the three-diagonal working set), which reduces memory and lets longer sequences be aligned. Runs in Saxon HE and EE (threading gives little benefit here), remains quadratic time, code and timings sit on GitHub; path-as-string is noted as a performance hotspot.
AI-written summary · about
chapters (7)
- 0:00Introduction
- 1:11What is sequence alignment
- 6:11Dynamic programming basics
- 8:20Needleman-Wunsch algorithm
- 17:33XSLT implementation challenges
- 23:15Optimizing the algorithm
- 23:57Q&A
related talks
25mA Semi-Persistent E-Graph with Native AC Canonization and Leapfrog AC Matching.
24mTruly Functional Solutions to the Longest Uptrend Problem (Functional Pearl)
44mPlaying with Grammars: What Have We Known So Far!
25mNano-parsing: A Data-parallel Architecture for Perverse Parsing Environments
21mgoSLP - Globally Optimized Superword Level Parallelism Framework
57mSwift Tutorial - Exploring Swift Sequences in Depth
39mScaling Xtext
25mZero-Overhead Parallel Scans for Multi-Core CPUs