A Count Filter Is Not an Assembler
Partition observed k-mer counts by a declared threshold and keep both sides visible.
Original synthetic inputs; computed records, not biological motion. The written trace below is the text equivalent.The problem
A count threshold is a deliberately small teaching rule. Windows whose total occurrence count reaches the threshold go into a kept map, and the rest go into a rejected map. Both maps must be reported because a singleton can be genuine and a repeated error can pass. The operation is a partition of the observed multiset, not an assembler and not an error-correcting algorithm with a measured accuracy.
Trace the program
The demo reads ATGCG twice and ATGAG once with k equal to three and threshold two. ATG occurs three times, GCG twice, and TGC twice, so those three keys are kept. GAG and TGA each occur once and are rejected. Sorting the keys in each map makes the output deterministic. The program does not remove reads, merge reverse complements, or invent a k-mer that was never observed.
The live graph
Edit the reads, k, threshold or source and run the program. The result contains the kept and rejected maps. Reset restores the demonstration reads.
The path and degree checks are local functions in the displayed program, so its connectivity assumptions can be inspected independently.
from collections import Counter
import json
from bio_data import DNA_BASES
data = json.loads(input())
reads, k, t = (data['reads'], data['k'], data['threshold'])
if k < 2 or t < 1 or (not reads) or any((not r or len(r) < k or any((b not in DNA_BASES for b in r)) for r in reads)):
raise ValueError('invalid input')
counts = Counter((x for r in reads for x in [r[i:i + k] for i in range(len(r) - k + 1)]))
kept = {x: counts[x] for x in sorted(counts) if counts[x] >= t}
rejected = {x: counts[x] for x in sorted(counts) if counts[x] < t}
result = {'kept': kept, 'rejected': rejected}
print(result)
{
"kept": {
"ATG": 3,
"GCG": 2,
"TGC": 2
},
"rejected": {
"GAG": 1,
"TGA": 1
}
}Browse the declared helper library
"""Declared input/model data only; algorithms are written in each program."""
DNA_BASES = 'ACGT'
Your turn
For each supplied read list, k, and integer threshold t, return two lexicographically ordered maps: kept for counts greater than or equal to t, and rejected for counts below t. Include every observed k-mer exactly once, including when kept is empty. Reject invalid k, reads or threshold. Set result to an object with kept and rejected.
import json
data = json.loads(input())
reads, k = (data['reads'], data['k'])
counts = {}
for r in reads:
for i in range(len(r) - k + 1):
x = r[i:i + k]
counts[x] = counts.get(x, 0) + 1
result = {'kept': dict(sorted(counts.items())), 'rejected': {}}
print(result)
For each supplied read list, k, and integer threshold t, return two lexicographically ordered maps: kept for counts greater than or equal to t, and rejected for counts below t. Include every observed k-mer exactly once, including when kept is empty. Reject invalid k, reads or threshold. Set result to an object with kept and rejected.
{
"kept": {
"ACG": 3,
"CGG": 1,
"CGT": 2
},
"rejected": {}
}Browse the declared helper library
"""Declared input/model data only; algorithms are written in each program."""
DNA_BASES = 'ACGT'
Boundaries and interpretation
The threshold is a heuristic on synthetic counts. It has no sensitivity, specificity, coverage, quality-score, or clinical meaning, and it cannot distinguish a genuine low-coverage window from a sequencing error. The page does not use paired reads, long-range links, or an overlap layout. Its kept graph is only a smaller observed graph, not a finished assembly.
A threshold of one keeps every observed window, while a threshold above the largest count keeps none; neither outcome is an error. The two maps partition the same key set, so a key must never appear in both. The count is over observed windows, not over reads or bases.
The threshold partition is computed from the same count map for both maps, so the kept and rejected keys are disjoint and together exhaust the observed windows. The page does not re-estimate counts after filtering, because that would change the evidence rather than merely select it. A higher threshold therefore removes keys without altering the counts of the keys that remain.
Recap
- The filter partitions observed counts at a declared threshold.
- A singleton can be genuine and a repeated error can pass.
- Kept and rejected maps both belong in the result.
Synthetic data: CC0-1.0. No personal data are sent anywhere.