Transcription factors bind short, degenerate sequence motifs scattered across the
regulatory regions of co-expressed genes. Finding those motifs from sequence alone is one of the
foundational problems in computational biology, and the greedy approach — build a profile from what you
have, use it to pick the next best match, repeat — is the conceptual ancestor of Gibbs sampling and the
expectation-maximisation methods behind MEME. Laplace pseudocounts matter here: without them a single
missing base zeroes out an otherwise excellent candidate.
Statement
Given a collection of DNA strings and integers k and t, find a k-mer motif in each
of the t strings using greedy motif search with Laplace pseudocounts.
The algorithm:
- For each
k-mer in the first string, treat it as the first motif. - Build a profile matrix from the motifs chosen so far, adding 1 to every count (Laplace rule).
- For each subsequent string, choose the
k-mer that the current profile scores highest. On ties,
choose the leftmost. - Score the resulting motif set by total Hamming distance from its consensus, and keep the best set.
- On tied scores, keep the set found earliest.
Print the t chosen motifs, one per line, in the order of their source strings.
Input — read from standard input
| Variable | Type | Description |
|---|---|---|
k
line 1
|
int |
The motif length
2 <= k <= 12
|
t
line 1
|
int |
The number of DNA strings
2 <= t <= 25
|
dna
line 2..t+1
|
str |
One DNA string per line, all of equal length
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 t motif strings of length k, one per line, in input string order
Sample Cases
3 5
GGCGTTCAGGCA
AAGAATCAGTCA
CAAGGAGTTCGC
CACGTCAATCAC
CAATAATATTCG
TTC
ATC
TTC
ATC
TTC
2 2
ACGT
TGCA
AC
GC
Submit 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
kandtappear on the first line, separated by a space- All
tDNA strings have equal length and contain onlyA,C,G,T - Profile probabilities use Laplace pseudocounts: every count starts at 1, denominator is
t + 4 - All ties — both in profile-most-probable selection and in final scoring — resolve to the earliest
candidate, which makes the answer unique
Further Reading
- Build the profile as
(count + 1) / (number_of_motifs + 4)for each base at each column. - The profile-most-probable k-mer is the one maximising the product of per-column probabilities.
- Score is the sum over columns of
(number of motifs) - (count of the most common base).