Find Frequent Words with Mismatches and Reverse Complements solved by 1478

We now extend “Find the Most Frequent Words with Mismatches in a String” to find frequent words with both mismatches and reverse complements. Recall that Pattern refers to the reverse complement of Pattern.

Frequent Words with Mismatches and Reverse Complements Problem

Find the most frequent k-mers (with mismatches and reverse complements) in a DNA string.

Given: A DNA string Text as well as integers k and d.

Return: All k-mers Pattern maximizing the sum Count_d(Text, Pattern) + Count_d(Text, Pattern) over all possible k-mers.

Sample Dataset

ACGTTGCATGTCGCATGATGCATGAGAGCT
4 1

Sample Output

ATGT ACAT

Extra Datasets

Click for debug datasets

Note

As in “Find the Most Frequent Words with Mismatches in a String”, it is not necessary for Pattern to appear in Text in order to to solve the Frequent Words with Mismatches and Reverse Complements Problem for Text.