Shred

Basic Usage

shred.sh in=<file> out=<file> length=<int>
shred.sh in=<assembly.fa> out=<pieces.fa> k=<int>

Shreds input sequences into shorter subsequences of specified length, with optional overlap and various length distribution modes.

With k= set to a positive value, SHRED instead cuts each sequence at de Bruijn branch points (see Algorithm Details). Branch mode keeps every input base and cannot be combined with length, overlap, or filtering options.

Parameters

Parameters control input/output files, shred length specifications, distribution modes, de Bruijn branch mode, and naming conventions.

File Parameters

in=<file>: Input sequences. Accepts FASTA or FASTQ format, compressed or uncompressed. Required parameter.
out=<file>: Destination of output shreds. Will be written in the same format as input (FASTA or FASTQ). Required parameter.

Processing Parameters

k=0: Positive values select de Bruijn branch shredding instead of length shredding. Canonical k-mers are counted over the input, then each sequence is cut after every k-mer with multiple present predecessors or successors. Repeat count alone does not cause a cut. Every input base is kept, including Ns and short tails, so adjacent branches can produce 1-base pieces. Branch mode reads the input twice, so it requires a regular FASTA or FASTQ file (not stdin and not a comma-separated list). It is incompatible with length, minlen, maxlen, median, variance, the mode flags (linear, exp, log), equal=t, nonzero overlap or increment, and maxns filtering; combining them throws an error. Default is 0, which keeps the length-based behavior.
hashonly=t: For branch mode with k above 31, stores two hashes per k-mer instead of its full packed sequence. Each allocated table slot then uses 16 bytes of hash key plus a 4-byte count, independent of k. Set to f to store full packed keys. Small-k tables (k 31 and below) and length-based shredding are not affected. Default is t.
length=500: Desired length of shreds if a uniform length is desired. Default value is 500 bases. This is the target length for each shred when using uniform length mode.
minlen=-1: Shortest allowed shred. The last shred of each input sequence may be shorter than desired length if this is not set. When set to -1 (default), no minimum length is enforced. If set to a positive value, shreds shorter than this will be discarded.
maxlen=-1: Longest shred length. If minlength and maxlength are both set, shreds will use a random flat length distribution. When set to -1 (default), no maximum length is enforced beyond the sequence length.
median=-1: Median length for random length distribution. Setting median and variance will override minlen and maxlen settings. Used in conjunction with variance to define a random distribution around the median value.
variance=-1: Variance for random length distribution. Used with median parameter to create a random length distribution. The actual range will be median ± variance.
linear: Use linear distribution for random lengths. When maxlen is greater than minlen, the distribution can be linear, exp, or log (pick one as a flag). Linear distribution gives equal probability to all lengths in the range.
exp: Use exponential distribution for random lengths. Alternative to linear and log distributions. Exponential distribution favors shorter lengths with decreasing probability for longer lengths.
log: Use log-uniform distribution for random lengths. Alternative to linear and exp distributions. Log-uniform distribution samples from a continuous log-uniform distribution between minlen and maxlen.
overlap=0: Amount of overlap between successive shreds in bases. Default is 0 (no overlap). Positive values create overlapping shreds where increment = length - overlap. Used in the increment calculation for processUnevenly() and processEvenly() methods.
reads=-1: Maximum number of input sequences to process. If set to a non-negative value, processing will stop after this many input sequences. Default of -1 processes all input sequences.
equal=f: Shred each sequence into subsequences of equal size of at most 'length', instead of a fixed size. When enabled, sequences are divided into equal-sized chunks rather than using fixed-length shreds with potentially shorter remainder.
qfake=30: Quality score to assign to all bases when output format is FASTQ. Default is 30 (corresponding to 99.9% accuracy). Only used when input is FASTA but output needs to be FASTQ format.
filetid=f: Parse taxonomic ID from filename and incorporate into shred names. When enabled, extracts TID from the input filename (e.g., "sample_tid_12345.fasta") and includes it in output sequence names.
headertid=f: Parse taxonomic ID from sequence headers and incorporate into shred names. When enabled, extracts TID from individual sequence headers and includes it in the corresponding shred names.
prefix=null: Prefix to use for shred names instead of original sequence names. When specified, shred names will start with this prefix followed by coordinate information.

Examples

Basic Uniform Shredding

shred.sh in=genome.fasta out=shreds.fasta length=1000

Shreds input sequences into 1000-base fragments with no overlap.

Overlapping Shreds

shred.sh in=contigs.fasta out=overlapping_shreds.fasta length=500 overlap=100

Creates 500-base shreds with 100 bases of overlap between consecutive shreds (400-base increment).

Random Length Distribution

shred.sh in=sequences.fasta out=random_shreds.fasta minlen=300 maxlen=800 linear

Generates shreds with random lengths between 300-800 bases using linear distribution.

Even-Length Shredding

shred.sh in=assembly.fasta out=even_shreds.fasta length=1000 equal=t

Divides each sequence into equal-sized chunks of at most 1000 bases, ensuring uniform coverage.

Quality Score Assignment

shred.sh in=sequences.fasta out=shreds.fastq length=500 qfake=25

Converts FASTA input to FASTQ output with quality scores of 25 for all bases in the shreds.

Median-Variance Distribution

shred.sh in=genome.fasta out=variable_shreds.fasta median=600 variance=200 exp

Creates shreds with exponential length distribution centered around 600 bases with 200-base variance (range: 400-800).

De Bruijn Branch Shredding

shred.sh in=assembly.fasta out=pieces.fasta k=31

Cuts each contig in assembly.fasta after every 31-mer that has more than one present predecessor or successor. Every input base appears in exactly one output piece, and repeat copies are retained.

Branch Shredding With Long k and Full Keys

shred.sh in=assembly.fasta out=pieces.fasta k=127 hashonly=f

Uses 127-mers with full packed keys instead of dual hashes. For k above 31 the Java source requires the packed k-mer layout and reports an error otherwise (see Algorithm Details).

Algorithm Details

Shredding Modes

SHRED implements three length-based shredding strategies, plus a de Bruijn branch mode selected with k:

1. Uniform Length Shredding (Default)

Processes sequences using a fixed increment calculated as increment = length - overlap. Each shred has exactly the specified length (except potentially the last shred of each sequence). Uses the processUnevenly() method with simple arithmetic progression through sequence coordinates.

2. Even-Length Distribution

When equal=true, sequences are divided into approximately equal-sized chunks. The processEvenly() method calculates chunks using chunks = ceil((bases.length - overlap) * incMult) and increment using inc2 = bases.length / chunks. Each chunk position is calculated as a = floor(inc2 * chunk) and b = overlap + floor(inc2 * (chunk + 1)).

3. Random Length Distribution

When minlen and maxlen are both specified, shreds are generated with random lengths. Three distribution modes are available:

Linear: Uniform probability across the length range
Exponential: Decreasing probability for longer lengths using Tools.exponential() with invlambda parameter 1/λ = 1/√(minlen × maxlen), with retry mechanism (up to 20 attempts) for out-of-bounds values
Log-uniform: Uses logUniformLength() method sampling from continuous log-uniform distribution calculated as logValue = logMin + u * (logMax - logMin) where u is uniform random [0,1], then converts back via Math.round(Math.exp(logValue))

4. De Bruijn Branch Shredding (k above 0)

Selected with k= set to a positive value. Implemented in ShredKmer, which makes two passes over the input file. Length, overlap, distribution, and filtering options are not used in this mode.

Counting pass: Canonical k-mers (reverse-complement aware) are counted over all input sequences. Prefiltering, minimum-probability filtering, quality trimming, and minimum average quality are disabled. For k of 31 and below, counts are stored in the small-k native table (KmerTableSet). For k above 31, counts are stored in KmerTableSetU, which requires exact packed k-mers and reports an error if the packed layout is not enabled.
Cutting pass: Each sequence is streamed in its original order. A rolling window of the last k unambiguous bases is maintained; a non-ACGT base (such as N) clears the window, so no cut is made at N and no k-mer spans it. When the window holds a full k-mer, SHRED looks up its four right extensions and then its four left extensions. If more than one extension has a nonzero count, the k-mer is a branch and the current piece ends after its last base. A k-mer that is repeated but has only one neighbor on each side does not cause a cut.

Pieces are half-open intervals that partition each input sequence exactly, with no gaps or overlaps. Adjacent branch points can produce pieces of 1 base. Ns and short tails are kept in the output. After the cutting pass, SHRED checks that the bases read equal the bases counted in the first pass, and that the bases emitted equal the bases read; a mismatch aborts the run. Output is written in batches of 256 reads.

Piece names use the same original_name_start-end format as length-based shredding, with the prefix, filetid, and headertid options applied in the same way. The run summary also reports the number of branch k-mers found.

Coordinate Naming

Shred names follow the format original_name_start-end where start and end represent 0-based coordinates in the original sequence. When taxonomic IDs are parsed (via filetid or headertid), the format becomes original_name_start-end_tid_XXXXX.

Quality Score Handling

For FASTQ input, original quality scores are preserved and trimmed to match shred coordinates. For FASTA input with FASTQ output, uniform quality scores specified by qfake are assigned to all bases.

Memory Optimization

In length-based modes (k=0), SHRED uses streaming processing with buffer limits set by Shared.capBuffers(4) and Shared.capBufferLen(100). The ConcurrentReadInputStream processes reads in batches using ListNum<Read> structures, maintaining O(1) memory usage independent of input file size.

Branch mode (k above 0) is not constant-memory: it holds a k-mer table for the whole input. With k above 31 and hashonly=t (the default), each allocated table slot stores a 16-byte hash key plus a 4-byte count, 20 bytes per slot, independent of k. With hashonly=f, the table stores full packed k-mer keys, so the per-slot size grows with k. Small-k tables (k 31 and below) are not affected by hashonly.

Performance Characteristics

Time Complexity: O(n) where n is total input bases (length-based modes)
Space Complexity: O(1) constant memory usage with streaming (length-based modes); branch mode memory is the k-mer table described above
Branch Mode Passes: Two passes over the input file (counting, then cutting); the input must be a regular file that can be read twice
I/O Optimization: Enables ReadWrite.USE_PIGZ=true and ReadWrite.USE_UNPIGZ=true with thread count set via ReadWrite.setZipThreads(Shared.threads())
Array Operations: Uses KillSwitch.copyOfRange() for byte array operations creating shred bases and quality scores

Support

For questions and support:

Email: bbushnell@lbl.gov
Documentation: bbmap.org