A primer with no twins
To multiply a gene in a test tube by PCR, primers are chosen for it: short DNA chains from which copying starts. A forward primer repeats the beginning of the gene. DNA is double-stranded, and a primer binds where one of the strands has a sequence complementary to it. So it will bind not only to the beginning of the gene but also to any place where the same sequence occurs again in the gene, and to where the gene has its reverse complement: the letters replaced by their pairs A↔T, C↔G and written in reverse order. Each extra place means extra copies in the tube.
Let us simplify: a primer is the beginning of the gene of length k, and it is good if this sequence occurs in the gene exactly once, at the very beginning, and never occurs in the reverse complement of the gene. For each gene find the smallest such k. If no beginning is good, up to the whole gene, output −1.
For example, the gene ATGTTTCAT has the reverse complement ATGAAACAT. The beginning ATG occurs in it, so a three-letter primer will bind to the other strand too; only ATGT is good, k = 4. Among the tests are nineteen genes of phage lambda and thirteen protein genes of human mitochondria.
Input
The first line holds the number of genes t (1 ≤ t ≤ 1000). Each of the next t lines holds a gene of the letters A, C, G, T. The total length of the genes is at most 300,000.
Output
For each gene, on a separate line, the smallest suitable k or −1.
Examples
Example 1
3 ATGACATGAC ATGCAT ATGTTTCAT
6 -1 4
Example 2
1 ATGTACTAAGGAGGTTGTATGGAACAACGCATAACCCTGAAAGATTATGCAATGCGCTTTGGGCAAACCAAGACAGCTAAAGATCTCGGCGTATATCAAAGCGCGATCAACAAGGCCATTCATGCAGGCCGAAAGATTTTTTTAACTATAAACGCTGATGGAAGCGTTTATGCGGAAGAGGTAAAGCCCTTCCCGAGTAACAAAAAAACAACAGCATAAATAACCCCGCTCTTACACATTCCAGCCCTGAAAAAGGGCATCAAATTAAACCACACCTATGGTGTATGCATTTA
5
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
If a beginning of length k is good, so is any longer one: a longer beginning has no more twins than a shorter one. So the answer is “the longest beginning that has a twin” plus one.
2Hint 2
The longest beginning that occurs again in the gene from position i is z[i], the value of the gene’s Z-function. The other strand remains.
3Hint 3
Whether the beginning of the gene occurs in its reverse complement is a search for the beginning of string g in another string. Glue together g + “#” + the reverse complement and compute the Z-function of the result.
4The idea
Let M be the greatest length for which the beginning of the gene matches the text at some other place: on its own strand that is max z[i] over i ≥ 1, on the other the maximum of the Z-function of g + “#” + rc(g) over the positions to the right of the “#”. All beginnings of length up to M have a twin, and the beginning of length M + 1 no longer does. The answer is M + 1, if that does not exceed the length of the gene.
5Walkthrough
Two Z-functions per gene: of the gene itself and of its concatenation with the reverse complement. The separator “#” keeps a match from stepping over from the gene into the complement, so the values to the right of it are exactly the lengths of the common beginnings of the gene and the tails of the complement.
The answer −1 occurs only for a gene that is its own reverse complement, like the enzyme site GAATTC: then even the whole gene occurs on the other strand. Real genes have small answers, 4–9 letters, and that makes sense: a random word of k letters occurs in a gene of length n roughly n/4k times. Real primers are longer, 18–25 letters, because they must be unique in the whole genome, not in one gene, and bind firmly.
5+Solution
6Complexity
O(n) per gene of length n, O(Σn) in all: about 900 thousand Z-algorithm steps on the largest test. Trying each k with a substring search costs O(n) per k: on a gene whose beginning repeats for 20,000 letters that is billions of comparisons.
7Common mistakes
- Only one’s own strand. Looking for twins of the beginning only in the gene itself. The gene ATGTTTCAT then gives 3, although ATG stands in the reverse complement ATGAAACAT, and the primer will bind there.
- A complement without reversal. Replacing letters by their pairs is not enough: the other strand is read in the opposite direction. TACAAAGTA is not the sequence the primer binds to.
- z[0] in the maximum. By convention z[0] is the length of the whole string, and if it is not excluded, the answer is always −1.