Pith. sign in

REVIEW 3 major objections 7 minor 73 references

Reviewed by Pith at T0; open to challenge.

T0 means a machine referee read the full paper against a public rubric. The mark states how deep the mechanical check went, never who wrote it. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · glm-5.2

Separate recurrence from pruning, get hand-tuned speed

2026-07-08 12:36 UTC pith:2PITUO5C

load-bearing objection FILTR separates recurrence, scheduling, and pruning into three composable languages for bioinformatics DP — the pruning language with dynamic domain recurrences and the search transformation are the real contributions. the 3 major comments →

arxiv 2607.06225 v1 pith:2PITUO5C submitted 2026-07-07 cs.PL q-bio.QM

Compiling Bioinformatics Recurrences

Bala Vinaithirthan , Shiv Sundram , Sneha Goenka , Fredrik Kjolstad This is my paper
classification cs.PL q-bio.QM
keywords filtrmatrixbioinformaticscellspruningalgorithmsbiologicalimplementations
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

FILTR is a compiler that takes bioinformatics algorithms written as dynamic programming recurrences and generates C++ code matching or exceeding the performance of hand-optimized libraries. The core idea is a three-way separation: the mathematical recurrence (what to compute), the iteration schedule (in what order), and the pruning strategy (what to skip) are each specified independently in their own mini-languages, then combined and lowered to efficient code. The compiler handles coordinate transformations (like rewriting row-major traversal into antidiagonal order for parallelism), score-indexed search (inverting position and cost so the algorithm explores by edit count rather than matrix position), and dynamic pruning where runtime values feed back to contract the active computation region. The paper claims this separation is expressive enough to capture the full spectrum of real bioinformatics heuristics—banded alignment, X-drop, Z-drop, WFA-Adapt, and search—while producing code that runs 0.95x to 30x faster than hand-tuned libraries across benchmarks. The key mechanism enabling this is the Recurrence IR, an intermediate representation that allows domain bounds to be defined by their own recurrences (domain recurrences), creating a feedback loop where computed values determine which cells are evaluated next.

Core claim

The central technical discovery is that the optimization strategies used in production bioinformatics—reordering matrix traversal, pruning unpromising regions, and searching by score rather than position—can each be expressed as independent rewrites on a shared recurrence intermediate representation, and that these rewrites compose freely. Specifically, the paper shows that shearing (a coordinate transformation that makes antidiagonals contiguous in memory), search (inverting the roles of score and position so the algorithm sweeps through costs and discovers reachable positions), and dynamic pruning (where domain recurrences narrow the active region based on computed scores) are all expresss

What carries the argument

The Recurrence IR (RIR) with domain recurrences: an intermediate representation where the bounds of the iteration space are themselves defined by recurrences that depend on previously computed values, enabling data-dependent pruning feedback loops. Three input languages feed it: a recurrence language for the mathematical model, an iteration ordering language for traversal transforms (loop reordering, shearing, search), and a pruning language for static and dynamic region restriction.

Load-bearing premise

The pruning language assumes that at each step there is a single contiguous active region and that pruning decisions depend only on currently available information, not on future values. This means any bioinformatics heuristic requiring non-contiguous active regions or lookahead-dependent pruning cannot be expressed without extending the language.

What would settle it

A real-world bioinformatics heuristic that requires either non-contiguous active regions (multiple disjoint bands) or pruning decisions that depend on values not yet computed at the current step would not be expressible in FILTR, undermining the claim that the three-language separation captures the full spectrum of production heuristics.

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

  • A pruning heuristic developed for one alignment algorithm (e.g., X-drop) can be directly applied to a different recurrence (e.g., RNA folding) without rewriting the algorithm, enabling rapid cross-domain heuristic transfer.
  • The best optimization strategy depends on input data characteristics: search traversal is 97-300x faster than antidiagonal for 1% divergence but slower at 30% divergence, meaning no single configuration is optimal and the composable design enables per-dataset tuning.
  • The search transformation converts position-indexed DP matrices into score-indexed ones automatically, deriving wavefront-algorithm-style implementations from standard recurrences without manual algorithm redesign.
  • FILTR-generated code outperforms hand-vectorized libraries partly because the shearing transformation reorganizes memory layout to make antidiagonal traversal cache-contiguous, a property the hand-tuned libraries lack.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

3 major / 7 minor

Summary. This paper introduces FILTR, a DSL and compiler for bioinformatics dynamic programming recurrences. FILTR separates the specification into three languages: a recurrence language for the mathematical model, an iteration ordering language for traversal/storage (loop reordering, shearing, search), and a pruning language for semantics-breaking approximations (static banding, dynamic X-drop/Z-drop). The compiler lowers these into a Recurrence IR and generates C++ code. The evaluation compares FILTR-generated kernels against Recuma, Bellman's Gap, and hand-optimized libraries (Ksw2, Parasail, SeqAn, WFA2) across four recurrence classes, reporting speedups from 0.95x to 30x.

Significance. The three-language separation (recurrence, scheduling, pruning) is a well-motivated design contribution that addresses a real problem: bioinformatics practitioners routinely reimplement entire algorithms when changing pruning heuristics or traversal strategies. The search transformation (Section 6.3)—automatically converting a position-indexed recurrence into a score-indexed one—is a notable technical contribution that non-trivially automates a transformation previously done by hand. The composability demonstration in Section 9.5, where X-drop pruning is transferred from alignment to RNA folding recurrences, effectively showcases the value of the separation. The staged code generation for mutually recursive data/domain recurrences (Figure 14) is technically sound. The artifact commitment (Section 12) is appropriate.

major comments (3)
  1. §9.1–9.3, Figures 19–20: All library comparisons for dynamic pruning methods (X-drop, Z-drop, WFA-Adapt) use synthetic sequences at 90% similarity. This is the regime where these heuristics prune most aggressively—the alignment path stays near the main diagonal, few cells exceed the score threshold, and the active region contracts rapidly. Table 1 already demonstrates that the search transformation's advantage collapses at higher divergence (0.45–0.72x at 30% divergence vs. 97–300x at 1%). The paper does not test library comparisons at multiple divergence levels, so we cannot assess whether the 1–2 order-of-magnitude speedups in Figures 19–20 persist at 10%, 15%, or 30% divergence. Since the headline claim ('0.95x to 30x faster across biological benchmarks') draws substantially from these dynamic pruning results, this gap is load-bearing. Adding at least one additional divergence level (
  2. §9.3, Figures 19–20: No accuracy comparison is reported for the library benchmarks. X-drop, Z-drop, and WFA-Adapt are approximate methods—different implementations may prune different cells and produce different alignments. If FILTR's X-drop variant produces lower-quality alignments than Ksw2's X-drop at the same threshold, the speed comparison is not like-for-like. The paper reports accuracy for the design-space exploration (Section 9.4, Figure 21) and heuristic transfer (Section 9.5, Figure 22) but not for the library comparisons where the headline performance claims are made. Reporting alignment accuracy (or at least confirming identical results) for the library comparisons would close this gap.
  3. Abstract and §1: The headline range '0.95x to 30x faster' appears inconsistent with Figures 19–20, which show speedups of 1–2 orders of magnitude (10–100x) over Ksw2 and SeqAn for dynamic pruning. If the 30x figure refers only to comparisons against the best-in-class library for each benchmark (e.g., WFA2 in Figure 20, where FILTR is roughly comparable), this should be stated explicitly. If the larger speedups in Figure 19 are valid, the abstract understates the results. Either way, the relationship between the headline range and the figure data needs clarification.
minor comments (7)
  1. §9.1: The paper runs each benchmark 10 times, discards the top 2 and bottom 2, and reports the mean of 6. No error bars or confidence intervals are shown in any figure. Given the log-scale plots, adding error bars (or at least noting variance) would strengthen the comparisons, especially for cases where FILTR is close to a baseline (e.g., Figure 20).
  2. Figure 14 (center): The generated C++ uses array indices 0 and 1 as double-buffer slots (diag_lo[0] = previous, diag_lo[1] = current) rather than as antidiagonal indices. While functionally correct, this is confusing to read. A comment or renaming would help readers verify the code generation.
  3. §7, paragraph beginning 'The pruning model focuses on supporting real-world heuristics': The assumption of a single contiguous active region per antidiagonal is acknowledged but its implications are not fully explored. For instance, some adaptive banding methods (e.g., abPOA [16]) maintain non-contiguous active regions. A brief discussion of what classes of algorithms fall outside the current model would help readers assess applicability.
  4. §6.3: The search transformation requires that all zero-cost transitions preserve the chosen index variable. The paper states the compiler verifies this automatically, but does not describe what happens when the check fails (error message? fallback?). A sentence clarifying the failure mode would help.
  5. Figure 18 caption: 'Spike is due to a cache line boundary' — it would help to annotate which spike is meant, as several curves are shown.
  6. §9.2: The paper states sequences are '90% similar and representative of many real genomic datasets [22].' Reference [22] (Jain et al. 2018) discusses ANI analysis of prokaryotic genomes. The 90% figure may be appropriate for within-species comparisons but is less representative for cross-species or long-read error correction scenarios. This should be qualified.
  7. §5.1: The domain recurrence mechanism is introduced with diag_lo and diag_hi as the primary example. It would help to briefly state whether domain recurrences can be arbitrary (any recurrence over the iteration domain) or are restricted to the min/max set-builder form shown in the examples.

Simulated Author's Rebuttal

3 responses · 0 unresolved

We thank the referee for a careful and constructive review. The three major comments all identify genuine gaps in the evaluation that we will address in revision. Below we respond to each point.

read point-by-point responses

  1. Referee: §9.1–9.3, Figures 19–20: All library comparisons for dynamic pruning methods use synthetic sequences at 90% similarity. This is the regime where heuristics prune most aggressively. Table 1 shows search advantage collapses at higher divergence. Need additional divergence levels for library comparisons.

    Authors: The referee is correct that the dynamic pruning library comparisons (Figures 19–20) are evaluated only at 90% similarity, and that this is the regime where X-drop, Z-drop, and WFA-Adapt prune most aggressively. We agree that this gap is load-bearing for the headline claims, since the speedups in Figures 19–20 are driven largely by how much of the matrix is pruned, which in turn depends on sequence divergence. We will add at least two additional divergence levels (10% and 30%) to the library comparisons in Section 9.3. We expect speedups to narrow at higher divergence, consistent with the trend shown in Table 1 for the search transformation. We will update the figures and discussion accordingly, and will qualify the headline performance claims to specify the divergence regime in which each speedup range holds. revision: yes

  2. Referee: §9.3, Figures 19–20: No accuracy comparison reported for library benchmarks. X-drop, Z-drop, and WFA-Adapt are approximate methods; different implementations may produce different alignments. Need to confirm like-for-like comparison.

    Authors: This is a valid concern. We report accuracy for the design-space exploration (Section 9.4, Figure 21) and heuristic transfer (Section 9.5, Figure 22) but not for the library comparisons where the headline performance claims are made. We will add accuracy comparisons for the dynamic pruning library benchmarks (X-drop vs. Ksw2/SeqAn, Z-drop vs. SeqAn, WFA-Adapt vs. WFA2). For X-drop and Z-drop, we will verify that FILTR and the library implementations produce identical alignment scores and paths when using the same drop threshold, since these heuristics are defined by the same pruning condition. If any discrepancies arise (e.g., due to differences in tie-breaking or floating-point scoring), we will report them explicitly. For WFA-Adapt, we will confirm that FILTR's generated code produces the same alignment as WFA2's adaptive heuristic at the same pruning parameters. revision: yes

  3. Referee: Abstract and §1: The headline range '0.95x to 30x faster' appears inconsistent with Figures 19–20, which show speedups of 1–2 orders of magnitude (10–100x) over Ksw2 and SeqAn for dynamic pruning. Need clarification of the relationship between the headline range and the figure data.

    Authors: The referee has identified a genuine inconsistency in how we present our results. The '0.95x to 30x' range in the abstract is drawn from the unpruned and static-pruning library comparisons (Figures 16–18), where the maximum speedup over the best library baseline is approximately 30x (antidiagonal edit distance vs. SeqAn/Parasail at large sizes) and the minimum is approximately 0.95x (FILTR row-wise banded vs. Parasail at certain sizes). However, Figures 19–20 show larger speedups (up to ~100x) for dynamic pruning against Ksw2 and SeqAn, which are not reflected in the abstract's range. Conversely, the WFA-Adapt comparison (Figure 20) shows FILTR is roughly comparable to WFA2, which is consistent with the lower end of the range. We will revise the abstract and introduction to clarify that the '0.95x to 30x' range refers specifically to unpruned and static-pruning comparisons, and that dynamic pruning comparisons yield larger speedups (up to two orders of magnitude) over Ksw2 and SeqAn. We will also note that against the best-in-class library for each benchmark (e.g., WFA2 for search-based methods), FILTR is competitive rather than dramatically faster. This will make the relationship between the headline claims and the figure data explicit. revision: yes

Circularity Check

0 steps flagged

No significant circularity; one minor self-citation to Recuma for code generation infrastructure, not load-bearing for the paper's central claims

full rationale

The paper's derivation chain is self-contained. The three novel contributions—pruning language (Section 7), search transformation (Section 6.3), and shearing (Section 6.2)—each have explicit before/after RIR rewrites shown in the paper, with no step reducing to its own inputs by construction. The search transformation is a genuine index-value inversion with compiler-verified constraints (zero-cost transitions must preserve the chosen coordinate). The pruning language lowers user-facing specifications into domain recurrences via a compilation step (Figure 13 → Figure 7 right), not by renaming. The only self-citation is to Recuma [57] (Sundram, Kjolstad) for the code generation lowering strategy (Section 8: 'We adopt the general approach of the Recuma recurrence compiler'), but this provides infrastructure, not the paper's central claims. All performance claims are validated against external libraries (Parasail, SeqAn, Ksw2, WFA2) with no author overlap, and the Recuma comparison on basic traversals confirms no overhead rather than asserting superiority. The skeptic's concern about 90% similarity test data is an experimental methodology issue, not circularity. Score 1 reflects the minor, non-load-bearing self-citation.

Axiom & Free-Parameter Ledger

3 free parameters · 4 axioms · 0 invented entities

No new physical entities, particles, or forces are introduced. The paper introduces compiler constructs (prune axis, domain recurrence, search transformation) but these are language abstractions, not postulated physical entities.

free parameters (3)
  • X-drop threshold X = user-specified (e.g., 48, 96 in benchmarks)
    Controls when cells are pruned in X-drop alignment; not fitted by the paper but chosen by the user per dataset.
  • Band width B = user-specified (e.g., 16, 32, 64 in benchmarks)
    Controls static pruning band width; user-specified, not fitted.
  • Z-drop threshold Z = user-specified
    Controls Z-drop pruning; user-specified.
axioms (4)
  • domain assumption Bioinformatics recurrences have regular dependency patterns (neighbors along rows, columns, diagonals, antidiagonals)
    Section 3, paragraph describing structural properties of recurrences in Figure 4. Enables the shearing and search transformations.
  • domain assumption Pruning decisions can be based on a single contiguous active region per step
    Section 7: 'The pruning model focuses on supporting real-world heuristics but does not allow for arbitrary pruning... it targets pruning techniques over contiguous geometric regions, assuming that at each step there is a single continuous active region.'
  • domain assumption Search transformation requires all costly transitions to have strictly positive weights (for min) and free transitions to preserve the chosen index variable
    Section 6.3: 'all costly transitions have strictly positive weights (for min)... ensuring that scores change monotonically along any path' and 'transitions of cost zero must preserve whatever indexing variable is chosen.'
  • standard math Recuma's dependency-based code lowering is correct
    Section 8: 'We adopt the general approach of the Recuma recurrence compiler [57], which constructs a dependency graph from recurrence definitions and lowers it into loop code.'

pith-pipeline@v1.1.0-glm · 32328 in / 3506 out tokens · 295868 ms · 2026-07-08T12:36:40.245855+00:00 · methodology

0 comments
read the original abstract

Many bioinformatics algorithms, such as sequence alignment and structure prediction, can be expressed as recurrence equations over a dynamic programming matrix. Efficient implementations of these algorithms for large-scale biological data often require changing the order in which matrix cells are calculated and pruning ineffectual regions of the matrix from consideration altogether, but these techniques typically complicate implementation. We introduce FILTR, a domain-specific language (DSL) and compiler framework for bioinformatics recurrences. FILTR keeps the core recurrence rules separate from the pruning and scheduling strategies, where pruning acts as an approximation to limit where in the DP matrix cells are computed, and scheduling determines the iteration order for how cells are explored. FILTR compiles these high-level descriptions into optimized C++ code that matches the performance of hand-tuned implementations while enabling rapid exploration of new heuristics. FILTR is competitive with hand-optimized sequence-alignment libraries, ranging from 0.95x to 30x faster across biological benchmarks.

Figures

Figures reproduced from arXiv: 2607.06225 by Bala Vinaithirthan, Fredrik Kjolstad, Shiv Sundram, Sneha Goenka.

Figure 1
Figure 1. Figure 1: Edit distance example [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Three edit distance alignment variants that differ in where cells are computed and in what order. [PITH_FULL_IMAGE:figures/full_fig_p004_2.png] view at source ↗
Figure 5
Figure 5. Figure 5: The recurrence language is lowered to a Recurrence [PITH_FULL_IMAGE:figures/full_fig_p005_5.png] view at source ↗
Figure 4
Figure 4. Figure 4: Example recurrences for different biology problems. [PITH_FULL_IMAGE:figures/full_fig_p005_4.png] view at source ↗
Figure 6
Figure 6. Figure 6: Grammar of Recurrence IR, extending the Recurrence Language ( [PITH_FULL_IMAGE:figures/full_fig_p006_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: Progressive refinement of the edit distance Recurrence IR. (Left) The original Cartesian formulation [PITH_FULL_IMAGE:figures/full_fig_p007_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: Grammar of Iteration Ordering Language. loopOrd, antidiag, and diag are abbreviations. Ordering commands are named rewrites on the RIR and leave the recurrence’s traceback and final value unchanged, i.e. are correctness preserving. Each transformation takes an RIR as input and pro￾duces a rewritten RIR in a new coordinate system. loopOrd, the simplest case, swaps the nesting of in￾dex variables. Shearing i… view at source ↗
Figure 9
Figure 9. Figure 9: (a, left) Cells on the same antidiagonal (constant i+j) [PITH_FULL_IMAGE:figures/full_fig_p009_9.png] view at source ↗
Figure 10
Figure 10. Figure 10: Search iteration for edit distance. Each [PITH_FULL_IMAGE:figures/full_fig_p011_10.png] view at source ↗
Figure 11
Figure 11. Figure 11: Step-by-step search expansion. Each panel shows one score level’s frontier over the original [PITH_FULL_IMAGE:figures/full_fig_p013_11.png] view at source ↗
Figure 12
Figure 12. Figure 12: Grammar of the Pruning Language. Pruning-language is syntactically RIR statements but written in user coordinates and compiled into loop order coordinates by the compiler. In two-dimensional sequence alignment, each dy￾namic programming recurrence corresponds to an alignment matrix. Matrix cells near the main diag￾onal represent alignments with relatively few inser￾tions or deletions, while cells far from… view at source ↗
Figure 13
Figure 13. Figure 13: Pruning specification for X-drop. Other pruning programs follow a similar structure. Z-drop, for instance, replaces the X-drop conditional with one that measures distance in addition to score and is described in Section 9.3. Similarly, after applying a search transformation to a recurrence, the user can derive a pruned version of the result￾ing search algorithm, such as WFA-Adapt, which prunes diagonals b… view at source ↗
Figure 14
Figure 14. Figure 14: End-to-end example of FILTR compiling X-drop edit distance, showing the user-facing input specifi [PITH_FULL_IMAGE:figures/full_fig_p017_14.png] view at source ↗
Figure 15
Figure 15. Figure 15: FILTR versus Recuma runtime (log-log) across four recurrences: edit distance, affine gap penalty [PITH_FULL_IMAGE:figures/full_fig_p018_15.png] view at source ↗
Figure 16
Figure 16. Figure 16: FILTR versus hand-optimized unpruned align [PITH_FULL_IMAGE:figures/full_fig_p019_16.png] view at source ↗
Figure 18
Figure 18. Figure 18: FILTR vs. banded alignment libraries and com [PITH_FULL_IMAGE:figures/full_fig_p020_18.png] view at source ↗
Figure 20
Figure 20. Figure 20: FILTR vs. WFA-Adapt. Log scale. We also compare against dynamic pruning strategies applied to search. The WFA-Adapt al￾gorithm [38] employs a heuristic that, at each score level, discards diagonals that fall too far from the leading diagonal (the diagonal repre￾senting the most progress through the alignment matrix). FILTR can express this data-dependent pruning and achieves performance comparable to this… view at source ↗
Figure 21
Figure 21. Figure 21: Accuracy vs. runtime for three biological conditions: resequencing (Human vs. Mouse Cytochrome [PITH_FULL_IMAGE:figures/full_fig_p021_21.png] view at source ↗
Figure 22
Figure 22. Figure 22: Each subplot shows a recurrence evaluated on four RNA sequences. Points represent different X-drop [PITH_FULL_IMAGE:figures/full_fig_p022_22.png] view at source ↗

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

73 extracted references · 73 canonical work pages · 1 internal anchor

  1. [1]

    Quim Aguado-Puig, Max Doblas, Christos Matzoros, Antonio Espinosa, Juan Carlos Moure, Santiago Marco-Sola, and Miquel Moreto. 2023. WFA-GPU: gap-affine pairwise read-alignment using GPUs.Bioinformatics39, 12 (11 2023), btad701. doi:10.1093/bioinformatics/btad701

    work page doi:10.1093/bioinformatics/btad701 2023

  2. [2]

    Altschul, Thomas L

    Stephen F. Altschul, Thomas L. Madden, Alejandro A. Schäffer, Jinghui Zhang, Zheng Zhang, Webb Miller, and David J. Lipman. 1997. Gapped BLAST and PSI-BLAST: a new generation of protein database search programs.Nucleic Acids Res.25, 17 (1997), 3389–3402. doi:10.1093/nar/25.17.3389

    work page doi:10.1093/nar/25.17.3389 1997

  3. [3]

    1993.Loop Transformations for Restructuring Compilers

    Utpal Banerjee. 1993.Loop Transformations for Restructuring Compilers. Springer

    work page 1993

  4. [4]

    Ewan Birney and Richard Durbin. 1997. Dynamite: a flexible code generating language for dynamic programming methods used in sequence comparison. InProceedings of the Fifth International Conference on Intelligent Systems for Molecular Biology. 56–64

    work page 1997

  5. [5]

    Tianqi Chen, Thierry Moreau, Ziheng Jiang, Lianmin Zheng, Eddie Yan, Haichen Shen, Yida Wang, Yuwei Hu, Cody Yu, Chris Fletcher, Luis Ceze, Carlos Guestrin, and Arvind Krishnamurthy. 2018. TVM: An Automated End-to-End Optimizing Compiler for Deep Learning. In13th USENIX Symposium on Operating Systems Design and Implementation (OSDI)

    work page 2018

  6. [6]

    Mathews, and Max Ward

    Eliot Courtney, Amitava Datta, David H. Mathews, and Max Ward. 2025. memerna: Sparse RNA folding including coaxial stacking.Journal of Molecular Biology437, 3 (2025), 168819. doi:10.1016/j.jmb.2024.168819

    work page doi:10.1016/j.jmb.2024.168819 2025

  7. [7]

    Jeffrey Daily. 2016. Parasail: SIMD c library for global, semi-global, and local pairwise sequence alignments.BMC Bioinformatics17, 1 (2016), 81. doi:10.1186/s12859-016-0930-z

    work page doi:10.1186/s12859-016-0930-z 2016

  8. [8]

    Dirk De Ridder et al. 2013. Pattern recognition in bioinformatics.Briefings in Bioinformatics14, 5 (2013), 633–647. doi:10.1093/bib/bbt020

    work page doi:10.1093/bib/bbt020 2013

  9. [9]

    Max Doblas, Oscar Lostes-Cazorla, Quim Aguado-Puig, Cristian Iñiguez, Miquel Moreto, and Santiago Marco-Sola

    work page

  10. [10]

    doi:10.1093/bioinformatics/btaf112

    QuickEd: high-performance exact sequence alignment based on bound-and-align.Bioinformatics41, 3 (2025), btaf112. doi:10.1093/bioinformatics/btaf112

    work page doi:10.1093/bioinformatics/btaf112 2025

  11. [11]

    Eddy, Anders Krogh, and Graeme Mitchison

    Richard Durbin, Sean R. Eddy, Anders Krogh, and Graeme Mitchison. 1998.Biological Sequence Analysis: Probabilistic Models of Proteins and Nucleic Acids. Cambridge University Press

    work page 1998

  12. [12]

    Sean R. Eddy. 2011. Accelerated Profile HMM Searches.PLoS Computational Biology7, 10 (2011), e1002195. doi:10. 1371/journal.pcbi.1002195

    work page 2011

  13. [13]

    Michael Farrar. 2007. Striped Smith–Waterman speeds database searches six times over other SIMD implementations. Bioinformatics23, 2 (2007), 156–161. doi:10.1093/bioinformatics/btl582

    work page doi:10.1093/bioinformatics/btl582 2007

  14. [14]

    Paul Feautrier. 1991. Dataflow Analysis of Array and Scalar References.Int. J. Parallel Program.20, 1 (1991), 23–53. doi:10.1007/BF01407931

    work page doi:10.1007/bf01407931 1991

  15. [15]

    Paul Feautrier. 1992. Some efficient solutions to the affine scheduling problem. I. One-dimensional time.International Journal of Parallel Programming21, 5 (1992), 313–347

    work page 1992

  16. [16]

    Joseph Felsenstein. 1981. Evolutionary trees from DNA sequences: a maximum likelihood approach.J. Mol. Evol.17 (1981), 368–376. doi:10.1007/BF01734359

    work page doi:10.1007/bf01734359 1981

  17. [17]

    Yan Gao, Yongzhuang Liu, Yanmei Ma, Bo Liu, Yadong Wang, and Yi Xing. 2021. abPOA: an SIMD-based C library for fast partial order alignment using adaptive band.Bioinformatics37, 15 (2021), 2209–2211. doi:10.1093/bioinformatics/btaa963

    work page doi:10.1093/bioinformatics/btaa963 2021

  18. [18]

    Generalized Slow Roll for Tensors

    Sneha D. Goenka, Yatish Turakhia, Benedict Paten, and Mark Horowitz. 2020. SegAlign: A scalable GPU-based whole genome aligner. InProceedings of SC 2020: International Conference for High Performance Computing, Networking, Storage and Analysis. IEEE Computer Society, 540–552. doi:10.1109/SC41405.2020.00043

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.1109/sc41405.2020.00043 2020

  19. [19]

    Osamu Gotoh. 1982. An improved algorithm for matching biological sequences.J. Mol. Biol.162, 3 (1982), 705–708. doi:10.1016/0022-2836(82)90398-9

    work page doi:10.1016/0022-2836(82)90398-9 1982

  20. [20]

    1997.Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology

    Dan Gusfield. 1997.Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology. Cambridge University Press

    work page 1997

  21. [21]

    Bell, et al

    James Hadfield, Colin Megill, Sidney M. Bell, et al . 2018. Nextstrain: real-time tracking of pathogen evolution. Bioinformatics34, 23 (2018), 4121–4123. doi:10.1093/bioinformatics/bty407

    work page doi:10.1093/bioinformatics/bty407 2018

  22. [22]

    Robert S. Harris. 2007.Improved Pairwise Alignment of Genomic DNA. Ph. D. Dissertation. The Pennsylvania State University

    work page 2007

  23. [23]

    Rodriguez-R, Adam M

    Chirag Jain, Luis M. Rodriguez-R, Adam M. Phillippy, Konstantinos T. Konstantinidis, and Srinivas Aluru. 2018. High throughput ANI analysis of 90K prokaryotic genomes reveals clear species boundaries.Nature Communications9, 1 (2018), 5114. doi:10.1038/s41467-018-07641-9

    work page doi:10.1038/s41467-018-07641-9 2018

  24. [24]

    Fredrik Kjolstad, Shoaib Kamil, Stephen Chou, David Lugato, and Saman Amarasinghe. 2017. The Tensor Algebra Compiler.Proc. ACM Program. Lang.1, OOPSLA, Article 77 (2017), 77:1–77:29 pages. doi:10.1145/3133901

    work page doi:10.1145/3133901 2017

  25. [25]

    Ragnar Groot Koerkamp and Pesho Ivanov. 2024. Exact global alignment using A* with chaining seed heuristic and match pruning.Bioinformatics40, 3 (2024), btae032. doi:10.1093/bioinformatics/btae032 , Vol. 1, No. 1, Article . Publication date: July 2026. 26 Bala Vinaithirthan, Shiv Sundram, Sneha Goenka, and Fredrik Kjolstad

    work page doi:10.1093/bioinformatics/btae032 2024

  26. [26]

    Konstantina Koliogeorgi, Sotirios Xydis, and Dimitrios Soudris. 2021. FPGA Acceleration of Short Read Alignment. InProceedings of the 11th International Symposium on Highly Efficient Accelerators and Reconfigurable Technologies (HEART ’21). Association for Computing Machinery, Article 13, 2 pages. doi:10.1145/3468044.3468057

    work page doi:10.1145/3468044.3468057 2021

  27. [27]

    Mikhail Kolmogorov, Jeffrey Yuan, Yu Lin, and Pavel A. Pevzner. 2019. Assembly of long, error-prone reads using repeat graphs.Nature Biotechnology37, 5 (2019), 540–546. doi:10.1038/s41587-019-0072-8

    work page doi:10.1038/s41587-019-0072-8 2019

  28. [28]

    Walenz, Konstantin Berlin, Jason R

    Sergey Koren, Brian P. Walenz, Konstantin Berlin, Jason R. Miller, Nicholas H. Bergman, and Adam M. Phillippy. 2017. Canu: scalable and accurate long-read assembly via adaptive k-mer weighting and repeat separation.Genome Research 27, 5 (2017), 722–736. doi:10.1101/gr.215087.116

    work page doi:10.1101/gr.215087.116 2017

  29. [29]

    Leslie Lamport. 1974. The parallel execution of DO loops.Commun. ACM17, 2 (1974), 83–93. doi:10.1145/360827.360844

    work page doi:10.1145/360827.360844 1974

  30. [30]

    Salzberg

    Ben Langmead and Steven L. Salzberg. 2012. Fast gapped-read alignment with Bowtie 2.Nature Methods9, 4 (2012), 357–359. doi:10.1038/nmeth.1923

    work page doi:10.1038/nmeth.1923 2012

  31. [31]

    Heng Li. 2018. Minimap2: pairwise alignment for nucleotide sequences.Bioinformatics34, 18 (2018), 3094–3100. doi:10.1093/bioinformatics/bty191

    work page doi:10.1093/bioinformatics/bty191 2018

  32. [32]

    Heng Li and Richard Durbin. 2009. Fast and accurate short read alignment with Burrows–Wheeler transform. Bioinformatics25, 14 (2009), 1754–1760. doi:10.1093/bioinformatics/btp324

    work page doi:10.1093/bioinformatics/btp324 2009

  33. [33]

    Heng Li and Richard Durbin. 2010. Fast and accurate long-read alignment with Burrows–Wheeler transform.Bioinfor- matics26, 5 (2010), 589–595. doi:10.1093/bioinformatics/btp698

    work page doi:10.1093/bioinformatics/btp698 2010

  34. [34]

    Xingyu Liao, Wufei Zhu, Juexiao Zhou, Haoyang Li, Xiaopeng Xu, and Bin Zhang. 2023. Repetitive DNA sequence detection and its role in the human genome.Communications Biology6 (2023), 954. doi:10.1038/s42003-023-05322-y

    work page doi:10.1038/s42003-023-05322-y 2023

  35. [35]

    Maskell, and Bertil Schmidt

    Yongchao Liu, Douglas L. Maskell, and Bertil Schmidt. 2009. CUDASW++: optimizing Smith-Waterman sequence database searches for CUDA-enabled graphics processing units.BMC Research Notes2 (2009), 73. doi:10.1186/1756- 0500-2-73

    work page doi:10.1186/1756- 2009

  36. [36]

    Zhuren Liu, Shouzhe Zhang, and Hui Zhao. 2024. Survey of Hardware Acceleration of Genomic Analysis.NSF PURL Technical Report(2024). https://par.nsf.gov/servlets/purl/10552567 Comprehensive review of GPUs, FPGAs, and ASICs for accelerating genomic analysis tasks including sequence alignment

    work page arXiv 2024

  37. [37]

    Kanak Mahadik, Christopher Wright, Jinyi Zhang, Milind Kulkarni, Saurabh Bagchi, and Somali Chaterji. 2016. SARVAVID: A Domain Specific Language for Developing Scalable Computational Genomics Applications. InProc. ACM Int. Conf. on Supercomputing (ICS). 34:1–34:12. doi:10.1145/2925426.2926283

    work page doi:10.1145/2925426.2926283 2016

  38. [38]

    Santiago Marco-Sola, Jordan M Eizenga, Andrea Guarracino, Benedict Paten, Erik Garrison, and Miquel Moreto. 2023. Optimal gap-affine alignment in O(s) space.Bioinformatics39, 2 (02 2023), btad074. arXiv:https://academic.oup.com/bioinformatics/article-pdf/39/2/btad074/50530586/btad074.pdf doi:10.1093/bioinformatics/btad074

    work page doi:10.1093/bioinformatics/btad074 2023

  39. [39]

    Moure, Miquel Moreto, and Antonio Espinosa

    Santiago Marco-Sola, Juan C. Moure, Miquel Moreto, and Antonio Espinosa. 2021. Fast gap-affine pairwise alignment using the wavefront algorithm.Bioinformatics37, 4 (2021), 456–463. doi:10.1093/bioinformatics/btaa777

    work page doi:10.1093/bioinformatics/btaa777 2021

  40. [40]

    McCaskill

    John S. McCaskill. 1990. The equilibrium partition function and base pair binding probabilities for RNA secondary structure.Biopolymers29, 6–7 (May–Jun 1990), 1105–1119. doi:10.1002/bip.360290621

    work page doi:10.1002/bip.360290621 1990

  41. [41]

    Aaron McKenna, Matthew Hanna, Eric Banks, et al. 2010. The Genome Analysis Toolkit: a MapReduce framework for analyzing next-generation DNA sequencing data.Genome Research20, 9 (2010), 1297–1303. doi:10.1101/gr.107524.110

    work page doi:10.1101/gr.107524.110 2010

  42. [42]

    David W. Mount. 2004.Bioinformatics: Sequence and Genome Analysis. Discusses the prevalence of substitutions (mismatches) and identical residues (matches) in biological sequence comparison

    work page 2004

  43. [43]

    Gene Myers. 1999. A fast bit-vector algorithm for approximate string matching based on dynamic programming.J. ACM46, 3 (1999), 395–415. doi:10.1145/316542.316550

    work page doi:10.1145/316542.316550 1999

  44. [44]

    National Human Genome Research Institute. [n. d.]. Base Pair (Genetics Glossary). https://www.genome.gov/genetics- glossary/Base-Pair. Accessed 2026-02-20

    work page 2026

  45. [45]

    Needleman and Christian D

    Saul B. Needleman and Christian D. Wunsch. 1970. A general method applicable to the search for similarities in the amino acid sequence of two proteins.J. Mol. Biol.48, 3 (1970), 443–453. doi:10.1016/0022-2836(70)90057-4

    work page doi:10.1016/0022-2836(70)90057-4 1970

  46. [46]

    Sergey Nurk, Sergey Koren, Arang Rhie, et al. 2022. The complete sequence of a human genome.Science376, 6588 (2022), 44–53. doi:10.1126/science.abj6987

    work page doi:10.1126/science.abj6987 2022

  47. [47]

    Jacobson

    Ruth Nussinov and Ann B. Jacobson. 1980. Fast algorithm for predicting the secondary structure of single-stranded RNA.Proc. Natl. Acad. Sci. USA77, 11 (1980), 6309–6313

    work page 1980

  48. [48]

    Pevzner, Haixu Tang, and Michael S

    Pavel A. Pevzner, Haixu Tang, and Michael S. Waterman. 2001. An Eulerian path approach to DNA fragment assembly. Proceedings of the National Academy of Sciences98, 17 (2001), 9748–9753. doi:10.1073/pnas.171285098

    work page doi:10.1073/pnas.171285098 2001

  49. [49]

    Minh Pham, Yicheng Tu, and Xiaoyi Lv. 2023. Accelerating BWA-MEM Read Mapping on GPUs. InProceedings of the 37th International Conference on Supercomputing. 155–166. doi:10.1145/3577193.3593703

    work page doi:10.1145/3577193.3593703 2023

  50. [50]

    Jonathan Ragan-Kelley, Connelly Barnes, Andrew Adams, Sylvain Paris, Frédo Durand, and Saman Amarasinghe. 2013. Halide: a language and compiler for optimizing parallelism, locality, and recomputation in image processing pipelines. InProc. ACM SIGPLAN PLDI. 519–530. doi:10.1145/2491956.2462176 , Vol. 1, No. 1, Article . Publication date: July 2026. Compili...

    work page doi:10.1145/2491956.2462176 2013

  51. [51]

    Knut Reinert, Temesgen Hailemariam Dadi, Marcel Ehrhardt, Hannes Hauswedell, Svenja Mehringer, René Rahn, Jongkyu Kim, Christopher Pockrandt, Jörg Winkler, Enrico Siragusa, Gianvito Urgese, and David Weese. 2017. The SeqAn C++ template library for efficient sequence analysis: A resource for programmers.Journal of Biotechnology 261 (2017), 157–168. doi:10....

    work page doi:10.1016/j.jbiotec.2017.07.017 2017

  52. [52]

    Isidore Rigoutsos and Aris Floratos. 1998. Combinatorial pattern discovery in biological sequences: The TEIRESIAS algorithm.Bioinformatics14, 1 (1998), 55–67. doi:10.1093/bioinformatics/14.1.55

    work page doi:10.1093/bioinformatics/14.1.55 1998

  53. [53]

    Georg Sauthoff and Robert Giegerich. 2013. Bellman’s GAP—A Language and Compiler for Dynamic Programming in Sequence Analysis.Bioinformatics29, 5 (2013), 551–560. doi:10.1093/bioinformatics/btt022

    work page doi:10.1093/bioinformatics/btt022 2013

  54. [54]

    Ariya Shajii, Ibrahim Numana ˇgić, Riyadh Baghdadi, Bonnie Berger, and Saman Amarasinghe. 2019. Seq: a high- performance language for bioinformatics.Proc. ACM Program. Lang.3, OOPSLA (2019), 125:1–125:29. doi:10.1145/ 3360551

    work page 2019

  55. [55]

    Smith and Michael S

    Temple F. Smith and Michael S. Waterman. 1981. Identification of common molecular subsequences.J. Mol. Biol.147, 1 (1981), 195–197. doi:10.1016/0022-2836(81)90087-5

    work page doi:10.1016/0022-2836(81)90087-5 1981

  56. [56]

    Martin Šošić and Mile Šikić. 2017. Edlib: a C/C++ library for fast, exact sequence alignment using edit distance. Bioinformatics33, 9 (2017), 1394–1395. doi:10.1093/bioinformatics/btw753

    work page doi:10.1093/bioinformatics/btw753 2017

  57. [57]

    Michel Steuwer, Toomas Remmelg, and Christophe Dubach. 2017. Lift: A Functional Data-Parallel IR for Performance Portability. In2017 IEEE/ACM International Symposium on Code Generation and Optimization (CGO). doi:10.1109/CGO. 2017.7863730

    work page doi:10.1109/cgo 2017

  58. [58]

    Shiv Sundram, Muhammad Usman Tariq, and Fredrik Kjolstad. 2024. Compiling Recurrences over Dense and Sparse Arrays.Proc. ACM Program. Lang.8, OOPSLA1, Article 103 (April 2024), 26 pages. doi:10.1145/3649820

    work page doi:10.1145/3649820 2024

  59. [59]

    Suzuki and M

    H. Suzuki and M. Kasahara. 2018. Introducing difference recurrence relations for faster semi-global alignment of long sequences.BMC Bioinformatics19, Suppl 1 (2018), 45. doi:10.1186/s12859-018-2014-8

    work page doi:10.1186/s12859-018-2014-8 2018

  60. [60]

    Muhammad Usman Tariq, Shiv Sundram, and Fredrik Kjolstad. 2025. REPTILE: Performant Tiling of Recurrences. Proceedings of the ACM on Programming Languages9, OOPSLA2, Article 296 (October 2025), 670–696 pages. doi:10. 1145/3763074

    work page 2025

  61. [61]

    Tarozzi et al

    M. Tarozzi et al. 2022. Identification of recurrent genetic patterns from targeted sequencing data.BMC Medical Genomics15 (2022), 56. doi:10.1186/s12920-022-01173-4

    work page doi:10.1186/s12920-022-01173-4 2022

  62. [62]

    Goenka, Gill Bejerano, and William J

    Yatish Turakhia, Sneha D. Goenka, Gill Bejerano, and William J. Dally. 2019. Darwin-WGA: A Co-processor Provides Increased Sensitivity in Whole Genome Alignments with High Speedup. In2019 IEEE International Symposium on High Performance Computer Architecture (HPCA). 359–372. doi:10.1109/HPCA.2019.00050

    work page doi:10.1109/hpca.2019.00050 2019

  63. [63]

    Esko Ukkonen. 1985. Algorithms for approximate string matching.Inform. and Control64, 1–3 (1985), 100–118. doi:10.1016/S0019-9958(85)80046-2

    work page doi:10.1016/s0019-9958(85)80046-2 1985

  64. [64]

    Nicolas Vasilache, Oleksandr Zinenko, Theodoros Karanasos, Radu Teodorescu, Tobias Grosser, Priyank Patel, Jason Ansel, Edward Yang, Zachary DeVito, Martin Johnson, Alban Desmaison, and Iain Murray. 2018. Tensor Compre- hensions: Framework-Agnostic High-Performance Machine Learning. InAdvances in Neural Information Processing Systems (NeurIPS)

    work page 2018

  65. [65]

    Linyan Xue, Xiaoke Zhang, Fei Xie, Shuang Liu, and Peng Lin. 2019. Frequent Patterns Algorithm of Biological Sequences based on Pattern Prefix-tree.International Journal of Computers Communications & Control14, 4 (2019), 574–589

    work page 2019

  66. [66]

    Katherine Yelick et al. 2020. The parallelism motifs of genomic data analysis.Philosophical Transactions of the Royal Society A378, 2166 (2020). doi:10.1098/rsta.2019.0394

    work page doi:10.1098/rsta.2019.0394 2020

  67. [67]

    Santambrogio, Steven Hofmeyr, Aydın Buluç, Leonid Oliker, and Katherine Yelick

    Alberto Zeni, Giulia Guidi, Marquita Ellis, Nan Ding, Marco D. Santambrogio, Steven Hofmeyr, Aydın Buluç, Leonid Oliker, and Katherine Yelick. 2020. LOGAN: High-Performance GPU-Based X-Drop Long-Read Alignment. InIEEE International Parallel and Distributed Processing Symposium (IPDPS). 462–471. doi:10.1109/IPDPS47924.2020.00055

    work page doi:10.1109/ipdps47924.2020.00055 2020

  68. [68]

    Daniel R Zerbino and Ewan Birney. 2008. Velvet: algorithms for de novo short read assembly using de Bruijn graphs. Genome Research18, 5 (2008), 821–829

    work page 2008

  69. [69]

    Hendrix, David H

    He Zhang, Dezhong Deng, Kai Zhao, Kaibo Liu, David A. Hendrix, David H. Mathews, and Liang Huang. 2019. LinearFold: linear-time approximate RNA folding by 5’-to-3’ dynamic programming and beam search.Bioinformatics 35, 14 (2019), i295–i304. doi:10.1093/bioinformatics/btz375

    work page doi:10.1093/bioinformatics/btz375 2019

  70. [70]

    Mathews, and Liang Huang

    He Zhang, Liang Zhang, David H. Mathews, and Liang Huang. 2020. LinearPartition: linear-time approximation of RNA folding partition function and base-pairing probabilities.Bioinformatics36 (2020). doi:10.1093/bioinformatics/btaa460

    work page doi:10.1093/bioinformatics/btaa460 2020

  71. [71]

    Zheng Zhang, Scott Schwartz, Lukasz Wagner, and Webb Miller. 2000. A greedy algorithm for aligning DNA sequences. Journal of Computational Biology7, 1–2 (2000), 203–214. doi:10.1089/10665270050081478

    work page doi:10.1089/10665270050081478 2000

  72. [72]

    Michael Zuker. 2003. Mfold web server for nucleic acid folding and hybridization prediction.Nucleic Acids Research31, 13 (2003), 3406–3415. doi:10.1093/nar/gkg595 , Vol. 1, No. 1, Article . Publication date: July 2026. 28 Bala Vinaithirthan, Shiv Sundram, Sneha Goenka, and Fredrik Kjolstad

    work page doi:10.1093/nar/gkg595 2003

  73. [73]

    Michael Zuker and Patrick Stiegler. 1981. Optimal computer folding of large RNA sequences using thermodynamics and auxiliary information.Nucleic Acids Res.9, 1 (1981), 133–148. doi:10.1093/nar/9.1.133 , Vol. 1, No. 1, Article . Publication date: July 2026

    work page doi:10.1093/nar/9.1.133 1981