SWOffinder: Efficient and versatile search of CRISPR off-targets with bulges by Smith-Waterman alignment

Abstract

CRISPR/Cas9 technology is revolutionizing the field of gene editing. While this technology enables the targeting of any gene, it may also target unplanned loci, termed off-target sites (OTS), which are a few mismatches, insertions, and deletions from the target. While existing methods for finding OTS up to a given mismatch threshold are efficient, other methods considering insertions and deletions are limited by long runtimes, incomplete OTS lists, and partial support of versatile thresholds. Here, we developed SWOffinder, an efficient method based on Smith-Waterman alignment to find all OTS up to some edit distance. We implemented an original trace-back approach to find OTS under versatile criteria, such as separate limits on the number of insertions, deletions, and mismatches. Compared to state-of-the-art methods, only SWOffinder finds all OTS in the genome in just a few minutes. SWOffinder enables accurate and efficient genomic search of OTS, which will lead to safer gene editing.

Keywords: Algorithms; Bioinformatics; Biological constraints; Techniques in genetics.

Graphical abstract

Figure 1

Off-target site alignment illustration An off-target site alignment with 1 DNA bulge, 1 RNA bulge, and 1 mismatch of a sgRNA sequence AUUGAGAUAGUGUGGGGAAG with NGG PAM and a genome window of the forward strand.

Figure 2

Overview of SWOffinder for searching off-target sites across a given genome First, in the SW-matrix calculation step, SWOffinder scans the genome for all end positions of sites with an edit distance that meets a user-specified threshold using a novel version of the Smith-Waterman alignment algorithm. Then, in the trace-back step, SWOffinder applies a novel recursive procedure on the subset of end positions obtained by the SW-matrix calculation step to filter sites, which do not meet the user-specified operation-specific thresholds, and find their alignment that meets those thresholds with minimum edit distance (Algorithm 1).

Figure 3

Off-target sites identification and runtime comparison of SWOffinder, CALITAS, and CRISPRitz (A) Comparison of the number of sites found by each method. We ran SWOffinder and CALITAS to find off-target sites up to edit distance 4, and CRISPRitz with up to 4 mismatches and 4 bugles (as it does not support an edit-distance threshold). (B) The overlap between sites that were identified by SWOffinder and sites that were found by CALITAS and CRISPRitz in a window. SWOffinder found all sites that were found by CALITAS and CRISPRitz. (C) Runtime comparison of SWOffinder, CALITAS, and CRISPRitz in searching off-target sites up to edit distance 4. CRISPRitz was run with up to 4 mismatches and 4 bulges (as it does not support an edit-distance threshold).

Figure 4

A comparison of the number of unique off-target sites found and the runtime between SWOffinder and CRISPRitz over various combinations of bulges and mismatches thresholds We did not compare to CALITAS in this benchmark as it does not support a search with a combination of separate thresholds. (A) A comparison of the unique off-target sites that were found. Note that the x-axis is on a logarithmic scale. (B) A comparison of the runtime. Note that the runtime of SWOffinder trace-back step was calculated by reducing the runtime of the SWOffinder SW-matrix calculation step from the total runtime.