Sites with an N
The enzyme HinfI cuts DNA where the five letters G, A, any, T, C occur. Biologists write such a site as GANTC: the letter N in it means “any base”. Other ambiguous positions have letters of their own, approved by the IUPAC nomenclature committee:
| Letter | A, C, G, T | R | Y | S | W | K | M | B | D | H | V | N |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Bases | the letter itself | A G | C T | C G | A T | G T | A C | C G T | A G T | A C T | A C G | any |
For example, StyI has the site CCWWGG: the middle may be AA, AT, TA or TT. The prefix function and other clever search algorithms are designed for exact letter matches, while here a letter of the pattern is a whole set. Naive search does not care: it compares letter with letter anyway, and comparison simply becomes a check “is the base in the set”.
Count how many times each site occurs in the genome. Sites may overlap: in AAAA the site RR occurs three times. The genome is read as a linear molecule, along one strand, from the first letter to the last. The tests include the genomes of phages λ and φX174 and ten real enzymes.
Input
The first line holds the genome: a string of the letters A, C, G, T of length n (1 ≤ n ≤ 50,000). The second holds the number of sites q (1 ≤ q ≤ 10). Then q lines, each a site of letters from the table of length m, 1 ≤ m ≤ min(12, n).
Output
q lines: for each site, the number of positions of the genome where it starts.
Examples
Example 1
GAATTCGACTCGAGTCAA 3 GANTC CYCGRG NN
2 1 17
Example 2
AAAAAAGG 4 RR ARA AAAA GG
7 4 3 1
Limits
- Time · Python
- 4000 ms
- Time · Go
- 1000 ms
- Memory
- 256 MB
- Judging
- 10 tests
Walkthrough
Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.
1Hint 1
Take the naive search from the article and change one place in it: instead of “the text letter equals the pattern letter”, “the text letter is in the set the pattern letter stands for”.
2Hint 2
To make the check cost one operation, turn each letter of the site into a table in advance: for each of the four bases, whether it fits or not. In Python a regular expression can do the same: a site letter becomes a character class [AG].
3Hint 3
Check the second example: in AAAAAAGG the site RR occurs seven times. How many will re.findall count? Having found an occurrence, it continues searching after its end.
4The idea
Naive search draws no inferences about the text from matched letters: it simply lays the pattern against each position anew. So it does not mind that comparison is not equality but a membership check. Algorithms that remember what matched break on this: in KMP a match of A with R and of R with G does not imply that A matches G, and the borders of the pattern stop describing the text.
5Walkthrough
In Go, for each position of the site a table of 256 flags is built, and the search goes through the starts as in the article, comparing bases with the tables until the first refusal. In Python the same trial is done by the regular expression engine: the site becomes a chain of character classes, and a lookahead (?=…) looks for a match without consuming the text. So the engine tries every position in turn, and overlapping sites all get counted. This is exactly naive search, only written in C.
The answers to the third and fourth tests can be checked against a reference. In the tables of the enzyme manufacturer Promega, HinfI cuts the DNA of phage λ in 148 places and φX174 in 21, BglI in 29 and not once, DdeI in 104 and 14. Exactly as many as the solution counts.
5+Solution
6Complexity
Per site, O(n · m) in the worst case and about n checks in the usual one: in random DNA an exact first letter of a site fails in three cases of four, R or W in half. The worst test is a genome of nothing but A and sites of twelve letters that fit A almost entirely: up to 10 · 50,000 · 12 = 6 · 10⁶ checks. Go and the regular expression engine spend milliseconds on this, a plain Python loop about half a second on a fast laptop, which also fits in the time limit.
7Common mistakes
re.findallwithout a lookahead. It finds non-overlapping occurrences: in AAAA the site RR twice instead of three times. Overlaps are common in real DNA for sites with N and short sites like RR.str.countorstrings.Counton the site as it is. The letter N does not occur in the genome, and the answer is almost always zero. Besides, both functions do not count overlaps either.- Only N. “Any letter” is handled, but R, Y, W and the rest are forgotten: StyI and HaeII are then never found.
- A site longer than the genome. By the statement this does not happen, but if starts are tried up to n rather than n − m, you run past the end of the string.