Metadata-Version: 2.4
Name: barcodesdb
Version: 1.0.0
Summary: Find DNA barcodes that are absent from any genome, metagenome or read collection you choose
Author: Georgakopoulos-Soares Lab
License: MIT License
        
        Copyright (c) 2026 Georgakopoulos-Soares-lab
        
        Permission is hereby granted, free of charge, to any person obtaining a copy
        of this software and associated documentation files (the "Software"), to deal
        in the Software without restriction, including without limitation the rights
        to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
        copies of the Software, and to permit persons to whom the Software is
        furnished to do so, subject to the following conditions:
        
        The above copyright notice and this permission notice shall be included in all
        copies or substantial portions of the Software.
        
        THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
        IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
        FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
        AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
        LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
        OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
        SOFTWARE.
        
Project-URL: Homepage, https://github.com/Georgakopoulos-Soares-lab/barcodes_extraction
Project-URL: Repository, https://github.com/Georgakopoulos-Soares-lab/barcodes_extraction
Project-URL: Issues, https://github.com/Georgakopoulos-Soares-lab/barcodes_extraction/issues
Keywords: bioinformatics,kmer,nullomer,barcode,dna,metagenomics,sequence-design,genomics
Classifier: Development Status :: 5 - Production/Stable
Classifier: Environment :: Console
Classifier: Intended Audience :: Science/Research
Classifier: License :: OSI Approved :: MIT License
Classifier: Operating System :: POSIX :: Linux
Classifier: Operating System :: MacOS :: MacOS X
Classifier: Programming Language :: C++
Classifier: Programming Language :: Python :: 3
Classifier: Programming Language :: Python :: 3.8
Classifier: Programming Language :: Python :: 3.9
Classifier: Programming Language :: Python :: 3.10
Classifier: Programming Language :: Python :: 3.11
Classifier: Programming Language :: Python :: 3.12
Classifier: Programming Language :: Python :: 3.13
Classifier: Topic :: Scientific/Engineering :: Bio-Informatics
Requires-Python: >=3.8
Description-Content-Type: text/markdown
License-File: LICENSE
Dynamic: license-file

# barcodesdb

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

```bash
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

```bash
# 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:

```console
$ 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](#scale)).

---

## Install

```bash
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:

```console
$ 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`

```bash
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:

```bash
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:

```bash
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.

```bash
# 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:

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

<a name="scale"></a>
## 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](LICENSE).
