DNA barcodes, which are short DNA strings, are regularly used as tags in pooled sequencing experiments to enable the identification of reads originating from the same sample. A crucial task in the subsequent analysis of pooled sequences is barcode calling, where one must identify the corresponding barcode for each read. This task is computationally challenging when the probability of synthesis and sequencing errors is high, like in photolithographic microarray synthesis. Here, we propose a simple, yet highly effective new barcode calling approach that uses a filtering technique based on precomputed k-mer lists. This approach has a slightly higher accuracy than the state-of-the-art approach, is more than 500 times faster than that, and thus allows barcode calling for one million barcodes and one billion reads per day on a server GPU.
Our software has been developed for Linux. The following steps are required to install quik on a Ubuntu 24.04 system:
-
Install software packages:
sudo apt install git cmake g++ libomp-dev nvidia-cuda-toolkit -
Checkout the project.
git clone https://gitlab.informatik.uni-halle.de/agkya/barcode-calling.git -
Compile the source files. Quik comes with a CMake Script that should work for various environments.
Before building the code, you might want to specify some CMake variables.
-
Quik assumes a barcode set in which all barcodes have the same length. You need to specify this length using the option
-DBARCODE_LENGTH. The following example uses barcodes of length 34. -
If you want to run quik on a specific GPU that is not available in your build system, you can specify the Compute Capability of your target GPU. For example, to build the code for the NVIDIA A100 GPU (which has Compute Capability 8.0), you need the option
-DCMAKE_CUDA_ARCHITECTURES=80.
cd barcode-calling mkdir build cd build cmake -DBARCODE_LENGTH=34 .. make -
The build directory should now contain three binaries:
quikis the main tool used to assign reads to barcodes.benchmark_barcode_callingis an auxiliary program to test and compare the efficiency and accuracy of quik's different filtering techniques on your system.simulate_errorsis an auxiliary program used to create our synthetic test data.
All binaries explain their usage when executed without arguments.
The quik command line tool is used in the following way:
quik --barcodes <FILE> --reads <FILE> [OPTIONS]
Required arguments:
-b, --barcodes <FILE> Barcode file in our custom BC format.
Such files have two line-separated fields per barcode.
- Field 1 begins with a '@' character and is followed
by a barcode identifier (similar to FASTQ).
- Field 2 is the raw sequence letters.
-r, --reads <FILE> Read file in FASTQ format.
Optional arguments:
-d, --distance <STRING> Distance measure specification
Possible values:
levenshtein
sequence-levenshtein
(default: sequence-levenshtein)
-c, --costs <FILE> Cost file used for the distance measure
The file contains lines of the form:
<x> <y> <c_xy>
where <x> and <y> are characters from {A,C,G,T,-}
and <c_xy> is a non-negative integer describing
the cost of aligning barcode base <x> to read
base <y>.
Missing base pairs imply zero alignment cost.
(default: 1 for each substitution, deletion, or mismatch)
-t, --threshold-distance Maximum allowed distance between read and barcode.
A read is only assigned to a barcode if its
distance is smaller or equal than this integer.
(default: 2.147.483.647 (INT32_MAX))
-m, --method <STRING> Barcode matching method
Possible values:
no-filter
Highest accuracy, extremly slow
4-mer-filter
High accuracy, much faster than no-filter
5-mer-filter
Decent accuracy, even faster than 4-mer-filter
6-mer-filter
Low accuracy, much faster than 5-mer-filter
7-mer-filter
Lowest accuracy, fastest method
7-4-mer-filter
First runs the fast 7-mer-filter to assign the
majority of the reads, then run the 4-mer-filter
to assign the remaining reads.
(default: 4-mer-filter)
-g, --gpu Apply all calculations on all GPUs visible to quik.
This is usually much faster than non-gpu mode.
-h, --help Show this help message and exit
-v, --verbose Print extra information to the standard error stream
Output:
quik writes one line per assigned read to the standard output.
Fields are tab-separated and have the following meaning:
read Sequence identifier of each read (at most once)
barcode1 Sequence identifier of closest barcode
barcode2 Sequence identifier of second closest barcode
distance1 Distance between read and barcode1
distance2 Distance between read and barcode2
Reads with distance1 > threshold-distance do not occur in the output.
Examples:
# Basic usage on GPU
quik --barcodes barcodes.bc --reads reads.fq --gpu
# Use 5-mer filtering and classical Levenshtein distance
quik -b barcodes.bc -r reads.fq -m 5-mer-filter -d levenshtein
Quik will find a barcode for each read, even if the read contains too many errors to find the respective barcode. Thus it is important that the user filters the assignments appropriately by providing a threshold distance. As it is not trivial to choose an appropriate threshold, we provide the script run_quik.sh for automatic assignment filtering. Please refer to citation (2) for more details.
First install Quik as described in the previous chapter.
Python is used for the rejection optimization. It requires the packages numpy, pandas and biopython. If you want to use the linear rejection function or bound approach, you also need gurobipy.
We recommend using conda for setting up an environment with the required packages using
the requirements.txt:
conda create --name <env> --file requirements.txt
conda activate <env>
# optionally:
pip install gurobipyThe run_quik.sh script runs Quik and performs the rejection optimization. You can provide the same arguments to run_quik.sh as to the quik binary (see previous chapter). Additional arguments are listed below.
bash run_quik.sh --barcodes <FILE> --reads <FILE> --output <FILE> [OPTIONS]
Required arguments:
-o, --output <FILE> Assignment file in TSV format.
Optional arguments:
-f, --rejection-function Rejection function type
Possible values:
simple
combined
linear
Requires Gurobi
bound
Requires Gurobi
none
Skips rejection optimization and only runs Quik
--r_S Parameter r_S for rejection optimization, 0<=r_S<=1
(default: 0.99)
-n, --number-of-strings Number of randomly generated strings for rejection optimization
(default: 1000000)
-h, --help Show this help message and exit
Output:
TSV file <output> with the accepted assignments (see previous chapter for the format).
Log file in the same directory containing information on the optimal
rejection function (if one is used) and the number of assigned reads.
tmp folder in the same directory containing further information and intermediate results.
Examples:
# Use GPU version of Quik and simple rejection function
bash run_quik.sh --barcodes barcodes.bc --reads reads.fq --gpu --rejection-function simple
# Use 5-mer filtering and classical Levenshtein distance and higher expected precision
bash run_quik.sh -b barcodes.bc -r reads.fq -m 5-mer-filter -d levenshtein --r_S 0.999
tmp/
|--calling/
| |--<key>_result.tsv # unfiltered calling results
| |--<key>_result.txt # calling log
| |--<key>_random_strings.fastq # randomly generated strings
| |--<key>_result_random.tsv # calling result of random strings
| |--<key>_result_random.tsv # calling log of random strings
|--optimization/
| |--<key>_log.txt # log for rejection optimization
| | (check for progress)
| |--matrices/
| | |--<key>_read_matrix.csv # distance1-distance2-matrix of
| | | read assignments
| | |--<key>_random_matrix.csv # distance1-distance2-matrix of
| | | string assignments
| | |--<key>_<rejection-function>_mask.csv # matrix with entry[d1][d2]=1
| | | for accepting reads with
| | | distance1=d1 and distance2=d2
| | | and entry[d1][d2]=0 otherwise
The key for each read file is the sha1sum of the read file. If you want to run the optimization multiple times, the results from previous runs are re-used which might save runtime.
The data directory contains sample files that can be used for testing and which we used to produce some of the results in our journal article.
The reads and ground truth assignments in this directory have been created from the auxiliary tool simulate_errors using prob=0.2.
This project is licensed under the GPL3. See the LICENSE file for details.
If you use this repository or the associated article, please cite:
- Riko Corwin Uphoff, Steffen Schüler, Ivo Grosse, Matthias Müller-Hannemann, Fast barcode calling based on k-mer distances, PNAS Nexus, 2026;, pgag001, https://doi.org/10.1093/pnasnexus/pgag001
- Steffen Schüler, Antonia Schmidt, and Matthias Müller-Hannemann. Quik 2.0: Efficient Large-Scale DNA Barcode Calling. In 26th International Conference on Algorithms for Bioinformatics (WABI 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 390, pp. 14:1-14:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026) https://doi.org/10.4230/LIPIcs.WABI.2026.14