Palindromes in DNA
DNA is two strands, and the second reads like the first backwards with A↔T and C↔G swapped. A piece that does not change under this swap is called a palindrome: for example, GAATTC, recognised by the enzyme EcoRI. Find the longest palindrome in a sequence and count how many palindromes it has in all: each occurrence of each length counts separately.
Tests three to six are the genomes of phages λ, T7 and φX174 and of human mitochondria from NCBI. The mitochondrion has one letter N, an unknown nucleotide: it pairs with no letter.
Input
One line of the letters A, C, G, T and N, of length 1 to 5 · 10⁵.
Output
The first line holds the length of the longest palindrome and the number of its first letter (from one); if there are several longest, the leftmost; if there are no palindromes, 0 0. The second line holds the number of all palindromes.
Examples
Example 1
CCGAATTCGTTA
8 2 7
Example 2
ACGTTAACGT
10 1 9
Limits
- Time · Python
- 5000 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
Can a palindrome in DNA have odd length? What would then have to be true of the middle letter?
2Hint 2
The centre of a palindrome is a gap between letters. If there is a palindrome of length 2r around a gap, then around it there are palindromes of lengths 2, 4, …, 2r, and no others with this centre. So the answer to the second question is the sum of the radii. It remains to find the radius of each gap faster than by expanding anew.
3The idea
Manacher’s algorithm with “equal” replaced by “complementary”. Reflection inside a palindrome takes a word to its reverse-complement copy, and for a palindrome that is itself, so the mirror works: the radius at a gap inside the rightmost palindrome is at least the radius at the reflected gap, cut down to the edge.
4Walkthrough
Go over the gaps from left to right and keep the rightmost palindrome [left, right). For gap i inside it, start with min(radius(left + right − i), right − i), then compare pairs of letters outwards. The letter N pairs with nobody: the dictionary of pairs simply finds no pair without it. The sum of the radii on the string ATAT… of length 5 · 10⁵ is 6.25 · 10¹⁰: a 64-bit counter is needed.
4+Solution
5Complexity
O(n): a successful comparison moves the right edge, and there is one unsuccessful comparison per gap.
6Common mistakes
- Expanding from each centre anew. This is
wrong.py. On genomes it makes it in time, as the palindromes there are short. But the seventh test is the string ATAT…AT, and around every second gap the palindrome stretches to the edge: about n²/4 work. - Odd centres. If palindromes are also sought around letters, comparing letters in pairs with the swap, the middle letter is compared with nothing and silently accepted: the “palindrome” ACG will be found.
- Thirty-two bits. The answer in the seventh test does not fit in int32.
- Not the leftmost. With equal lengths the palindrome that starts earlier is needed; update the answer only on a strictly greater length.