MPI-RMapAlign3N

Read mapping and alignment for 3N-converted sequencing data, parallelized for HPC clusters.

---

About

RmapAlign3N maps next-generation sequencing reads to a reference genome or transcriptome. It targets reads produced by 3N nucleotide-conversion protocols — such as bisulfite sequencing — where one nucleobase is chemically exchanged for another depending on the presence or absence of a modification (e.g. methylation) in the original biomolecule. Because the converted read and the reference no longer match on a 4-letter alphabet, RmapAlign3N indexes and queries both in a reduced 3-letter space, using min-hash signatures over k-mers for candidate lookup and an optional edit-distance alignment step for refinement.

This repository is a fork that adds distributed-memory (MPI) execution to the upstream tool, so that a single mapping job can be spread across the nodes of a cluster instead of being confined to one shared-memory machine. MPI is integral here rather than an add-on: every build is MPI-enabled and compiled with mpicxx. The distributed layer lives in src/mpi_engine.h, src/mpi_querying.h and src/mpi_utils.h.

Highlights

• 3N-aware indexing — build once with -conv C T (or any other conversion pair) and query converted reads directly.
• Min-hash sketching — tunable k-mer length, sketch size and window stride to trade index size against sensitivity.
• Optional alignment — -align runs an edit-distance alignment (via edlib) over mapping candidates.
• Standard output formats — native tabular output, SAM, and BAM (through htslib).
• Paired-end support — reads paired across two files, or interleaved in a single file.
• Hybrid parallelism — MPI ranks across nodes, multi-threaded batch processing inside each rank.
• Selectable work distribution — static cyclic, static block, and block-into-dynamic re-distribution.

Quick start

# 1. build the tool (needs an MPI compiler wrapper, mpicxx)
make

# 2. build a reference database (C→T conversion, as used for BS-seq)
./rmapalign3n build myrefdb -conv C T reference.fa

# 3. align reads, distributed over 8 ranks
mpirun -n 8 ./rmapalign3n query myrefdb my_reads.fq -sam -align -out results.sam

Installation

Requirements

Compiler	any C++17-conforming compiler (g++, clang++)
MPI	an implementation providing mpicxx and mpirun — Open MPI, MPICH, Intel MPI, …
Build system	GNU make
Bundled dependencies	clipp, edlib, moodycamel queues — included as source, nothing to install
BAM output (optional)	htslib — bundled as a static library for Linux x86-64 only

Build variants

Run make in the directory containing the Makefile. Variants are selected through environment variables and combine freely:

Command	Result
make	release build → rmapalign3n
make debug	unoptimized build with symbols → rmapalign3n_debug
make profile	optimized build with symbols → rmapalign3n_prf
RMA_BAM=TRUE make	adds BAM output support (links htslib)
make clean	removes build directories and binaries

Build artifacts go into per-variant directories (build_release, build_debug, build_profile), so the variants do not clobber each other.

K-mer length

The width of the k-mer type caps the maximum k-mer length:

make MACROS="-DMC_KMER_TYPE=uint32_t"   # k up to 16 (default)
make MACROS="-DMC_KMER_TYPE=uint64_t"   # k up to 32, higher memory use

Important

A database can only be queried by a build of RmapAlign3N using the same data type settings it was built with. Databases are also not guaranteed to be portable across platforms that differ in endianness or integer width — in particular, do not mix 32-bit and 64-bit builds.

Usage

RmapAlign3N has four modes: build, query, info and help.

Building a reference database

Reference files must be in FASTA or FASTQ format. Pass them individually:

./rmapalign3n build myrefdb -conv C T reference1.fa reference2.fa reference3.fa

…or point at a directory, which is searched recursively:

./rmapalign3n build myrefdb -conv C T reference_folder/

-conv <original> <replacement> selects the nucleotide conversion. The default, -conv C T, is the C→T conversion of bisulfite sequencing. Sketching defaults are -kmerlen 16, -sketchlen 16, -winlen 64, -winstride 49; see docs/mode_build.txt for the full list.

Mapping reads

The examples below run as a single rank; see Parallel execution for spreading a job over several.

# single FASTQ file, native output, mapping only (no alignment)
./rmapalign3n query myrefdb my_reads.fq -out results.txt

# SAM output, mapping only (no alignment)
./rmapalign3n query myrefdb my_reads.fq -sam -out results.sam

# SAM output including alignments
./rmapalign3n query myrefdb my_reads.fq -sam -align -out results.sam

# a whole directory of FASTA/FASTQ files
./rmapalign3n query myrefdb my_folder/ -out results.txt

# paired-end reads in two files
./rmapalign3n query myrefdb reads_1.fq reads_2.fq -pairfiles -out results.txt

# paired-end reads interleaved in one file (a1,a2,b1,b2,…)
./rmapalign3n query myrefdb paired_reads.fq -pairseq -out results.txt

Frequently used knobs: -hitmin (candidate hit threshold, default 4), -cov-min (target coverage threshold, default 0.9), -align (post-mapping alignment), -threads and -batch-size (performance tuning). Running query with no input files starts an interactive session, which loads the database once and answers repeated queries against it.

Parallel execution

RmapAlign3N's query mode is an MPI program: launch it through your MPI runtime and each rank processes a share of the read batches. Mapping statistics, target coverage and (for the two-pass scheme) the batch index are reduced across ranks, and the root rank writes a single consistent output file.

mpirun -n 8 ./rmapalign3n query myrefdb my_reads.fq -sam -out results.sam

The build, info and help modes are serial and are invoked directly:

./rmapalign3n build myrefdb -conv C T reference.fa

Note

By default most MPI runtimes bind each process to a single core, which would confine all threads of that rank to that one core. Pass --bind-to none (Open MPI) or the equivalent option of your runtime, and set -threads to the number of cores available per rank.

Work-distribution strategies

How read batches are spread over the ranks is a compile-time choice, set by MPI_STRATEGY in src/mpi_querying.h:

Strategy	Behaviour
MPI_DEFAULT_STRATEGY	baseline distributed batch querying
MPI_STATIC_CYCLIC_DISTRIBUTION	batches dealt round-robin across ranks
MPI_STATIC_CYCLIC_NO_WRITE_DISTRIBUTION	as above, without output writing (benchmarking)
MPI_STATIC_BLOCK_INTO_DYNAMIC_DISTRIBUTION	default — static blocks in the first pass, then dynamic re-distribution of indexed batches in the second

Select a different one at build time:

make MACROS="-DMPI_STRATEGY=MPI_STATIC_CYCLIC_DISTRIBUTION"

Command-line reference

• build mode — build a database from reference sequences
• query mode — map reads against a database

The same documentation is available from the tool itself:

./rmapalign3n help build
./rmapalign3n help query
./rmapalign3n info myrefdb      # inspect an existing database

Repository layout

src/          core sources: modes, database, sketching, classification, I/O
  mpi_*.{h,cpp}   MPI engine, distributed querying and collective utilities
dep/          bundled third-party dependencies (clipp, edlib, queues, htslib)
docs/         command-line documentation for each mode
Makefile      build variants: release / debug / profile, optional BAM output

Credits

RmapAlign3N was written by André Müller (muellan@uni-mainz.de), Johannes Gutenberg University Mainz. This fork adds the MPI/distributed-memory execution layer.

Bundled third-party code retains its own licenses: clipp, edlib, moodycamel concurrent queues and htslib.

License

Released under the GNU General Public License v3.0. See LICENSE.