Harp: Leveraging Quasi-Sequential Characteristics to Accelerate Sequence-to-Graph Mapping of Long Reads

Yichi Zhang, Dibei Chen, Gang Zeng, Jianfeng Zhu, Zhaoshi Li, Longlong Chen and 2 others

Modern genomics has shifted from lining reads up against a single reference genome to aligning them against a graph that captures the genetic variation of a whole population — far more accurate, but the graph structure makes the alignment dramatically slower and moves the bottleneck to graph processing, which existing accelerators were not built for; this work from Tsinghua builds Harp, which exploits the fact that such genome graphs are almost entirely linear with only occasional branches to accelerate sequence-to-graph mapping of long reads.

The argument in one glance

Problem

Genomics moved from a linear reference to a graph, and it is slow

Read mapping places the fragments a sequencer produces onto a reference genome. The field has shifted from mapping against a single linear reference (sequence-to-sequence) to mapping against a genome graph that captures a whole population's genetic variation (sequence-to-graph). The graph is far more accurate, but aligning a read to a branching graph instead of a line is much more expensive, and the graph processing becomes the dominant cost — moving the performance hotspot to a place that prior tools and accelerators were not built for.
What people did

Run sequence-to-graph mapping in software or on linear accelerators

Software mappers extend read alignment to genome graphs, and prior hardware accelerators speed up read mapping. But those accelerators were designed for sequence-to-sequence mapping, targeting the classic sequence-alignment kernel that dominated when the reference was a single line.
Why it fell short

The bottleneck shifted to graph processing they never targeted

Sequence-to-graph mapping incurs high graph-processing overhead that sequence-to-sequence mapping never had, and this causes an unnoticed shift of the performance hotspot away from the sequence-alignment kernel that existing software and hardware accelerators were tuned for. As a result, those accelerators speed up the wrong part, and both software and hardware struggle with the new dominant cost of navigating the graph.
This paper's idea

Exploit that genome graphs are almost entirely linear

Harp is built on the observation that a genome graph is quasi-sequential: because genetic variation is sparse, the graph is made of long linear stretches punctuated by only occasional branches. Harp exploits this to accelerate sequence-to-graph mapping of long reads — handling the common linear stretches with a fast, sequence-like path and invoking the expensive graph-processing logic only at the rare branch points, so it attacks the true graph-processing bottleneck rather than the old linear kernel.

Why this problem is worth solving

To see why the move to graphs matters and why it is costly, start with what a genome graph is and why the field adopted it.

A sequencer does not read a genome in one piece; it produces many short or long fragments called reads, and read mapping is the task of figuring out where each read came from by aligning it against a reference. For decades the reference was a single linear sequence — one representative human genome, say. The problem is that no two individuals have exactly the same genome; they differ by millions of variants (single-letter changes, insertions, deletions, larger rearrangements). A read carrying a variant that is not in the linear reference aligns poorly or to the wrong place, a systematic distortion called reference bias. The fix that has swept the field is the pangenome graph: instead of one sequence, use a graph whose nodes are stretches of sequence and whose edges connect them into alternative paths, so that a common variant is represented as a branch offering both the reference and the alternative. Aligning a read against this graph — sequence-to-graph mapping — lets it match whichever path corresponds to the individual it came from, dramatically reducing reference bias and improving accuracy. This accuracy is why the paradigm shifted, and why making sequence-to-graph mapping fast is now a central problem in computational genomics.

The trouble is that a graph is a fundamentally harder thing to align against than a line.

Classic sequence-to-sequence alignment is, at its core, a matter of sliding a read along a linear reference and scoring how well they match, a computation with a regular, predictable structure that decades of software and hardware have been tuned to accelerate. Aligning to a graph breaks that regularity. At every point the aligner must consider not a single preceding position but potentially several, wherever edges merge or split, and it must traverse the graph’s topology — following branches, weighing alternative paths — rather than marching straight down a sequence. This graph processing (navigating nodes and edges, resolving which path a read follows) is irregular, memory-intensive, and expensive, and it is work that simply does not exist in the linear case. The consequence, as the paper emphasizes, is a quiet but decisive shift of the performance hotspot: where sequence-to-sequence mapping spent its time in the well-understood alignment kernel, sequence-to-graph mapping spends it in graph processing. Prior accelerators, built to speed up that alignment kernel, therefore optimize a part that is no longer the bottleneck, leaving the new dominant cost untouched. Recognizing and attacking that shifted hotspot is exactly what Harp sets out to do.

What people did before, and where it broke

Linear sequence-to-sequence mapping. Align each read against a single linear reference genome, the long-standing approach. Where it broke. A single reference cannot represent population variation, so reads carrying variants suffer reference bias and map inaccurately — the very problem genome graphs were adopted to fix.
Software sequence-to-graph mappers. Extend read alignment to pangenome graphs to gain accuracy. Where it broke. The graph processing they add is expensive and irregular, so mapping becomes far slower, and software alone cannot close the performance gap.
Prior read-mapping hardware accelerators. Build specialized hardware to speed up read mapping. Where it broke. They were designed for sequence-to-sequence mapping and target the classic alignment kernel; on a graph reference the bottleneck has moved to graph processing, which they do not accelerate, so they optimize the wrong part.
The gap. No approach efficiently handled the new dominant cost of sequence-to-graph mapping: something that recognizes the graph-processing hotspot and accelerates it, rather than the linear-alignment kernel that used to dominate. Exploiting the near-linear structure of genome graphs to do exactly that is what Harp contributes.

How Harp works

From graph processing everywhere to graph work only at branches

↓ →
new
↓ →
new
↓ →
new
↓ →
new
↓ →
new

The idea

Exploit that the graph is sparse in branches — mostly linear chains with rare cross-links. Genetic variation is uncommon relative to the genome’s length, so a pangenome graph is overwhelmingly a set of long linear runs with only a thin scattering of branch points, and Harp keys its work to that sparsity rather than treating every position as a full graph node. Exploiting that a structure is mostly linear with only sparse deviations from linearity, and building the fast path around that near-linearity, is the same insight the concurrency data-structure work covered elsewhere on this site is built on, whose whole efficiency comes from a graph being mostly independent chains with only a sparse set of cross-chain edges.

Give the common case a cheap fast path and reserve the expensive machinery for the rare hard case. Most of a read aligns along a single unambiguous path, which a sequence-like routine handles cheaply, so Harp spends the costly graph-processing logic only at the branches where alternatives actually exist. Handling the dominant common case on a cheap path and invoking the expensive path only for the rare cases that truly need it is exactly the strategy the low-bit language-model serving work covered elsewhere on this site uses, running the overwhelming majority of values through the cheap fast format and reserving the costly high-precision handling for the rare outliers.

Aim the specialized hardware at the bottleneck that actually moved. The performance hotspot shifted from the alignment kernel to graph processing, so Harp targets graph processing directly rather than re-optimizing the kernel prior accelerators already sped up. Co-designing a specialized mechanism to attack the true dominant cost that generic or previous-generation approaches leave untouched is the same discipline the virtualized-memory-translation work covered elsewhere on this site follows, building hardware aimed squarely at the page-walk bottleneck that ordinary caches and prefetchers could not eliminate.

Following a long read through Harp

Mapping one long read to a pangenome graph

Tracing one read shows the cheap linear path and the rare branch handling.

Step 1 of 5

A long read arrives to be aligned to a graph

A long, error-prone read must be aligned against a genome graph whose nodes are stretches of sequence and whose edges connect them into the alternative paths of a population's variation.

Long reads span many graph segments, so most of the read lies along linear runs.

Why it works

Variation is sparse, so the graph is mostly linear. Genetic variants are uncommon relative to the genome’s length → so a pangenome graph is long linear runs with only occasional branches → so most of the mapping work is effectively sequential rather than graph-shaped.
Linear alignment is far cheaper than graph alignment. Aligning along a single path is a regular, well-understood computation → so handling the common linear stretches with a sequence-like fast path avoids the graph machinery where it is not needed → so the bulk of each read is aligned cheaply.
Branches are where the graph cost is justified. Alternative paths only matter at the sparse branch points → so invoking the full graph-processing logic only there spends the expensive work exactly where it counts → so accuracy is preserved without paying graph cost everywhere.
The specialized effort hits the real bottleneck. The performance hotspot moved from the alignment kernel to graph processing → so a design that targets graph processing attacks the cost that actually dominates → so it accelerates where prior linear-alignment accelerators could not.
Long reads amortize the cheap path. A long read spans many graph segments and many linear stretches → so the cheap sequence-like alignment is amortized over long common runs → so the per-read cost drops even for long, error-prone reads.

What it costs (trade-offs and scope)

The benefit rests on the graph being mostly linear. Harp exploits the sparsity of branching; a reference graph that is densely branching — highly variable regions or complex structural variation — offers less quasi-sequential structure and less room to accelerate.
It is a specialized design for one task. Harp targets sequence-to-graph mapping of long reads; it is not a general graph processor, and other genomics kernels or short-read mapping would need their own treatment.
Splitting linear from branch handling adds control complexity. Detecting where the graph is effectively linear versus where it branches, and switching between the cheap and expensive paths, is machinery that must be both correct and efficient, and mis-splitting could cost accuracy or speed.
Long reads are error-prone. The approach must tolerate the high error rates of long-read sequencing, which make deciding which path a read follows at a branch genuinely hard, so the branch-handling logic carries the accuracy burden.
It accelerates one stage of the pipeline. Read mapping is a single step; downstream analyses such as variant calling and assembly are separate stages that still apply and are not addressed here.
The gains depend on the specific graphs and read sets. How much Harp helps varies with how linear a given pangenome graph is and with the read data’s characteristics, so different genomes or sequencing technologies would need their own evaluation.

The evaluation

Three ways to map reads to a reference

Property	Linear (sequence-to-sequence)	Naive sequence-to-graph
Reference used	A single linear genome	A population genome graph
Handles genetic variants		Accurately
Where the time goes	Sequence alignment
How the graph is processed	No graph

Three ways to map reads to a reference. Sequence-to-graph mapping gains accuracy over a linear reference by representing population variation as a graph, but its graph processing becomes the dominant cost and shifts the performance hotspot away from what prior accelerators target. Harp exploits the quasi-sequential structure of genome graphs — long linear stretches with only occasional branches — to align the common linear runs cheaply and invoke graph processing only at branches, reporting accelerated sequence-to-graph mapping of long reads over prior software and hardware approaches. (This explainer is drawn from the paper's abstract and standard background on read mapping; the full text, including the accelerator's design and its measured speedups, was not available.)Underlined values explain themselves when clicked.

Where this stops working

What to keep in mind

Harp targets a real and timely problem: as genomics shifts from linear references to pangenome graphs for accuracy, the cost of aligning reads to a graph explodes and the performance hotspot moves to graph processing, which the accelerators built for the old linear kernel do not address. Harp’s insight is that genome graphs are quasi-sequential — because variation is sparse, they are mostly long linear runs with only occasional branches — so it can align the common linear stretches cheaply and spend expensive graph processing only at the rare branches, aiming its specialized effort at the bottleneck that actually moved. Read it with its scope. The advantage depends on the graph being mostly linear; densely branching regions offer less to exploit. It is a specialized design for long-read sequence-to-graph mapping, not a general graph engine, and it accelerates one pipeline stage. Splitting linear from branch handling adds complexity, and long-read error rates make the branch decisions genuinely hard. Importantly, this page is written from the paper’s brief abstract and standard background on read mapping, because the full text was behind an inaccessible paywall; the specific accelerator architecture, the exact mechanism for exploiting quasi-sequentiality, and the quantitative speedups are described in the paper and are not reproduced here. The durable lesson is that when a workload’s reference structure changes — from a line to a graph — the bottleneck can move somewhere unexpected, and the win comes from noticing where it went and exploiting whatever regularity the new structure still retains.

Background

Why the bottleneck keeps moving, and accelerators must chase it

It helps to see Harp as an instance of a pattern that recurs whenever a field changes its data representation: the accelerators built for the old representation optimize a cost that is no longer dominant. Read mapping spent years with a linear reference, and a generation of hardware learned to fly through the sequence-alignment kernel; the moment the reference became a graph, the time quietly relocated to graph processing, and all that specialized effort was aimed at the wrong place. The retrospective on deep-learning accelerators covered elsewhere on this site makes the same argument at the scale of whole systems, that the ceiling has moved from raw arithmetic to memory and data movement, so hardware designed to add more compute now optimizes what is no longer the constraint. The broad lesson is that a performance hotspot is not a fixed target but something that migrates as workloads and data structures evolve, and the enduring engineering skill is less about building a faster version of yesterday’s bottleneck than about profiling honestly to find where the cost has actually gone — and then exploiting whatever structure the new workload still offers, as Harp does with the near-linearity that survives even inside a graph.

If you remember only three things

1. Computational genomics has shifted from sequence-to-sequence mapping (aligning reads against a single linear reference genome) to sequence-to-graph mapping (aligning against a pangenome graph whose branches encode a population's genetic variation). The graph is far more accurate — it avoids the reference bias that makes reads carrying variants map poorly to a single reference — but aligning to a branching graph rather than a line is much more expensive: the aligner must navigate graph topology instead of sliding along a sequence. This graph processing becomes the dominant cost, causing an unnoticed shift of the performance hotspot away from the classic sequence-alignment kernel that prior software and hardware accelerators were built to speed up.
2. Harp is built on the observation that a genome graph is quasi-sequential: because genetic variation is sparse relative to the genome's length, the graph is made of long linear stretches punctuated by only occasional branches. Harp exploits this to accelerate sequence-to-graph mapping of long reads — handling the common linear stretches with a fast, sequence-like alignment path and invoking the expensive graph-processing logic only at the rare branch points where alternative paths genuinely matter. This concentrates its specialized effort on the graph-processing bottleneck that actually moved, rather than the linear-alignment kernel that prior accelerators already optimized, while long reads amortize the cheap path over their long common runs.
3. Its scope: the benefit depends on the graph being mostly linear (densely branching regions offer less to exploit); it is a specialized design for long-read sequence-to-graph mapping rather than a general graph engine; splitting linear from branch handling adds control complexity; long-read error rates make branch decisions hard; and it accelerates one pipeline stage, with downstream analyses separate. This explainer is written from the paper's brief abstract and standard read-mapping background, because the full text was unavailable — the specific accelerator architecture, the exact quasi-sequentiality mechanism, and the measured speedups are in the paper and are not reproduced here.

Check yourself

Check your understanding

1. Why did computational genomics move from a linear reference to a genome graph, and what did it cost?
2. What is the "unnoticed shift of performance hotspots" that the paper highlights?
3. What is Harp's key idea for accelerating sequence-to-graph mapping?
4. Which statement best reflects the scope and limitations of this work?

Sources

The paper is “Harp: Leveraging Quasi-Sequential Characteristics to Accelerate Sequence-to-Graph Mapping of Long Reads” by Yichi Zhang, Dibei Chen, Gang Zeng, Jianfeng Zhu, Zhaoshi Li, Longlong Chen, and colleagues, published at ASPLOS 2024, DOI 10.1145/3620666.3651331. The authors are at Tsinghua University.

This explainer is marked as a draft because the full text was not accessible: the paper is gold open access (Creative Commons) on the ACM Digital Library, but that page was protected by an anti-bot challenge that blocked automated retrieval, and no arXiv preprint, author-hosted copy, or repository version could be found; only a brief abstract was available. The account above is written from that abstract together with standard, well-established background on computational genomics — read mapping, the reference-bias problem of a single linear reference, pangenome graphs and how they encode variation as alternative paths, sequence-to-graph mapping, and long-read sequencing. The specific claims attributed to the paper — that read mapping has shifted from sequence-to-sequence to sequence-to-graph mapping, that sequence-to-graph mapping incurs high graph-processing overhead and causes an unnoticed shift of performance hotspots that challenges current software and hardware, and that Harp leverages the quasi-sequential characteristics of genome graphs to accelerate sequence-to-graph mapping of long reads — come from the abstract and title. The description of Harp’s approach (a fast linear path for the common stretches and graph processing only at branches) is a faithful reading of the quasi-sequential idea stated in the title, but the specific accelerator architecture, the exact mechanism for exploiting quasi-sequentiality, and the quantitative speedups are detailed in the full paper and are not reproduced or invented here; they should be confirmed against the paper itself.