Most Frequent k-mers

Intermediate Bioinformatics k-mer Frequency Motif Discovery
Significance:

Over-represented k-mers are the signal that motif-discovery algorithms chase: the DnaA box that
marks a bacterial replication origin was found precisely this way. k-mer counting is also the
computational core of modern assemblers and of alignment-free comparison methods.

Statement

Given a DNA string text and an integer k, find every k-mer (substring of length k) that
occurs the maximum number of times in text. Occurrences may overlap.

Print the winning k-mers separated by single spaces, in lexicographic (alphabetical) order,
on one line. Sorting is required so the answer is unique when several k-mers tie.

Input — read from standard input
Variable Type Description
text
line 1
 str The DNA sequence to scan
1 <= len(text) <= 1000, uppercase A, C, G, T only
k
line 2
 int The k-mer length
1 <= k <= len(text)

These variables are already read for you in the starter code on the right.

Output

str the most frequent k-mers, space-separated, in lexicographic order

Sample Cases
Sample 1
Input
ACGTTGCATGTCGCATGATGCATGAGAGCT
4
Expected Output
CATG GCAT
CATG and GCAT both occur three times; sorted alphabetically, CATG comes first.
Sample 2
Input
AAAAA
2
Expected Output
AA
AA is the only 2-mer, occurring four times.

Submit also runs your code against 4 hidden test cases. Hidden inputs are never shown — if one fails you'll get its number and a description of the mismatch, not the data.

Constraints
  • 1 <= length(text) <= 1000
  • 1 <= k <= length(text)
  • Occurrences may overlap
  • Output must be sorted lexicographically, otherwise ties would be ambiguous
Further Reading
  • collections.Counter over every text[i:i+k] window gives the counts directly.
  • Find the maximum count first, then collect and sort every k-mer with that count.
My Notes
Log in to save personal notes.
Console output will appear here when you click Run Code or Submit...
Expected: text (str), k (int)
Next Problem
RNA Splicing