CoveringSet

Script: coveringset.sh Package: prok Class: CoveringSet.java

Greedy set-cover kmer selection for tRNA (or any short-gene) covering sets. Iteratively selects the most prevalent kmers from a pool of sequences, evicts covered sequences, and repeats until a coverage target or kmer budget is reached.

Basic Usage

coveringset.sh in=<file> out=<file>

Builds a small kmer set that collectively "covers" (matches at least one kmer in) as much of the input sequence pool as possible, useful for building compact detection sets for short genes like tRNAs.

Parameters

Parameters control the input pool, kmer length, and the greedy selection process.

Input Parameters

in=<file>
Input FASTA of pool sequences (e.g. all tRNAs). Required parameter.
extra=<file>
Optional additional sequences to weight the pool, typically consensus models. Added copies= times.
copies=10
Number of copies of extra sequences to add to the pool.
rcomp=f
Also add the reverse-complement of each input sequence to the pool.

Kmer Parameters

k=17
Kmer length used for both selection and output.
kdesign=
If set, selection runs at this k but output is decomposed to k. For example kdesign=18 k=17 selects 18-mers, then outputs their constituent 17-mers; each covered sequence then has >=2 kmer hits, which enables minkmerhits=2 downstream for free.

Selection Parameters

step=500
Number of kmers selected per round.
maxkmers=
Maximum total kmers to select. 0 means no limit.
target=0.999
Stop once this fraction of pool sequences is covered.

Java Parameters

-Xmx
Set memory usage. Default is autodetected.

Examples

Basic Covering Set

coveringset.sh in=all_trnas.fasta out=covering_kmers.fasta

Selects a default k=17 kmer set covering 99.9% of the input tRNA pool, 500 kmers per round.

Weighting with Consensus Models

coveringset.sh in=all_trnas.fasta extra=trna_consensus.fasta copies=20 out=covering_kmers.fasta

Adds 20 copies of the consensus sequences into the pool before selection, biasing coverage toward kmers shared with the consensus models.

Design-at-k, Output-at-Lower-k

coveringset.sh in=all_trnas.fasta kdesign=18 k=17 minkmerhits=2 out=covering_kmers.fasta

Selects using 18-mers for specificity, but outputs the constituent 17-mers so each covered sequence carries at least 2 kmer hits — enabling a minkmerhits=2 threshold in whatever tool consumes this set.

How It Works

CoveringSet uses a two-tier greedy ranking each round: it selects the top 2×step kmers by current count on the remaining (not-yet-covered) pool, then re-sorts that shortlist by original prevalence — prevalence measured before any eviction — and keeps only the top step. This concentrates selection on kmers that are shared between rare and common sequences, rather than kmers that happen to be common only among the stragglers left late in the process. Sequences are evicted from the pool once covered, and the process repeats until the target coverage fraction or the kmer budget is reached.

Support

For questions and support: