barcodesdb

Find DNA barcodes that occur nowhere in a sequence database you choose.

pip install barcodesdb

Given a collection of genomes, metagenomes or raw sequencing reads, barcodesdb records every k-mer that occurs anywhere in it. The k-mers left over — the ones that never appear — are barcode candidates: synthetic sequences that cannot be confused with real sequence from that collection.

That property is what makes them useful. A barcode that already exists somewhere in your organism's genome will show up in your sequencing reads whether or not your construct is there, and you cannot tell the two apart. A barcode absent from the whole database cannot produce that ambiguity.

The database is yours. Point it at the tree of life, at one bacterial genome, at your lab's assemblies, or at a metagenome from the environment you actually work in. "Absent" always means absent from what you indexed, and the tool is built so you can state exactly what that was — and re-check any candidate against it later.

---

Quick start

# 1. index everything under a directory (FASTA/FASTQ, plain or gzipped)
barcodesdb build -k 18 -i my_genomes/ -o mydb

# 2. see how much barcode space you have
barcodesdb stats -d mydb.bitarray

# 3. pull 1000 usable barcodes
barcodesdb dump -d mydb.bitarray \
    --gc-min 40 --gc-max 60 --max-homopolymer 3 --min-entropy 1.8 \
    -n 1000 > barcodes.txt

# 4. check any sequence against the database
barcodesdb query -d mydb.bitarray GCTCCCTGTAAGACCCCA

A real run on two Drosophila genomes (84 MB gzipped), start to finish:

$ barcodesdb build -k 12,13,14 -i genomes/ -o droso
[barcodesdb] found 2 input file(s), 83.9 MB
  k=12  16777216 k-mers  2 MiB  -> droso_k12.bitarray
  k=13  67108864 k-mers  8 MiB  -> droso_k13.bitarray
  k=14  268435456 k-mers  32 MiB  -> droso_k14.bitarray
encoding=gc  revcomp=on (in-line)  bitmap memory ~0.04 GiB
[done][all] k=12 present=16747733 absent(barcodes)=29483
[done][all] k=13 present=62504354 absent(barcodes)=4604510
[done][all] k=14 present=169026384 absent(barcodes)=99409072

$ barcodesdb dump -d droso_k14.bitarray --gc-min 40 --gc-max 60 --max-homopolymer 3 -n 5
AAGATTGTTGGCCT
AAGATTGTTGGGAG
AAGATTGTTGGGCT
AAGATTGTTGGGTC
AAGATTGTTGGGTG

$ barcodesdb query -d droso_k14.bitarray AAAAAAAAAAAAAA
sequence        verdict   index  matched_strand
AAAAAAAAAAAAAA  PRESENT   0      fwd

Note the shape of that result: at k=12 barely any 12-mer is unused, and by k=14 over a third of the space is free. Barcode space appears suddenly as k grows, and where that transition falls depends entirely on how much sequence you index. Two fly genomes leave room at k=14; hundreds of thousands of genomes do not (see Scale).

---

Install

pip install barcodesdb

The core is C++ and is compiled during install, so you need a C++17 compiler and zlib headers:

platform	command
Debian / Ubuntu	sudo apt install build-essential zlib1g-dev
RHEL / Fedora	sudo dnf install gcc-c++ zlib-devel
macOS	xcode-select --install
conda	conda install -c conda-forge cxx-compiler zlib

Then confirm the install actually works — this takes a few seconds and needs no data:

$ barcodesdb selftest
...
28/28 checks passed
This installation reproduces the reference encoding exactly.

Build knobs, if you need them:

variable	effect
CXX	compiler to use
BARCODESDB_MARCH=1	add -march=native (faster, but the binary will not run on an older CPU)
BARCODESDB_CXXFLAGS	replace the default -O3 -DNDEBUG
BARCODESDB_NO_ZLIB=1	build without gzip support

---

Commands

Every command carries worked examples in its own --help.

command	what it does
build	scan sequences, record which k-mers occur
stats	how many k-mers occur, how many are free
dump	list the absent k-mers, with filters
query	check whether given sequences occur
merge	combine bitmaps from parallel runs
scheduler	plan a multi-node build
info	version, detected cores, installed programs
selftest	verify the installation against an independent reference

build

barcodesdb build -k 16,17,18 -i genomes/ reads/ -o mydb

• FASTA and FASTQ, plain or gzipped, mixed freely in one run. FASTQ is parsed as FASTQ: quality lines are never treated as sequence, and a k-mer never spans two reads.
• Several k in one pass. -k 16,17,18 reads the collection once, not three times. All requested bitmaps are held at once, so budget 4^k bits per k (k=16 → 512 MB, k=17 → 2 GB, k=18 → 8 GB).
• Both strands by default. Observing a k-mer marks its reverse complement too, so a reported barcode is absent from both strands. --no-revcomp disables this for strand-specific work.
• All cores by default, or -t N. The default comes from this process's CPU affinity mask rather than the machine's core count, so it stays correct inside a Slurm allocation, cgroup or container.
• Resumable. --resume mydb.journal records finished work; rerun the same command after an interruption and it continues instead of starting over.

dump

Filters run inside the C++ scan, so narrowing the output is nearly free:

barcodesdb dump -d mydb.bitarray \
    --gc-min 40 --gc-max 60 \      # GC content window
    --max-homopolymer 3 \          # no AAAA / GGGG runs
    --min-entropy 1.8 \            # reject low-complexity sequence
    --not-contains GAATTC \        # avoid an EcoRI site (checked on both strands)
    -n 1000

--count reports how many barcodes pass the filters without emitting any.

query

The command for checking a candidate against a database — yours or someone else's:

barcodesdb query -d mydb.bitarray GCTCCCTGTAAGACCCCA
barcodesdb query -d mydb.bitarray -f candidates.txt

# barcodes from one database, checked against another
barcodesdb dump -d mydb.bitarray -n 100 | barcodesdb query -d other.bitarray -f -

A sequence is PRESENT if it occurs on either strand; the matched_strand column says which. --one-strand restricts the check to the forward strand.

---

Running at scale

Split one collection across nodes, then merge. Presence is a monotone OR, so merging partial runs is exact.

# plan balanced buckets (largest files placed first)
barcodesdb scheduler -i genomes/ reads/ --buckets 4000 -o sched.json

# each node runs one part
barcodesdb build -k 16,17,18 -j sched.json -o part1 --part-index 0 --part-count 2
barcodesdb build -k 16,17,18 -j sched.json -o part2 --part-index 1 --part-count 2

# combine
barcodesdb merge -o mydb_k18.bitarray part1_k18.bitarray part2_k18.bitarray

One caveat worth planning around: a gzipped file is one unit of work, because a gzip stream cannot be decompressed from an arbitrary offset. A single 20 Gbp FASTQ will occupy one thread for its whole duration no matter how many cores you have. If large read sets dominate your input, split them first on 4-line boundaries:

zcat big.fastq.gz | split -l 8000000 -d --filter='gzip > $FILE.fastq.gz' - shard.

Scale

The reference database behind the barcodesDB paper was built with this tool: 403,199 NCBI complete genome assemblies (302 GB) plus 12 SRA metagenome runs (215 Gbp of raw marine, soil and gut reads), indexed for k=14–18 in a single pass on 2 nodes × 144 cores in 11 h 38 min.

k	k-mer space	absent (barcodes)	% free
14	268,435,456	0	0%
15	1,073,741,824	0	0%
16	4,294,967,296	4,634	0.0001%
17	17,179,869,184	43,833,856	0.26%
18	68,719,476,736	5,845,777,189	8.5%

This is the saturation effect in full. Against a database that size there is no 14-mer or 15-mer left anywhere, and only 4,634 free 16-mers in the entire space — too few to build a library from. Practical barcode design against a tree-of-life-scale database starts at k=17, with k=18 giving real freedom.

Query cost, for reference: counting all 5.8 billion absent 18-mers in the 8 GB bitmap takes 80 s on 8 threads; a GC-filtered dump returns in milliseconds, because under the default encoding GC content maps to contiguous index ranges and the scan skips most of the bitmap outright.

---

How it works

For each k, a dense bitmap of 4^k bits — one bit per possible k-mer. Scanning sets the bit of every observed k-mer; bits still zero at the end are the barcodes.

Storing one bit rather than a counter is what makes tree-of-life scale feasible: at k=18 a 32-bit counter per k-mer would need ~275 GB, whereas the bitmap needs 8 GB and fits on an ordinary node.

Bitmaps are plain files with no header: ceil(4^k / 8) bytes, with k-mer i at bit i & 7 of byte i >> 3. Two index encodings are available (--encoding), and the same choice must be used for build, dump and query:

• gc (default) — ordered by GC count, then A<C<G<T within each GC block. Equal-GC k-mers occupy contiguous ranges, which is what makes GC-filtered dumps fast.
• lex — plain base-4: A=0, C=1, G=2, T=3.

Both are exact bijections onto [0, 4^k), and both are invertible — that is how dump turns an absent bit position back into a sequence.

---

Correctness

barcodesdb selftest runs 28 checks in a few seconds, comparing the compiled programs against a Python re-implementation of the encoding that shares no code with them:

• every one of the 4^k bits verified against the reference at k=4 and k=6, for both encodings, with reverse complement on and off
• one multi-k pass produces bit-identical results to separate single-k passes
• FASTQ quality lines are provably excluded; no k-mer spans two reads
• a sharded build merges back to exactly the unified result
• an interrupted build, resumed, equals an uninterrupted one bit-for-bit
• gzipped input equals plain, lowercase equals uppercase, wrapped FASTA equals unwrapped, windows containing N are skipped
• k-mers straddling the internal 5 MB streaming boundary are recorded on both strands
• every barcode from dump is confirmed absent, and query agrees

Because the encoding is purely combinatorial and parameterised only by k — no heuristics, no approximation, no data-dependent branches — correctness proven exhaustively at small k carries over to k=18.

---

What "absent" does and does not mean

Worth being precise about, because it is the entire basis of the method:

• Absence is relative to what you indexed. A barcode from a database of complete bacterial genomes may well occur in a draft assembly, a transcriptome, or an organism nobody has sequenced yet. If that matters for your application, index those too — that is what this tool is for.
• Absence is a snapshot. New sequences are deposited constantly. Re-run build on an updated download and re-check candidates with query.
• Exact matches only. A barcode absent from the database may still have near-matches in it, differing by one or two bases. If partial hybridisation matters for your assay, filter further downstream.
• Raw reads carry sequencing errors. Indexing FASTQ marks error-containing k-mers as present, which only ever removes candidate barcodes. That is the conservative direction, but it does make the barcode set smaller than the underlying biology strictly requires.

---

Citation

If you use this tool, please cite the barcodesDB paper (Patsakis et al.).

License

MIT — see LICENSE.