K-mer Multisets Across Reads
Aggregate overlapping windows from several reads without losing occurrence counts.
Original synthetic inputs; computed records, not biological motion. The written trace below is the text equivalent.The problem
Several reads can contribute the same window. A multiset, or bag, records how many times each distinct string occurs across the whole input. The total count is not the number of reads and not the number of distinct strings. It is the number of valid start positions whose window has that text. Overlapping occurrences inside one read count separately, which is why a naive string count can undercount a run such as AAA.
Trace the program
The demo reads ATGCG twice and ATGAG once with k equal to three. ATG occurs three times, GCG twice, TGC twice, and GAG and TGA once each. Sorting the keys makes the serialization deterministic without changing any count. The program keeps singleton keys because a count of one is evidence of one occurrence, not an absent observation.
The live graph
Change the reads, their shared k, or both, then run the program. The result is one sorted object from window text to total occurrences. Reset restores the demonstration reads.
The counting loop is visible here; the supplied alphabet defines accepted bases without performing any counting.
import json
from bio_data import DNA_BASES
data = json.loads(input())
reads, k = (data['reads'], data['k'])
if k < 2 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 = {}
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 = {x: counts[x] for x in sorted(counts)}
print(result)
{
"ATG": 3,
"GAG": 1,
"GCG": 2,
"TGA": 1,
"TGC": 2
}Browse the declared helper library
"""Declared input/model data only; algorithms are written in each program."""
DNA_BASES = 'ACGT'
Your turn
For each supplied nonempty list of DNA reads and shared k, return one lexicographically ordered object mapping every observed k-mer to its total occurrence count. Include singleton counts. Reject invalid k or reads outside the declared alphabet. Set result to that object.
import json
data = json.loads(input())
reads, k = (data['reads'], data['k'])
r = reads[0]
counts = {}
for i in range(len(r) - k + 1):
x = r[i:i + k]
counts[x] = counts.get(x, 0) + 1
result = {x: counts[x] for x in sorted(counts)}
print(result)
For each supplied nonempty list of DNA reads and shared k, return one lexicographically ordered object mapping every observed k-mer to its total occurrence count. Include singleton counts. Reject invalid k or reads outside the declared alphabet. Set result to that object.
{
"ATA": 1,
"TAT": 1
}Browse the declared helper library
"""Declared input/model data only; algorithms are written in each program."""
DNA_BASES = 'ACGT'
Boundaries and interpretation
Counts describe this synthetic read bag. A count of three does not establish three biological copies, three cells, or three sequencing runs. Repeats, amplification bias, and errors can all inflate an observed count. The page deliberately uses overlapping occurrences, so a method that counts non-overlapping matches answers a different question. It also does not merge reverse complements or perform error correction.
Overlapping windows are counted at every start position, including positions that share letters with the previous window. The result is a map of observed text, not a list of reads, and the order of reads does not change the totals. A read shorter than k contributes no window and is rejected rather than silently ignored. The sorted key order is only a serialization rule.
The read order changes neither the key set nor the totals, because addition is commutative. The shared k must be valid for every read, not only the first, so one short read rejects the whole input instead of contributing a partial bag. A count map is therefore a property of the declared read multiset and k, not of the order in which the reads arrive.
Recap
- Aggregation sums occurrences across reads and across overlapping positions.
- Singleton keys stay visible because one occurrence is still an observation.
- A k-mer count is not a coverage estimate or a biological copy number.
Synthetic data: CC0-1.0. No personal data are sent anywhere.