FMLRC2

This repo contains the source code for FMLRC v2, based on the same methodology used by the original FMLRC. In benchmarks, the results between FMLRC v1 and v2 are nearly identical, but tests have shown that v2 uses approximately 50% of the run and CPU time compared to v1.

Installation

All installation options assume you have installed Rust along with the cargo crate manager for Rust.

From Cargo

cargo install fmlrc
fmlrc2 -h
fmlrc2-convert -h

From GitHub

git clone https://github.com/HudsonAlpha/fmlrc2.git
cd fmlrc2
#testing optional, some tests will fail if ropebwt2 is not installed or cannot be found on PATH
cargo test --release
cargo build --release
./target/release/fmlrc2 -h
./target/release/fmlrc2-convert -h

Usage

BWT Building

msbwt2 Construction Approach

For most users, it is recommended to use the msbwt2 crate to build the BWT. This approach is generally simpler (requiring only one command) and more flexible (accepting both FASTQ and FASTA files at once). While it is generally competitive with the ropebwt2 construction approach (see below) for memory and CPU usage, it is not parallelized and typically runs slower by wall-clock time.

ropebwt2 Construction Approach

If you are familiar with more complicated shell commands, then ropebwt2 can also be used to build the BWT.
For most short-read datasets, this approach is faster than msbwt2-build but also more complicated (multiple piped commands) and less flexible (fixed to FASTQ in the below example). Given one or more FASTQ files of accurate reads (reads.fq.gz with extras labeled as [reads2.fq.gz ...]), you can use the following command from this crate to create a BWT at comp_msbwt.npy. Note that this command requires the ropebwt2 executable to be installed:

gunzip -c reads.fq.gz [reads2.fq.gz ...] | \
    awk 'NR % 4 == 2' | \
    sort | \
    tr NT TN | \
    ropebwt2 -LR | \
    tr NT TN | \
    fmlrc2-convert comp_msbwt.npy

Note: If you are only using the BWT for correction, then the sort can be removed from the above command. This will reduce construction time significantly, but loses the read recovery property of the BWT.

Correction

Assuming the accurate-read BWT is built (comp_msbwt.npy) and uncorrected reads are available (fasta/fastq, gzip optional, uncorrected.fq.gz), invoking FMLRC v2 is fairly simple:

fmlrc2 [OPTIONS] <comp_msbwt.npy> <uncorrected.fq.gz> <corrected_reads.fa>

Currently, only uncompressed FASTA is supported for output reads.

Options to consider

-h - see full list of options and exit
-k, --K - sets the k-mer sizes to use, default is [21, 59]; all values are sorted from lowest to highest prior to correction
-t, --threads - number of correction threads to use (default: 1)
-C, --cache_size - the length of sequences to pre-compute (i.e. C-mers); will reduce CPU-time of queries by O(C) but increases cache memory usage by O(6^C); default of 8 uses ~25MB; if memory is not an issue, consider using 10 with ~1GB cache footprint (or larger if memory really isn't an issue)

FMLRC v2 core differences

Implemented in Rust instead of C++ - this comes will all the benefits of Rust including cargo, such as easy installation of the binary and supporting structs/functions along with documentation
Unlimited k/K parameters - FMLRC v1 allowed 1 or 2 sizes for k only; FMLRC v2 can have the option set as many times as desired at increased CPU time (for example, a 3-pass correction with k=[21, 59, 79])
Call caching - FMLRC v2 pre-computes all k-mers of a given size. This reduces the run-time significantly by cutting reducing calls to the FM-index.
Input handling - thanks to needletail, the uncorrected reads can be in FASTA/FASTQ and may or may not be gzip compressed.
Unit testing - FMLRC v2 has unit testing through the standard Rust testing framework (i.e. cargo test)

Benchmarks

Thus far, all benchmarks have focused on a relatively small E. coli dataset for verifying correctness. The files for this dataset can be found in the original fmlrc example. The exact same BWT and uncorrected long read files were used for both fmlrc v1 and fmlrc v2. ELECTOR was used to evaluate the results. All fmlrc executions were run on a Macbook Pro with Apple M1 Pro processor (8 threads/processes used) with 16 GB of RAM. Run times were gathered using Mac OSX time. All parameters were set to defaults except for -C 10 in FMLRC v2.

The following table summarizes the results. The actual corrections are nearly identical (there are slight differences not reflected in summary metrics). However, FMLRC v2 runs in less than half the time from both real time and CPU time perspectives. While not explicitly measured, FMLRC v2 does use ~1GB of extra memory due to the 10-mer cache (-C 10).

Metric	FMLRC v1.0.0	FMLRC2 v0.1.6 (`-C 10`)	FMLRC2 v0.1.7 (`-C 10`)
Recall	0.9830	0.9830	0.9830
Precision	0.9821	0.9821	0.9821
Real time	3m38.067s	1m24.219s	1m14.720s
CPU time	27m23.652s	8m49.680s	8m15.823s

FAQ

How do I set multiple, custom k-mer sizes?

K-mer sizes are set via the -k/-K parameter. Since the parameter allows for multiple values, the CLI may need the end-of-list delimiter ("--") specified as well. The following is an example of how you would add a third filtering step with k=79 to the defaults:

fmlrc2 -k 21 59 79 -- <comp_msbwt.npy> <uncorrected.fq.gz> <corrected_reads.fa>

Reference

FMLRC2 reference: Mak, Q. C., Wick, R. R., Holt, J. M., & Wang, J. R. (2023). Polishing de novo nanopore assemblies of bacteria and eukaryotes with FMLRC2. Molecular Biology and Evolution, 40(3), msad048.

Original FMLRC reference: Wang, Jeremy R. and Holt, James and McMillan, Leonard and Jones, Corbin D. FMLRC: Hybrid long read error correction using an FM-index. BMC Bioinformatics, 2018. 19 (1) 50.

License

Licensed under either of

Apache License, Version 2.0 (LICENSE-APACHE or http://www.apache.org/licenses/LICENSE-2.0)
MIT license (LICENSE-MIT or http://opensource.org/licenses/MIT)

at your option.

Contribution

Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in the work by you, as defined in the Apache-2.0 license, shall be dual licensed as above, without any additional terms or conditions.