A DNA sequence read mapper based on mash distances and the wavefront alignment algorithm.
wfmash is a fork of MashMap that implements base-level alignment using WFA, via the wflign tiled wavefront global alignment algorithm.
It completes MashMap with a high-performance alignment module capable of computing base-level alignments for very large sequences.
Each query sequence is broken into non-overlapping pieces defined by -s[N], --segment-length=[N].
These segments are then mapped using MashMap's sliding minhash mapping algorithm and subsequent filtering steps.
To reduce memory, a temporary file is used to store initial mappings.
Each mapping location is then used as a target for alignment using WFA.
The resulting alignments always contain extended CIGARs in the cg:Z:* tag.
Approximate mapping (equivalent to MashMap2) can be obtained with -m, --approx-map.
Sketching, mapping, and alignment are all run in parallel using a configurable number of threads.
The number of threads must be set manually, using -t, and defaults to 1.
wfmash has been developed to accelerate the alignment step in variation graph induction (the first step in the seqwish / smoothxg pipeline).
Suitable default settings are provided for this purpose.
Seven parameters shape the length, number, identity, and alignment divergence of the resulting mappings.
The first three affect the structure of the mashmap2 mappings:
-s[N], --segment-length=[N]is the length of the mapped and aligned segment (when-Nis not set)-N, --no-splitavoids splitting queries into segments, and instead maps them in their full length-p[%], --map-pct-id=[%]is the percentage identity minimum in the mapping step-n[N], --n-secondary=[N]is the maximum number of mappings (and alignments) to report for each segment abovesegment-length(the number of mappings for sequences shorter than the segment length is defined by-S[N], --n-short-secondary=[N], and defaults to 1)
Together, these settings allow us to precisely define an alignment space to consider.
During all-to-all mapping, -X can additionally help us by removing self mappings from the reported set, and -Y extends this capability to prevent mapping between sequences with the same name prefix.
Map a set of query sequences against a reference genome:
wfmash reference.fa query.fa >aln.pafSetting a longer segment length to reduce spurious alignment:
wfmash -s 50000 reference.fa query.fa >aln.pafSelf-mapping of sequences:
wfmash -X query.fa query.fa >aln.pafwfmash provides a progress log that estimates time to completion.
This depends on determining the total query sequence length.
To prevent lags when starting a mapping process, users should apply samtools index to index query and target FASTA sequences.
The .fai indexes are then used to quickly compute the sum of query lengths.
The build is orchestrated with cmake:
cmake -H. -Bbuild && cmake --build build -- -j 16
The wfmash binary will be in build/bin.
To clean up, just remove the build directory.
-
Santiago Marco-Sola, Juan Carlos Moure, Miquel Moreto, and Antonio Espinosa "Fast gap-affine pairwise alignment using the wavefront algorithm" Bioinformatics, 2020.
-
Chirag Jain, Sergey Koren, Alexander Dilthey, Adam M. Phillippy, and Srinivas Aluru. "A Fast Adaptive Algorithm for Computing Whole-Genome Homology Maps". Bioinformatics (ECCB issue), 2018.
-
Chirag Jain, Alexander Dilthey, Sergey Koren, Srinivas Aluru, and Adam M. Phillippy. "A fast approximate algorithm for mapping long reads to large reference databases." In International Conference on Research in Computational Molecular Biology, Springer, Cham, 2017.
-
Martin Šošić and Mile Šikić "Edlib: a C/C ++ library for fast, exact sequence alignment using edit distance", Bioinformatics, 2017.