Optimizing Sequence Alignment with Scored NFAs

Rasha Karakchi; Ryan Karbowniczak

REVIEW 4 major objections 5 minor 1 cited by

Optimizing Sequence Alignment with Scored NFAs

T0 review · 4 major / 5 minor · reviewed 2026-08-10 · deepseek-v4-flash

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

Pith's one-line read NAPOLY+ adds per-state score registers to an automata accelerator, letting it report the highest-scoring sequence alignment rather than just the first match.

desk verdict A plausible but unvalidated scored-NFA extension of NAPOLY: the score-update rule is never defined and no functional test is reported, so the central claim of optimal alignment is unsupported. read the letter →

arxiv 2501.02162 v1 pith:6X5U7TM2 submitted 2025-01-04 cs.ET

Ryan Karbowniczak , Rasha Karakchi This is my paper · ORCID

classification cs.ET

keywords sequencealignmentweightedfiniteautomataNFAoverlayFPGAacceleratorpatternmatchingscoretrackingprocessorViterbiscoring

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

This paper tries to show that an NFA-pattern-matching accelerator can be extended to compute optimal sequence-alignment scores without leaving the acceleration fabric. It adds to each state-transition element a score register and an arithmetic unit, so every active path carries an accumulated score, and accepting elements report the best score seen. If that works, the same FPGA overlay that finds pattern matches can also rank alignments, which matters for DNA comparisons where the highest-scoring match is the biological answer.

What carries the argument

The carrying mechanism is the scored state-transition element: each element holds a symbol-matching state bit, a score register, a configured edge-cost register, and an arithmetic unit that accumulates the incoming predecessor score with the edge cost. The start element stays active for all input symbols and new symbols inject zero scores so fresh paths can begin; accepting elements, which are not connected to the start element, emit the accumulated score when activated. This makes the overlay a hardware implementation of a weighted automaton that evaluates many alternative start-to-accept paths in parallel.

What would settle it

Feed NAPOLY+ a weighted automaton in which two start-to-accept paths with different total scores converge at a common intermediate state, then compare the reported score with the true maximum computed by dynamic programming; a reported score below that maximum would refute the optimality claim.

Watch

Extended reading notes

Core claim

The central claim is that NAPOLY+, by adding score tracking to the NAPOLY state-transition elements, can identify the highest score corresponding to the best sequence-alignment match. The paper reports that the enhanced array keeps NAPOLY's activation logic while computing an outgoing score as the incoming score plus a configured edge score, and that accepting elements report the final score once activated. In the reported experiments, the design runs on two FPGA boards across array sizes from 1K to 64K processing elements, uses 90–95% of logic cells on one board and under 85% on the other, keeps distributed-memory use comparable to the original NAPOLY, and shows maximum clock frequency decreasing as array size grows.

Load-bearing premise

The design assumes that keeping a single score per processing element, reset to zero at the start of each new input symbol, is enough to maintain the best accumulated path score when several active paths reach the same element at the same time.

Editorial extensions

If this is right

If the design is correct, sequence alignment on the overlay returns the optimal score, not merely a first match, which is the quantity needed for DNA similarity scoring.
The added arithmetic and registers raise logic-cell utilization by a few percentage points while leaving distributed-memory use close to NAPOLY's, so the capability is affordable at array sizes up to 64K.
Maximum clock frequency falls as the array grows on both tested FPGAs, with the larger board staying roughly 50–100 MHz faster, so the achievable throughput depends on array scale.
Because the score mechanism is generic over configured edge costs, the same arithmetic unit can encode different scoring rules for matches, mismatches, and gaps without changing the fabric.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

If one score register per element is truly enough, then NAPOLY+ is computing the maximum path score in the Viterbi sense, so the design could be reused for shortest-path problems or probabilistic model scoring by reinterpreting the edge weights.
The paper's evaluation measures hardware metrics, not alignment accuracy against a known-optimal software result; a direct comparison of reported scores to dynamic-programming optimal scores on benchmark sequences would settle the functional claim.
The unresolved point of how multiple incoming scores to the same element in the same cycle are combined means the architecture likely assumes one dominant predecessor per cycle; testing with converging paths would reveal whether the reported score is an upper or lower bound.
The reported resource figures exclude buffers and DRAMs, so end-to-end system scaling with the memory hierarchy may differ from the core-array trends shown here.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Desk Editor's Note

read the letter

Short version: this is a legitimate but small extension of the authors' NAPOLY overlay, and the resource-utilization/Fmax numbers look like real implementation work. But the central claim—that NAPOLY+ computes the highest-scoring alignment—is unsupported: the score-update rule is never defined, and there is no functional test anywhere. That is a load-bearing gap, not a polish issue.

What is actually new: adding a score register and arithmetic unit to each STE, with a fan-in from the start state to handle gaps and mismatches, is a plausible way to turn an NFA overlay into a weighted automaton. I don't see this exact design in the cited prior work, so the increment is real. The background on NAPOLY is clear, and the synthesis results across 1K–64K arrays on two Zynq parts are the kind of data the automata-processing community uses. I believe those numbers are real; nothing in the text signals fabrication.

The soft spots are serious. Section 3 says each STE+ "combines activation signals from all f predecessors" and calculates an outgoing score "based on the incoming score from its predecessor and its edge score," but it never says what happens when two predecessors are active with different accumulated scores. In a weighted automaton, the whole game is the max-plus recurrence S_q = max_p (S_p + w(p,q)); without stating that, the claimed optimality has no mathematical basis. The phrase "initialize the incoming scores to zero for every new symbol" makes it worse—it sounds like per-symbol reset rather than DP accumulation. Section 4 reports only LUT/FF/memory usage and Fmax; no simulation, no trace, no comparison to a reference alignment algorithm. The abstract and conclusion say NAPOLY+ "outperforms" NAPOLY in identifying best matches, but no functional comparison is shown. There are also unfinished citation placeholders ("[?]"), which suggests the manuscript was not ready.

Who should read it: FPGA/automata researchers looking at scored-automata overlays might skim it for the resource data, but I wouldn't trust the functional claims yet. For peer review: not in current form. The right move is a desk reject with an invitation to resubmit after specifying the score-combination rule, adding functional verification on known examples (e.g., the +2/-1/-2 DNA alignment from the intro), and cleaning up the references. Then it would be a reasonable short paper.

Referee Report

4 major / 5 minor

Summary. This manuscript describes NAPOLY+, a modification of the NAPOLY FPGA-based nondeterministic finite automaton overlay. Each state-transition element is extended with a register for a score/weight and an arithmetic unit, with the stated goal of making the accelerator report the highest-scoring match, e.g., the optimal score in DNA sequence alignment. Section 3 gives a high-level description of the STE+ and the array, and Section 4 reports FPGA resource utilization, distributed-memory usage, fan-out, Fmax, and throughput for array sizes from 1K to 64K on ZCU102 and ZCU104 boards, compared against the original NAPOLY. No functional or simulation results for alignment scores are reported.

Significance. The intended contribution is potentially useful: scoring an NFA overlay in a max-plus sense would extend automata processors beyond Boolean match detection and could benefit sequence alignment and related applications. The paper also provides resource-scaling data at nontrivial array sizes. However, the manuscript does not define the score-update rule essential to correct computation, does not provide functional verification, and leaves citation placeholders and unclear relations to prior work. Because none of the reported measurements concerns correctness of the computed scores, the central claim is currently unsupported. No machine-checked proofs, source code, or test vectors are shipped.

major comments (4)

[Section 3, STE+ arithmetic and score update] The paper never defines the rule by which an STE+ combines multiple incoming scores. After stating that each STE+ 'combines activation signals from all f predecessors,' it says only that the outgoing score is calculated 'based on the incoming score from its predecessor and its edge score' (singular). For weighted automata, optimal alignment requires the max-plus recurrence S_q(t) = max_{p in pred(q)} (S_p(t-1) + w(p,q)). The text does not state whether the arithmetic unit implements this maximum, a sum, or first-arrival selection. The sentence 'we initialize the incoming scores to zero for every new symbol' is also ambiguous: if all scores are reset on every symbol, accumulated path scores cannot propagate across multiple symbols; if only new-start paths are reset, that exception needs to be part of an explicit update equation. Without this definition, the claimed computation of highest alignment scores is not established.
[Section 4, functional validation] All experimental results in Section 4 are resource and timing metrics: LUT utilization, distributed memory, fan-out, Fmax, and throughput. There is no simulation trace, no known-answer test, no comparison of NAPOLY+ scores against a reference alignment algorithm such as Needleman-Wunsch or against the authors' earlier scored-NFA implementation, and no demonstration that accepting STEs report the same score as a software baseline. The abstract's statement that 'results showing that NAPOLY+ offers superior functionality' is therefore not supported by the data presented.
[Section 3, start-state and accepting-state connections] The special connections for the start STE+ are described only informally: 'we designed all (STE+)s to be connected to the start STE+' but accepting STEs 'have no connection with the start state.' This raises questions about how a match that begins at the start state and ends at an accepting state is scored when the accepting state can only be reached through non-start predecessors, and how gap penalties on multi-symbol paths are applied when the start state is continuously active. A precise description of the interconnection topology and the handling of new-start path scores is needed to evaluate the design.
[Section 3 and References, completeness] The manuscript contains two unresolved citation placeholders ('[?]') in Section 3 and cites the authors' previous arXiv preprint [12] without explaining the incremental contribution of NAPOLY+ over that work. This prevents a reviewer from verifying novelty and reproducibility. The text as submitted is not complete enough for publication.

minor comments (5)

[Abstract and throughout] The spacing in 'NF A' is inconsistent (e.g., Abstract and Section 2.1); use 'NFA' consistently throughout the manuscript.
[Section 4, device names and units] The text mixes 'zynq102'/'zynq104' with 'ZCU102'/'ZCU104', and states '6.2 Mb Mb of distributed memory' with a duplicated unit; these should be standardized and corrected.
[Figures 5-8] The figures referenced in Section 4 are not included in the submitted text; each figure needs axis labels, units, and clear descriptions of what is plotted (e.g., point markers versus lines) so the resource data can be interpreted.
[Section 3, score representation] The description of the score registers and arithmetic unit should specify the bit width and signed representation, since the motivating example uses negative scores for mismatches and gaps.
[Section 2.2, weighted automata versus ANML] The weighted automaton definition in Section 2.2 assigns weights to transitions, while NAPOLY uses ANML with labels on states; the mapping between these two representations and the resulting edge-score register in STE+ should be stated explicitly.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: NAPOLY+ extends the authors' earlier NAPOLY with scored STEs, but the claimed best-match scoring is not derived by construction from its inputs.

full rationale

The paper's contribution is an engineering extension rather than a derivation that reduces to its own inputs. NAPOLY+ adds per-STE score registers and an arithmetic unit to the previously published NAPOLY overlay; the abstract's 'highest score' claim is a design goal, and the reported evaluation is resource utilization and Fmax, not a statistical fit followed by a prediction. The score-update rule is under-specified (no equation defines how multiple predecessor scores combine), and no functional simulation validates the alignment result; these are correctness and evidence gaps, not circularity. Citations to the authors' own NAPOLY papers and to a prior scored-NFA preprint supply background and design context, but no load-bearing step is forced by a self-citation chain, and no parameter is fitted then renamed as a prediction. The central claim is therefore unverified rather than equivalent to an input by definition, so the circularity score is 0.

Assumptions & free parameters 0 free parameters · 3 assumptions · 1 invented entities

The central claim rests on an unverified hardware design assumption (single-score-per-state updates) and standard domain assumptions about additive scoring. No fitted free parameters are used; the design is an architectural proposal rather than a data-fitting exercise.

assumptions (3)

domain assumption The start state remains active at all times, and a new match can begin at every input symbol.
Required for exploring multiple alignment paths concurrently; stated in Section 3.
domain assumption Additive transition scores (match, mismatch, gap) with maximization yield the biologically optimal alignment.
Standard assumption for sequence alignment; introduced in Section 1.
ad hoc to paper A single score register per STE+ can represent the best score for that state at each point in time.
This is the core design premise for NAPOLY+; the paper does not analyze how it handles converging paths with different scores.

invented entities (1)

STE+ (scored State Transition Element)
purpose: Adds score storage and arithmetic to NAPOLY's STE so the array can accumulate and report alignment scores.
The claimed best-match capability is untested; no independent validation of the STE+ behavior is provided.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Optimizing Sequence Alignment with Scored NFAs." pith.science (2026). https://pith.science/paper/6X5U7TM2

@misc{pith2026250102162,
  author       = {Pith},
  title        = {Pith review of: Optimizing Sequence Alignment with Scored NFAs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/6X5U7TM2}},
  note         = {Machine review of arXiv:2501.02162}
}

read the original abstract

The rapid increase in symbolic data has underscored the significance of pattern matching and regular expression processing. While nondeterministic finite automata (NFA) are commonly used for these tasks, they are limited to detecting matches without determining the optimal one. This research expands on the NAPOLY pattern-matching accelerator by introducing NAPOLY+, which adds registers to each processing element to store variables like scores, weights, or edge costs. This enhancement allows NAPOLY+ to identify the highest score corresponding to the best match in sequence alignment tasks through the new-added arithmetic unit in each processor element. The design was evaluated against the original NAPOLY, with results showing that NAPOLY+ offers superior functionality and improved performance in identifying the best match. The design was implemented and tested on zynq102 and zynq104 FPGA devices, with performance metrics compared across array sizes from 1K to 64K processing elements. The results showed that memory usage increased proportionally with array size with Fmax decreasing as the array size grew on both platforms. The reported findings focus specifically on the core array, excluding the impact of buffers and DRAMs.

Figures

Figures reproduced from arXiv: 2501.02162 by the authors.

**Figure 1.** Example of NFA-ANML conversion This inefficiency has driven interest in Domain-Specific Architectures (DSA) that can effectively utilize NFA parallelism. Many current automata processors are built using specialized hardware such as FPGAs [3] and ASICs [7, 8], which enable efficient parallel processing. These specialized processors are faster than general-purpose CPUs for specific tasks and offer better energy effici… view at source ↗

**Figure 2.** Tracking multiple paths simultaneously When active, an STE transmits activation signals to its f outputs. These signals are combined with ”interconnect configuration” bits via AND gates before being routed to the OR gates of the successor STEs. The configuration bits define the edges (connections) between states mapped onto STEs, forming a point-to-point programmable interconnect. Each wire and its associated config… view at source ↗

**Figure 3.** NAPOLY+ layout of STE+ within the design [PITH_FULL_IMAGE:figures/full_fig_p003_3.png] view at source ↗

Figures from the paper (5 more)

**Figure 4.** Figure 4: The original STE design compared to the STE+ design of NAPOLY+ [PITH_FULL_IMAGE:figures/full_fig_p004_4.png]

**Figure 5.** Figure 5: Percentage of Logical Cells utilized across each design configuration [PITH_FULL_IMAGE:figures/full_fig_p005_5.png]

**Figure 6.** Figure 6: The distributed memory usage for each design configuration [PITH_FULL_IMAGE:figures/full_fig_p005_6.png]

**Figure 7.** Figure 7: Maximum fanout allowed for each design configuration [PITH_FULL_IMAGE:figures/full_fig_p005_7.png]

**Figure 8.** Figure 8: Maximum frequency and Performance of NAPOLY+ on ZCU104 and ZCU102 FPGA boards [PITH_FULL_IMAGE:figures/full_fig_p006_8.png]

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

ML-Based Automata Simplification for Symbolic Accelerators
cs.LG 2025-07 reject novelty 2.0 of 10

AutoSlim prunes NFA transitions with a Random Forest that simply learns a score threshold, reporting hardware savings but no evidence that matching semantics are preserved.

Reference graph

Works this paper leans on

20 extracted references · 18 canonical work pages · cited by 1 Pith paper

[12]

A scored non-deterministic finite automata processor for sequence alignment, 2024

Ryan Karbowniczak and Rasha Karakchi. A scored non-deterministic finite automata processor for sequence alignment, 2024. arXiv preprint arXiv:2410.19758

arXiv 2024
[1]

Bradshaw, Rasha Karakchi, and Jason D

Jordan A. Bradshaw, Rasha Karakchi, and Jason D. Bakos. Two-hit filter synthesis for genomic database search. In 2016 IEEE 24th Annual International Symposium on Field-Programmable Cus- tom Computing Machines (FCCM) , volume 52–55, pages 165–172, 2016. 6

work page 2016
[2]

Bradshaw, and Jason D

Rasha Karakchi, Jordan A. Bradshaw, and Jason D. Bakos. High-level synthesis of a genomic database search engine. In 2016 International Conference on ReConFigurable Computing and FP- GAs (ReConFig), pages 1–6, 2016

work page 2016
[3]

Rasha Karakchi and Jason D. Bakos. Napoly: A non-deterministic automata processor overlay. ACM Transactions on Reconfigurable Technology and Systems, 16:1–25, 2023

2023
[4]

Robotomata: A framework for approximate pattern matching of big data on an automata processor

Xiaodong Yu, Kaixi Hou, Hao Wang, and Wu chun Feng. Robotomata: A framework for approximate pattern matching of big data on an automata processor. In 2017 IEEE International Conference on Big Data (Big Data) , pages 283–292, 2017

work page 2017
[5]

Richards, and Jason D

Rasha Karakchi, Lothrop O. Richards, and Jason D. Bakos. A dynamically reconfigurable automata processor overlay. In 2017 International Conference on ReConFigurable Computing and FPGAs (ReConFig), pages 1–8, 2017

work page 2017
[6]

An overlay architecture for pattern matching

Rasha Karakchi, Charles Daniels, and Jason Bakos. An overlay architecture for pattern matching. In 2019 IEEE 30th International Conference on Application-specific Systems, Architectures and Processors (ASAP), volume 2160–052X, pages 165–172, 2019

work page 2019
[7]

Finding motifs in biological sequences using the micron automata processor

Indranil Roy and Srinivas Aluru. Finding motifs in biological sequences using the micron automata processor. In 2014 IEEE 28th International Parallel and Distributed Processing Symposium , pages 415–424, 2014

work page 2014

Show all 20 references

[8]

K. Wang, K. Angstadt, C. Bo, N. Brunelle, E. Sadredini, T. Tracy, J. Wadden, M. Stan, and K. Skadron. An overview of micron’s automata processor. In Proceedings of the 11th IEEE/ACM/IFIP International Conference on Hardware/Software Codesign and System Synthe- sis, 2017

2017
[9]

Weighted automaton, 2024

Wikipedia Contributors. Weighted automaton, 2024. Accessed: 2024-12-29

2024
[10]

Weighted automata algorithms

Mehryar Mohri. Weighted automata algorithms. In Handbook of weighted automata, pages 213–254. Springer, 2009

2009
[11]

Handbook of Weighted Automata

Bakh Khoussainov and Wei Li, editors. Handbook of Weighted Automata . Springer, 2020

2020
[13]

Weighted automata algorithms

Mehryar Mohri. Weighted automata algorithms. IEEE Transactions on Neural Networks and Learning Systems, 23(1):17–28, 2012

2012
[14]

Bakos and Rasha Karakchi

Jason D. Bakos and Rasha Karakchi. nfatool, 2023. https://github.com/HeRCLab/nfatool

2023
[15]

An efficient and scalable semiconductor architecture for parallel automata processing

Paul Dlugosch, Dave Brown, Paul Glendenning, Michael Leventhal, and Harold Noyes. An efficient and scalable semiconductor architecture for parallel automata processing. IEEE Transactions on Parallel and Distributed Systems , 25(12):3088–3098, 2014

2014
[16]

Approximating proba- bilistic models as weighted finite automata

Ananda Theertha Suresh, Brian Roark, Michael Riley, and Vlad Schogol. Approximating proba- bilistic models as weighted finite automata. 2021

2021
[17]

Quasi-distances and weighted finite automata

Timothy Ng, David Rappaport, and Kai Salomaa. Quasi-distances and weighted finite automata. In International Workshop on Descriptional Complexity of Formal Systems , pages 209–219. Springer, 2015

2015
[18]

Zcu104 evaluation board user guide, 2019

Xilinx Inc. Zcu104 evaluation board user guide, 2019. Retrieved from https://www.mouser.com/datasheet/2/903/ug1267-zcu104-eval-bd-1596428.pdf

2019
[19]

Zcu102 evaluation board user guide, 2019

Xilinx Inc. Zcu102 evaluation board user guide, 2019. Retrieved from https://www.mouser.com/pdfDocs/ug1182-zcu102-eval-bd.pdf

2019
[20]

A scratchpad spiking neural network accelerator

Rasha Karakchi. A scratchpad spiking neural network accelerator. In 2024 IEEE 3rd International Conference on Computing and Machine Intelligence (ICMI) , pages 1–5. IEEE, 2024. 7

2024

Pith tools

Reviewed August 10, 2026 · model on record in the stance chip above.

[1] [12]

A scored non-deterministic finite automata processor for sequence alignment, 2024

Ryan Karbowniczak and Rasha Karakchi. A scored non-deterministic finite automata processor for sequence alignment, 2024. arXiv preprint arXiv:2410.19758

arXiv 2024

[2] [1]

Bradshaw, Rasha Karakchi, and Jason D

Jordan A. Bradshaw, Rasha Karakchi, and Jason D. Bakos. Two-hit filter synthesis for genomic database search. In 2016 IEEE 24th Annual International Symposium on Field-Programmable Cus- tom Computing Machines (FCCM) , volume 52–55, pages 165–172, 2016. 6

work page 2016

[3] [2]

Bradshaw, and Jason D

Rasha Karakchi, Jordan A. Bradshaw, and Jason D. Bakos. High-level synthesis of a genomic database search engine. In 2016 International Conference on ReConFigurable Computing and FP- GAs (ReConFig), pages 1–6, 2016

work page 2016

[4] [3]

Rasha Karakchi and Jason D. Bakos. Napoly: A non-deterministic automata processor overlay. ACM Transactions on Reconfigurable Technology and Systems, 16:1–25, 2023

2023

[5] [4]

Robotomata: A framework for approximate pattern matching of big data on an automata processor

Xiaodong Yu, Kaixi Hou, Hao Wang, and Wu chun Feng. Robotomata: A framework for approximate pattern matching of big data on an automata processor. In 2017 IEEE International Conference on Big Data (Big Data) , pages 283–292, 2017

work page 2017

[6] [5]

Richards, and Jason D

Rasha Karakchi, Lothrop O. Richards, and Jason D. Bakos. A dynamically reconfigurable automata processor overlay. In 2017 International Conference on ReConFigurable Computing and FPGAs (ReConFig), pages 1–8, 2017

work page 2017

[7] [6]

An overlay architecture for pattern matching

Rasha Karakchi, Charles Daniels, and Jason Bakos. An overlay architecture for pattern matching. In 2019 IEEE 30th International Conference on Application-specific Systems, Architectures and Processors (ASAP), volume 2160–052X, pages 165–172, 2019

work page 2019

[8] [7]

Finding motifs in biological sequences using the micron automata processor

Indranil Roy and Srinivas Aluru. Finding motifs in biological sequences using the micron automata processor. In 2014 IEEE 28th International Parallel and Distributed Processing Symposium , pages 415–424, 2014

work page 2014