July 29, 2015, 12:29 a.m. by Rosalind Team
Given a collection of strings Dna and an integer d, a k-mer is a (k,d)-motif if it appears in every string from Dna with at most d mismatches. The following algorithm finds (k,d)-motifs.
MOTIFENUMERATION(Dna, k, d)
Patterns ← an empty set
for each k-mer Pattern in Dna
for each k-mer Pattern’ differing from Pattern by at most d
if Pattern' appears in each string from Dna with at most d
add Pattern' to Patterns
remove duplicates from Patterns
Implement MotifEnumeration (shown above) to find all (k, d)-motifs in a collection of strings.
Given: Integers k and d, followed by a collection of strings Dna.
Return: All (k, d)-motifs in Dna.
3 1 ATTTGGC TGCCTTA CGGTATC GAAAATT
ATA ATT GTT TTT