Why CRISPR Off-Target Search Should Report Multiple Alignments Per Locus

How Sassy enumerates every reasonable alignment without sacrificing runtime

Jul 21, 2026

CRISPR off-target analysis depends on two things that are easy to take for granted: the sequence space being searched and the alignments a tool chooses to report. A workflow can miss relevant off-target candidates if it searches only the reference genome, or if it collapses multiple plausible alignments at a locus into a single preferred answer.

This post focuses on the second problem. Tim Dunn walks through recent work on Sassy that makes it possible to enumerate all reasonable alignments for short sequences such as CRISPR guides, while keeping runtime practical. In a companion post, Alison Meynert will look at the other side of the problem: rebuilding DivRef as a configurable resource for searching human variation and haplotype sequence.

Executive Summary

Sassy (authored by Rick Beeloo and Ragnar Groot Koerkamp) is an approximate string matching algorithm that uses bitpacking and SIMD instructions to quickly search for short patterns in long texts. The recent v0.2.5 release (authored by Fulcrum in collaboration with the original authors) eliminates the computational blind spot of returning only the single ‘best’ alignment at a particular locus when searching for CRISPR guide RNA off-target sites. For a typical Cas9 guide RNA, the enhanced algorithm identifies >9X more reasonable alignments in the human genome in under 30 seconds of total runtime, allowing researchers to evaluate the full spectrum of its potential off-target interactions.

Background

When CRISPR-Cas9 edits a genome, the guide RNA is designed to direct Cas9 to a single intended target. The guide is only 20 bases, and that’s short enough that it can partially match thousands of other sites across the human genome. Cas9 will cut at any of those if the spacer binds strongly enough. Unintended off-target cuts can disrupt genes, activate oncogenes, or introduce structural variants, any of which can be catastrophic in a therapeutic setting. Before a CRISPR-based therapy can advance toward the clinic, researchers must enumerate every close-enough partially matched genomic site and characterize what a cut there would mean. This post explains how we extended the fuzzy string matching tool sassy to not just report alignment locations within a given maximum edit distance from a guide sequence, but all reasonable alignments at each location.

Why Report Every Alignment?

When investigating potential CRISPR off-target sites, looking at only the “best” possible alignment at a given location doesn’t always show the full picture.

Consider two ways to align the same guide to one off-target genomic region. For readability, the figure shows the corresponding DNA sequence on the non-target strand, followed by the PAM. This allows the bases to be compared directly without also depicting complementation or U-to-T conversion.

Two sequence alignments of the same guide RNA (AGGTTACTACGATCGATGGA·N·GG, followed by a PAM) against the same off-target reference DNA (ATGGT··CTACGATCGATGGAAGG). Alignment 1 introduces a gap in the guide and two gaps in the DNA, producing 21 matches but 2 gap opens and 3 gap bases for a score of 6. Alignment 2 has no gap in the guide and one gap in the DNA, but incurs 2 mismatches; it scores 5. Alignment 1 wins on sequence similarity, but its two gap opens keep the mismatches at zero while Alignment 2's mismatches fall at specific positions that a biological scoring model might weigh differently—illustrating that the highest-scoring alignment is not necessarily the most biologically relevant one.

Alignment 1 receives a slightly better score when aligned using BWA’s default parameters, but that does not establish that it is the more biologically relevant configuration. Standard affine-gap and edit-distance scores measure sequence similarity; they are not models of guide binding or cleavage. A downstream model or domain expert may rank the same alignments differently based on the locations and types of edits, including whether the PAM remains intact.

A guide-specific scoring model could choose one configuration, but there is no single model whose assumptions are appropriate for every nuclease, guide, or experimental context. Reporting only one alignment therefore commits the analysis to one scoring model before downstream evaluation begins. Sassy instead separates candidate enumeration from biological ranking: it reports every reasonable alignment at the locus, allowing later models and experts to decide which configurations warrant further attention.

Rather than trying to claim that every reported alignment is equally likely to produce an off-target cut, the goal is to avoid eliminating plausible configurations before the appropriate biological scoring, filtering, or experimental validation can be applied.

The question of which alignments are worth reporting turns out to be surprisingly subtle, and working through it is where some interesting algorithmic ideas live. This post walks through the depth-first search at the core of sassy’s new search_all_alignments() API, developed collaboratively between Fulcrum Genomics, Ragnar Groot Koerkamp, and Rick Beeloo. The algorithm builds on sassy’s existing SIMD-accelerated search and adds a recursive backtracker that efficiently enumerates every reasonable alignment within edit distance k.

What We’re Building On

In this section, we’ll be using the language of approximate string matching algorithms. A “pattern” in this context is the sequence of characters for which you want to find partial or exact matches, e.g. a guide RNA sequence. The “text” is the sequence of characters in which you are searching, e.g. a reference genome.

Sassy already does the hard part: given a short DNA pattern (in our case a 20 bp guideRNA plus a 3 bp PAM) and a reference sequence, it uses SIMD bitwise operations to find every position where the pattern matches within edit distance k, fast. What it couldn’t do until now was report all reasonable alignments — the specific sequences of matches, mismatches, insertions, and deletions that connect the pattern to the reference sequence.

The new search_all_alignments() API adds a second pass to accomplish this:

Pass 1 is the same SIMD search sassy already uses. Pass 2 is where the new recursive depth-first search lives.

Pass 1: Alignment

Sassy’s search_all() algorithm faithfully implements Navarro’s definition of ‘Approximate String Matching’: it finds all positions in the text where an alignment of the pattern with cost ≤k ends, and returns those positions with a traceback/alignment for each. If you are unfamiliar with sequence alignment, the Needleman-Wunsch Wikipedia article on semi-global alignment provides a good introduction. Sassy uses a block-based dynamic programming (DP) algorithm based on Myers’ bit-parallel alignment algorithm to efficiently search the text. Below, an example fully-computed DP matrix shows alignment end positions where the pattern matches the text with edit distance k≤3 (highlighted in gray). For this figure (and all following matrices), we depict only the 7-base prefix of the pattern, since all remaining bases match and are uninformative.

A fully-computed dynamic-programming edit-distance matrix for Sassy's search_all() function. The vertical axis is the 7-base guide RNA prefix AGGT TAC (one base per row, rows 1–7); the horizontal axis is the reference DNA text ATGGTCAGACAGCTAAGCAAGTA (one base per column, columns 1–23), with a row 0 and column 0 of zeros representing the semi-global alignment initialization. Each cell holds the minimum edit distance to align the pattern prefix ending at that row against a text substring ending at that column. Cells in the final row (pattern base C, row 7) with values ≤ 3 are shaded gray; these mark the text positions where the full pattern aligns with at most 3 edits. Nine such positions are highlighted, occurring at text columns 7, 8, 9, 11, 16, 17, 18, 19, and 23, with values of 3, 3, 3, 3, 3, 3, 3, 3, and 3 respectively.

Pass 2: Backtracking

Backtracking occurs independently for each of the alignment end positions highlighted in the final row of the above DP matrix. In order to make backtracking simple, many sequence alignment implementations store the predecessor of each cell in the DP matrix when it is first reached during the forward pass. Once the full DP matrix has been computed, backtracking is as simple as following a trail of pointers to the top of the matrix:

A DP edit-distance matrix titled "Standard Backtracking," with the 7-base guide RNA prefix AGGT TAC on the vertical axis and the reference DNA text ATGGTC on the horizontal axis. Every cell contains both a numeric edit-distance value and a small colored arrow indicating how that cell was reached from its predecessor: a green diagonal arrow for a match, red diagonal for a substitution, blue upward for an insertion in the pattern, and gold leftward for a deletion from the text (key shown at right). A gray-shaded trail of cells marks the traceback path from the bottom-right end-position cell (value 3) back to the top of the matrix, following the stored predecessor arrows. The path proceeds mostly along the main diagonal, reflecting several matches, but includes a blue upward arrow at one step, indicating an insertion. The traceback terminates at row 0, giving the alignment start position in the text.

Since we would like to return all reasonable alignments, and not just one alignment that ends at this position, we cannot take this approach and must instead consider each possible path backwards from the alignment end position:

A DP edit-distance matrix titled "Naive DFS Backtracking," with the same layout as the standard backtracking figure: the 7-base guide RNA prefix AGGT TAC on the vertical axis and reference DNA text ATGGTC on the horizontal axis. Unlike standard backtracking, where each cell stores a single predecessor arrow, here every cell displays all three possible backward moves simultaneously—a green diagonal (match), red diagonal (substitution), blue upward (insertion), and gold leftward (deletion)—representing every path a DFS could follow. The bottom-right cell, value 3, is shaded gray as the alignment end position. From that cell, the DFS would recursively explore all arrow directions, pruning any path whose cumulative edit cost exceeds k, until it reaches row 0 for each surviving path.

At each step, the depth-first search (DFS) considers three backward moves: diagonal (Match or Sub, consuming one base in both sequences), horizontal (Del, consuming text only), and vertical (Ins, consuming pattern only). Any move that would push the cumulative edit cost above k is pruned immediately. Other subtrees are explored only if they meet several additional criteria, explained in more detail below.

What Does “All Reasonable Alignments” Mean?

Before writing a line of code, the team had to answer a difficult question: which alignments should actually be reported?

Naively enumerating every path through the edit-distance dynamic programming (DP) graph is combinatorially explosive. Aligning a 23-mer and allowing k=6 edits has on the order of millions of candidate paths, and reference regions dense with N bases make things even worse. You need a principled way to thin the set.

Our discussion converged on the idea that an alignment B is not reasonable if there exists another alignment A that covers the same region with a strict subset of the edits. In this case, alignment A should be kept and alignment B should be discarded.

In general, a “reasonable” alignment with edit distance ≤k must meet the following additional criteria:

(A) it doesn’t start or end with deletions, i.e. horizontal edges (deletions don’t consume pattern bases, so the alignment should be considered complete instead of marking additional text bases as deleted when they could just not be part of the alignment)
(B) for any two points in the alignment, if the intervening positions match exactly in the text and pattern, the alignment uses those matches rather than routing around it with indels
(C) it doesn’t contain adjacent insertions and deletions (in this case, substitutions should be preferred)

For example, an alignment with CIGAR string 4=1I2=1D4= is not reasonable if another alignment covering the same positions has CIGAR string 9=, and so only 9= is reported. But 4=1X6= and 4=1I2=1D4= are incomparable (neither alignment contains a set of edits that is a subset of the other), so both get reported. Below, we explain how these criteria are enforced in greater detail:

Rule 1 — No leading or trailing deletions (Criterion A)

In general, a deletion represents a text base that is not present in the pattern. A deletion at the very edge of the aligned region is meaningless, since all text bases outside the aligned region are already not present in the pattern. For any alignment with cost c where c<k, the alignment could be left- and right-padded with up to k-c deletions. These additional alignments are not useful, and should be discarded.

Rule 2 — Don’t leave a diagonal you can extend exactly to the end (Criterion B)

Before taking an indel movement away from the current diagonal, the algorithm checks whether the remaining pattern prefix matches the corresponding text exactly:

If the prefix is all exact matches, any indel taken here produces an unreasonable alignment, since there exists an alignment (the path with all matches) with no additional edits. This rule covers criterion B from the left-hand side of the alignment.

Rule 3 — Don’t enter a diagonal reachable by exact matches (Criterion B)

The symmetric counterpart: when entering a new diagonal via an indel, the algorithm checks whether the pattern rows between the new position and the last time it visited this diagonal are all exact matches:

If these slices match exactly, then there exists an alignment with fewer edits (that never left this diagonal during this section of the alignment) and the current alignment is unreasonable and can be discarded. The key data structure here is last_row_in_diagonal, a vector that tracks, for each diagonal in the DP matrix, the most recent row in this diagonal visited during the current DFS. This logic enables enforcing criterion B from the right-hand side of each indel, ensuring that no unnecessary indels are ever included.

The following example illustrates this criterion filtering out path P2 as it extends leftwards into the dark gray cell (1,1). Because the last time this path visited the main diagonal was cell (4,4), text[1..4] = TGG is compared to pattern[1..4] = TGG and this path is pruned because alternate path P1 exists with fewer edits.

A DP matrix with the same layout as before—guide RNA prefix AT GGTA C on the vertical axis, reference DNA ATGGTC on the horizontal axis—with faded background arrows showing all possible moves. Two backtracking paths are overlaid and highlighted in gray. P1 (green, labeled "Reasonable") travels along the main diagonal through cells (1,1), (2,2), (3,3), (4,4), continuing downward with matches and a small number of edits. P2 (red, labeled "Not Reasonable") takes a divergent route involving substitutions and insertions, eventually making a leftward deletion move to reach cell (1,1), which is shaded dark gray to mark where pruning occurs. P2 is pruned at that cell because the last time it visited the main diagonal was (4,4), and the intervening slice—pattern rows 1–4 (TGG) and text columns 1–4 (TGG)—match exactly, meaning P1 covers the same region with fewer edits and P2's detour is unnecessary.

Rule 4 — No insertion-deletion mixing without a match anchor (Criterion C)

In an alignment, adjacent insertions and deletions can always be replaced by substitutions. For every alignment that includes a mismatch (X), reporting a pair of adjacent indels (ID or DI) as well is not useful. This rule avoids reporting all such alignments, but still allows D=I and I=D when == does not work.

Summary

The result of applying these four rules during a depth-first backtracking search is an iterator that delivers every structurally distinct alignment within cost k, without reporting unreasonable alignments, and without materializing the exponential set of possible alignments first.

A DP matrix titled "Final DFS Backtracking," with guide RNA prefix AGGT TAC on the vertical axis and reference DNA ATGGTC on the horizontal axis, with faded background arrows as in previous figures. Seven distinct backtracking paths are overlaid, all terminating at the same gray-highlighted end-position cell in the bottom right and fanning out toward the upper left as they trace different routes to row 0. A gray band highlights the diagonal region the paths traverse. Each path is a different color and labeled with a compact edit string in the key: P1 (blue, 1=1X1=1X1=1I1=), P2 (teal, 1X2=1I1=1I1=), P3 (pink, 1=1D2=1I1=1I1=), P4 (cyan, 1I2=1I1=1I1=), P5 (green, 1X3=2I1=), P6 (orange, 1=1D3=2I1=), and P7 (purple, 1I3=2I1=). P6 and P1 correspond to Alignment 1 and Alignment 2 respectively from the opening figure of the post.

The above figure visualizes all seven search_all_alignments() results reported on this example, and you can see that both Alignment #1 and Alignment #2 from the very first figure in this blog post are depicted here as paths P6 and P1, respectively.

Optimization: Filtering N-dense Regions

Reference sequences frequently contain hard-masked regions, most often due to assembly gaps caused by repetitive regions such as centromeres or telomeres. These are present in the FASTA as long stretches of N bases (e.g. NNNNN…) which result in a large number of uninformative alignments, since all bases A/C/G/T are considered a Match with N. To enable filtering these alignments, search_all_alignments() provides the argument max_n_frac, which defaults to 0.2. Any alignments where more than 20% of the aligned reference bases are Ns are discarded.

In many such cases, we can avoid computing the recursive DFS entirely using known properties of the alignment and text. All alignments of a pattern to the text with edit distance ≤k must have length of at least len(pattern)-k and at most len(pattern)+k. The alignment’s end_pos in the text has been computed by search_all(), and is known. Thus, all alignments will cover the region text[end_pos - (len(pattern)-k).. end_pos], though some may extend further leftwards. If the number of Ns contained in this text substring divided by the maximum possible alignment length (len(pattern)+k) exceeds max_n_frac, no alignments from this position will be valid and the recursive DFS can be skipped entirely. Since the pattern length is 23 and k is usually less than or equal to 6, as long as max_n_frac is below 58%, all alignments fully within hard-masked regions will be skipped.

Conclusion

Aligning the guideRNA sequence GAGTCCGAGCAGAAGAAGAANGG (from Zhang 2013) to a GRCh38 reference FASTA with k=6 results in the following high-level metrics, computed on an Apple M3 Max:

In under 30 seconds, we are able to find all reasonable alignments of the guide RNA to the human reference genome. The new N-region pre-filtering and recursive backtracking steps add less than 10 seconds of runtime, yet they are able to discard over 99% of hits as uninformative and increase the total number of useful alignments by over 9x! This is important because any alignments which are not reported are unable to be filtered and evaluated by a human expert. Removing this computational blind spot is cheap and fast, potentially saving significant time and money on downstream validation efforts.

Sassy is currently available on GitHub. The alignment iterator work is complete and has been incorporated into the recent sassy release v0.2.5.This release includes both a Rust implementation and Python bindings for Searcher.search_all_alignments().

Tim Dunn is a Staff Bioinformatics Scientist at Fulcrum Genomics, where he builds bioinformatics tools and pipelines for the genomics community. He earned his PhD in Computer Science from the University of Michigan and is the author of vcfdist, a method for accurately benchmarking small variant calls. You can find him on LinkedIn and GitHub, where he's still trying to convince two variant callers they made the same call.

Fulcrum Genomics is a bioinformatics consulting firm built by scientists at the forefront of large-scale genomic research, with deep expertise in sequencing technology, pipeline engineering, and genomic data analysis for biotech, pharma, and academia. Engage us through project-based work, fractional R&D, or hourly consulting. Contact us to discuss your project.

A guest post by

Tim Dunn

Staff Bioinformatics Engineer at Fulcrum Genomics