Pith. sign in

REVIEW 3 major objections 7 minor 73 references

Compiling Bioinformatics Recurrences

T0 review · 3 major / 7 minor · reviewed 2026-07-08 · glm-5.2

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

Pith's one-line read Separate recurrence from pruning, get hand-tuned speed

desk verdict 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. read the letter →

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

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

The pith

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

The reading

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.

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.

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

Extended reading notes

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

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.

Editorial extensions

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.
Share X Bluesky LinkedIn Reddit HN

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 · score 1.0 of 10

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.

Assumptions & free parameters 3 free parameters · 4 assumptions · 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.
assumptions (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.'

how reviews work

0 comments
Cite this review

Pith. "Pith review of Compiling Bioinformatics Recurrences." pith.science (2026). https://pith.science/paper/2PITUO5C

@misc{pith2026260706225,
  author       = {Pith},
  title        = {Pith review of: Compiling Bioinformatics Recurrences},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/2PITUO5C}},
  note         = {Machine review of arXiv:2607.06225}
}
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 the authors.

Figure 1
Figure 1. Edit distance example [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
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. The recurrence language is lowered to a Recurrence [PITH_FULL_IMAGE:figures/full_fig_p005_5.png] view at source ↗
Figures from the paper (16 more)
Figure 4
Figure 4. Figure 4: Example recurrences for different biology problems. [PITH_FULL_IMAGE:figures/full_fig_p005_4.png]
Figure 6
Figure 6. Figure 6: Grammar of Recurrence IR, extending the Recurrence Language ( [PITH_FULL_IMAGE:figures/full_fig_p006_6.png]
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]
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 i…
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]
Figure 10
Figure 10. Figure 10: Search iteration for edit distance. Each [PITH_FULL_IMAGE:figures/full_fig_p011_10.png]
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]
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 al…
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 transfor…
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]
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]
Figure 16
Figure 16. Figure 16: FILTR versus hand-optimized unpruned align [PITH_FULL_IMAGE:figures/full_fig_p019_16.png]
Figure 18
Figure 18. Figure 18: FILTR vs. banded alignment libraries and com [PITH_FULL_IMAGE:figures/full_fig_p020_18.png]
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￾sentin…
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]
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]

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

73 extracted references · 73 canonical work pages

  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

Show all 73 references
  1. [9]

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

  2. [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

    2025 doi

  3. [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

    1998

  4. [12]

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

    2011

  5. [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

    2007 doi

  6. [14]

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

    1991 doi

  7. [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

    1992

  8. [16]

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

    1981 doi

  9. [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

    2021 doi

  10. [18]

    Goenka, Yatish Turakhia, Benedict Paten, and Mark Horowitz

    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. ...

    2020 doi arXiv

  11. [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

    1982 doi

  12. [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

    1997

  13. [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

    2018 doi

  14. [22]

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

    2007

  15. [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

    2018 doi

  16. [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

    2017 doi

  17. [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, S...

    2024 doi

  18. [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,...

    2021 doi

  19. [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

    2019 doi

  20. [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

    2017 doi

  21. [29]

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

    1974 doi

  22. [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

    2012 doi

  23. [31]

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

    2018 doi

  24. [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

    2009 doi

  25. [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

    2010 doi

  26. [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

    2023 doi

  27. [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

    2009 doi

  28. [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 seque...

    2024

  29. [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...

    2016 doi

  30. [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/...

    2023 doi

  31. [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

    2021 doi

  32. [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

    1990 doi

  33. [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

    2010 doi

  34. [42]

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

    2004

  35. [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

    1999 doi

  36. [44]

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

    2026

  37. [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

    1970 doi

  38. [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

    2022 doi

  39. [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

    1980

  40. [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

    2001 doi

  41. [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

    2023 doi

  42. [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...

    2013 doi

  43. [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: ...

    2017 doi

  44. [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

    1998 doi

  45. [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

    2013 doi

  46. [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

    2019

  47. [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

    1981 doi

  48. [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

    2017 doi

  49. [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

    2017 doi

  50. [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

    2024 doi

  51. [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

    2018 doi

  52. [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

    2025

  53. [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

    2022 doi

  54. [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. d...

    2019 doi

  55. [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

    1985 doi

  56. [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 Lea...

    2018

  57. [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

    2019

  58. [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

    2020 doi

  59. [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...

    2020 doi

  60. [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

    2008

  61. [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

    2019 doi

  62. [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

    2020 doi

  63. [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

    2000 doi

  64. [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 Fre...

    2003 doi

  65. [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

    1981 doi

Pith tools

Reviewed July 8, 2026 · model on record in the stance chip above.