Why finding palindromes?

My former neighbor is an author. Many years ago he was writing a historical novel about the colonial past of the Netherlands. Unfortunately, his apartment was broken into, and the laptop that contained all material for the book was stolen. He had made no backups, and decided to write another book instead.

Things break, disappear, get lost, or fall apart. Dead things, like laptops, washing machines, and light bulbs, need to be replaced or repaired when they break. Living things have some advanced repair mechanisms, with which they repair a broken leg, a bleeding finger, or a missing leaf.

To repair their parts, living things use the building plans available in their cells. These building plans are expressed in DNA. Each cell contains a complete copy of the DNA of an organism. When an organism builds a new cell, or repairs part of the organism that has been damaged, it uses DNA to create new cells. But what if the building plans themselves get damaged? Then reparation wouldn't be possible anymore, or would lead to malformed parts.

The DNA mechanism has several means to repair broken DNA. Most of these means consist of maintaining copies of the DNA, using multiple copies of DNA to construct a new copy, or by repeating pieces of DNA inside the DNA itself. But one of the most intriguing mechanisms DNA uses is storing information in palindromes. If DNA in one half of a palindrome gets broken, the other half of the palindrome tells how to repair the broken DNA.

A palindrome is a number, verse, word or a phrase that is the same whether you read it backwards or forwards, for example the word "refer".

When I started as a PhD student in Computer Science in 1988, my professor gave the following problem assignment to me. Construct an algorithm that, when given a string, finds the longest palindrome substring occurring in the string. For example, given the string "yabadabadoo", the algorithm should return the substring "abadaba". The algorithm should not only return the longest palindrome substring, it should also return it fast. The requirement was that the algorithm should only use a number of steps comparable to the length of the argument string. This was a difficult problem, which gave me severe headaches in the months to follow. I spent four months on the problem, and solved it. The one comment I got from my professor was "The best thing about this problem and its solution is that they have absolutely no practical relevance."

He was wrong.

Palindromes play an important role in the world around us. Palindromes appear in poetry, music, math, and in genomes: human life depends on palindromes! It is intriguing that a concept generally considered nice but useless is fundamental to our existence.

This blog discusses where palindromes come from, where they appear around us, what role they play in human life, and how you can use a computer to find them. The latter focus is inspired by my work during my PhD, and is essential for finding palindromes in DNA. The resulting program for finding palindromes can also be used to find palindromes in other sizable sources. For example, what is the longest palindrome occurring in the bible? Of course, this depends on the version of the bible, but suppose we take the King James Bible. I will reveal the longest palindrome in the bible in a later blog post, in which I describe an algorithm for finding palindromes.