BWR-finder

BWR-finder is a de novo interspersed-repeat detection tool that searches a genome directly through its Burrows-Wheeler transform (BWT). Its primary workflow constructs a run-length encoded BWT (RLBWT) with grlBWT. An in-memory SDSL compressed suffix array (CSA) mode is also available.

This repository contains the research implementation used for manuscript preparation. The command-line interface and output format should be considered research-software interfaces and may change between versions.

Contents

• Installation
• Quick start
• Input modes
• Output
• Reproducibility and known limitations
• Citation
• License

Installation

Requirements

• Git
• Docker with Docker Compose v2

The provided image uses Ubuntu 22.04 and installs CMake, a C++17 compiler, OpenMP, SDSL-lite, libdivsufsort, and the other build dependencies. The Compose configuration targets linux/amd64; on ARM-based hosts, Docker may use architecture emulation.

Clone the repository together with all Git submodules:

git clone --recursive https://github.com/hmdlab/BWR-finder.git
cd BWR-finder

If the repository was cloned without --recursive, initialize the submodules before building:

git submodule update --init --recursive

Build the Docker image:

docker compose build

Start an interactive development container:

docker compose run --rm dev bash

Inside the container, configure and build BWR-finder:

cmake -S . -B build -DCMAKE_BUILD_TYPE=Release
cmake --build build --parallel

The executable is created at build/BWR-finder.

Quick start

For a reproducible single-threaded run that constructs an RLBWT with grlBWT:

mkdir -p work
OMP_NUM_THREADS=1 ./build/BWR-finder \
  --input genome.fa \
  --build-rlbwt

By default, this creates a preprocessed sequence next to the input, writes the RLBWT to work/processed.rl_bwt, and writes detected repeats next to the input as genome_repeat.fa.

Input modes

FASTA to RLBWT, then detect repeats

This is the recommended workflow. Use --build-rlbwt to preprocess the FASTA, construct an RLBWT with grlBWT, and run repeat detection:

OMP_NUM_THREADS=1 ./build/BWR-finder \
  --input genome.fa \
  --build-rlbwt \
  -k 7

The FASTA records are uppercased and concatenated. Record boundaries and runs of non-ACGT characters are represented by X.

Existing RLBWT

Run repeat detection from a previously constructed RLBWT:

OMP_NUM_THREADS=1 ./build/BWR-finder \
  --bwt-file genome.rl_bwt

FASTA to in-memory CSA

For small inputs or development checks, omitting --build-rlbwt constructs an in-memory SDSL CSA:

OMP_NUM_THREADS=1 ./build/BWR-finder \
  --input genome.fa

Output

The output is a FASTA-like text file. Each record contains a generated record identifier, consensus length, seed frequency, seed sequence, and consensus:

>repeat0 , length = 50 , seed freq = 10 , seed = GATATTT
CAGTCTTGTCCGACGGGGCTACTTTCTATAACGAACGTGCAGATATTTCT

Multiple records may contain the same consensus when it is reached from different seeds. Record identifiers describe output order and should not be treated as stable biological identifiers.

Reproducibility and known limitations

• Set OMP_NUM_THREADS explicitly because the thread count can affect the number and order of reported records. The --threads option separately controls RLBWT construction.
• FASTA preprocessing removes headers, joins records, and replaces non-ACGT runs with X.

Citation

If you use BWR-finder in published work, please cite the accompanying BWR-finder bioRxiv preprint. The full citation and DOI should be added here when the preprint record becomes available. For exact computational reproducibility, also report the Git commit used in the analysis.

License

BWR-finder is distributed under the GNU General Public License v3.0. Third-party dependencies and the grlBWT submodule are distributed under their respective licenses.