Where greedy motif search is fast but can miss the true answer, the median string
approach is exhaustive and provably optimal: it examines every possible k-mer in the entire sequence
space and picks the one minimising total distance to the input strings. The cost is 4^k work, which
is precisely why motif finding is hard and why heuristics dominate in practice. Implementing both gives
you the exact trade-off that shapes the whole field.
Statement
Given a set of DNA strings and an integer k, find a median string: the k-mer
that minimises the sum, over all input strings, of the minimum Hamming distance between that k-mer
and any k-mer in the string.
If several k-mers tie for the minimum total distance, print the lexicographically smallest.
Print the median string on one line.
Input — read from standard input
| Variable | Type | Description |
|---|---|---|
k
line 1
|
int |
The motif length
2 <= k <= 7
|
dna
line 2..n
|
str |
One DNA string per line
1 <= strings <= 20, k <= length <= 200, uppercase A, C, G, T only
|
These variables are already read for you in the starter code on the right.
Output
str the lexicographically smallest median string of length k
Sample Cases
3
AAATTGACGCAT
GACGACCACGTT
CGTCAGCGCCTG
GCTGAGCACCGG
AGTACGGGACAG
ACG2
ACGT
ACGT
ACSubmit also runs your code against 3 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
2 <= k <= 7, so at most4^7 = 16384candidates are examined1 <= number of DNA strings <= 20- Strings may have different lengths, each at least
k - Ties resolve to the lexicographically smallest
k-mer, which makes the answer unique
Further Reading
- Generate candidates with
itertools.product("ACGT", repeat=k)— this is already lexicographic order. - For each candidate, the contribution of a string is the minimum Hamming distance over its windows.
- Iterating candidates in lexicographic order and using strict
<when updating the best gives you the
tie-break rule for free.