STR Strings and text Algorithm
Manacher’s algorithm
Also known as: Manacher · longest palindromic substring · all palindromes of a string · palindromes in DNA · reverse-complement palindrome
All palindromes of a string in one pass: for every letter and every gap, the length of the longest palindrome centred there. The rightmost palindrome found works as a mirror: the radius at a centre inside it is already known from the reflected centre.
The DNA of phage λ has 48,502 letters. Six-letter words that coincide with their reverse-complement copy, like GAATTC, occur in it 460 times, while from the frequencies of its own short words 698 would be expected. Phages avoid such words: bacteria defend themselves with restriction enzymes, many of which cut DNA exactly at palindromes, and it pays a phage to have fewer places to be cut. In E. coli the avoidance is weaker, and in human mitochondria there is none at all: 212 found against 201 expected. All palindromes of a genome, of every length and wherever they are, are found in one pass by Manacher’s algorithm.
The longest palindromes in λ are 14 letters each: TCTGCCGCGGCAGA from position 20,526 and GGTTGATATCAACC from position 41,269; in the mitochondrion, TTCGCTTCGAAGCGAA, 16 letters. Such long ones are rare, but six-letter words number in the hundreds, and each is a possible cut. How the enzyme EcoRI cuts λ at GAATTC is told in the course chapter on substring search; here, how to find all palindromes at once.
The idea
The centre of a palindrome is a letter (a palindrome of odd length) or a gap between letters (even length). The radius of a centre is how many steps from it the string remains a palindrome. Naively the radius is found by expanding from each centre anew. On a text this is fast: its palindromes are short. But on the string “aaaa…a” every centre reaches the edge, and the work comes to about n²/4.
Manacher notices that a palindrome is a mirror. Suppose a palindrome has been found that reaches furthest to the right, the segment [l, r] with centre c. For a centre i inside it, the reflection j = l + r − i lies to the left, and its radius is already known. Everything visible around j within the segment is reflected around i.
The radius at a centre i inside the rightmost palindrome [l, r] is at least min(radius(j), r − i), where j is the reflection of i. Start from this number and compare further. Each successful comparison pushes the right edge r along, and there is one unsuccessful comparison per centre, so there are O(n) comparisons in all.
To avoid keeping two cases, a separator is inserted between letters: “aba” turns into “|a|b|a|”, and every palindrome gets a centre that is a position. The radius in the new string equals the length of the palindrome in the old one. Watch the mirror step by step. At the bottom, a bar of each centre’s radius grows under it, and a counter compares the number of comparisons with naive expansion.
«А роза упала на лапу Азора» (“And the rose fell on Azor’s paw”) is the Russian palindrome that Malvina dictates to Buratino, and it is attributed to Afanasy Fet. Its right half lies entirely inside the palindrome centred in the middle, and almost every radius in it is taken from the mirror without a single successful comparison. The longest palindromes of War and Peace, ignoring spaces, punctuation and case, are 11 letters each, and one of them is in the delirium of the wounded Prince Andrei: «и пити-пити-пити».
Why it is correct and fast
Let [l, r] be a palindrome with centre c, let the centre i lie in [c, r], j = l + r − i, and let dj be the radius at j. Then the radius at i is at least min(dj, r − i). If dj < r − i, it equals dj; if [l, r] cannot be extended and dj > r − i, it equals r − i.
Reflection about c takes position x to l + r − x and within [l, r] does not change letters: it is a palindrome. Let k ≤ min(dj, r − i). The positions i − k and i + k lie in [l, r] and are reflected to j + k and j − k, where the letters are equal because k ≤ dj. So the letters at i ± k are equal too.
If dj < r − i, then at step dj + 1 around j the letters differ, and both positions are still inside [l, r], so their reflections around i differ too. If dj > r − i, write k = r − i + 1. The letter at i − k lies in the segment and is reflected to j + k, and there, since k ≤ dj, stands the same as at j − k = l − 1. If i + k = r + 1 held the same letter as i − k, the letters at l − 1 and r + 1 would coincide and [l, r] would extend.
Manacher’s algorithm makes fewer than 2m comparisons, where m is the length of the string with separators.
An unsuccessful comparison ends the work on a centre; there are at most m of them. If the starting radius is less than r − i, then by the mirror theorem it is final, and the very first comparison fails. Otherwise the starting radius equals r − i (or the centre is to the right of r, and it is zero), and each successful comparison opens a position to the right of r. After the centre the edge becomes i + radius, that is, each successful comparison moves it by exactly one position. The edge does not go past the end of the string, so there are fewer than m successful comparisons.
For DNA everything is the same, only “equal” means “complementary”: A opposite T, C opposite G. Reflection inside a reverse-complement palindrome takes a word to its reverse-complement copy, and for a palindrome that is itself, so the mirror works. There are no letter centres: the middle letter would have to pair with itself, and DNA has no such letter. Gaps remain, and it is their radius that the code computes, without separators.
Code
For each gap, the radius of the reverse-complement palindrome around it. There are exactly as many palindromes of length m as gaps with radius at least m/2: each such gap has one word of length m. The expectation comes from words one and two letters shorter, as in Gelfand and Koonin: a word w = a…b would occur N(a…) · N(…b) / N(…) times if each letter depended only on the m − 2 previous ones.
What it costs
| Method | Time | Notes |
|---|---|---|
| Check every substring | O(n³) | n²/2 substrings, checking each takes up to n |
| Expand from every centre | O(n + the sum of radii) | almost linear on text, n²/4 on “aaaa…” |
| Hashes and binary search on the radius | O(n log n) | wrong with a small probability |
| Manacher | O(n) | exact, fewer than 2m comparisons |
On genomes naive expansion hardly loses: their palindromes are short. But a string of repeats of AT is its own reverse-complement copy, and around every second gap the palindrome stretches to the edge. Such stretches, microsatellites, do occur in real genomes.
With four thousand letters the naive method is several hundred times slower in Python, with 32 thousand letters in Go almost a thousand times. Manacher grows linearly and with a million letters in Go fits into 12 milliseconds.
Where it is easy to go wrong
- Only odd palindromes. If the centres are letters alone, “abba” will not be found. Gaps are needed too: two arrays of radii or separators.
- A separator from the text. If the separator occurs in the string, it will match itself where it should not. Take a character that is certainly not in the text, or do without, with two arrays.
- An inclusive edge or not. The reflection j = l + r − i is derived for the segment [l, r] including both ends. In the listing a palindrome is a half-open run of letters [left, right), and the centres are gaps, and the formula is the same only because gaps are numbered differently from letters. A mixed-up formula gives the radius of someone else’s centre, and the error does not show on every test.
- Odd centres in DNA. With “equal” replaced by “complementary”, a letter centre is compared with nothing and silently accepted, giving palindromes that are not there. In DNA the centres are gaps only.
- N in the sequence. In human mitochondria position 3107 holds N, an unknown letter. It pairs with no letter and breaks a palindrome, and the dictionary of pairs must not crash without it.
Where it works
The longest palindrome and all palindromes of a string; the number of palindromic substrings is the sum of the radii. In bioinformatics, reverse-complement palindromes: recognition sites of restriction enzymes, and, allowing for a loop and errors, RNA hairpins, though those need other algorithms. In programming contests Manacher goes alongside hashes and the palindromic tree, the 2015 structure of Mikhail Rubinchik and Arseny Shur that stores all distinct palindromes of a string.
History
Glenn Manacher published the algorithm in 1975 in the Journal of the ACM under the title “A new linear-time ‘on-line’ algorithm for finding the smallest initial palindrome of a string”: he was looking for palindromes at the start of a string as letters were read. In 1995 Alberto Apostolico, Dany Breslauer and Zvi Galil, building a parallel algorithm for finding all palindromes, noted that the same trick gives all maximal palindromes of a string in linear time, and that is how it is used now. The avoidance of short palindromes in bacterial genomes was described by Mikhail Gelfand and Eugene Koonin in 1997: words of length 4–6 occur in them noticeably less often than expected, most strongly the recognition sites of the species’ own restriction enzymes, while the genomes of mitochondria and chloroplasts show no avoidance.
Problems
The reverse-complement palindromes of a genome: the longest and how many there are in all. And the longest palindrome of a text, ignoring spaces, punctuation and case, printed as the piece stands in the text.
Palindromes in DNA A palindrome of lettersData: Genomes: NCBI RefSeq — NC_001416.1 (phage λ), NC_001604.1 (phage T7), NC_001422.1 (phage φX174), NC_000913.3 (E. coli K-12), NC_012920.1 (human mitochondrion); expectation model after Gelfand & Koonin, Nucleic Acids Research, 1997