may form a hairpin. Palindromic motifs are made by the order of the nucleotides that specify the complex chemicals (proteins) that, as a result of those genetic instructions, the cell is to produce. They have been specially researched in bacterial chromosomes and in the so-called Bacterial Interspersed Mosaic Elements (BIMEs) scattered over them. Recently a research genome sequencing project discovered that many of the bases on the Y-chromosome are arranged as palindromes. A palindrome structure allows the Y-chromosome to repair itself by bending over at the middle if one side is damaged. It is believed that palindromes are also found in proteins, but their role in the protein function is not clearly known. It has recently been suggested that the prevalence existence of palindromes in peptides might be related to the prevalence of low-complexity regions in proteins, as palindromes frequently are associated with low-complexity sequences. Their prevalence might also be related to an alpha helical formation propensity of these sequences, or in formation of proteins/protein complexes. Computation theory In automata theory, a set of all palindromes in a given alphabet is a typical example of a language that is context-free, but not regular. This means that it is impossible for a computer with a finite amount of memory to reliably test for palindromes. (For practical purposes with modern computers, this limitation would apply only to impractically long letter sequences.) In addition, the set of palindromes may not be reliably tested by a deterministic pushdown automaton which also means that they are not LR(k)-parsable or LL(k)-parsable. When reading a palindrome from left to right, it is, in essence, impossible to locate the "middle" until the entire word has been read completely. It is possible to find the longest palindromic substring of a given input string in linear time. The palindromic density of an infinite word w over an alphabet A is defined to be zero if only finitely many prefixes are palindromes; otherwise, letting the palindromic prefixes be of lengths nk for k=1,2,... we define the density to be Among aperiodic words, the largest possible palindromic density is achieved by the Fibonacci word, which has density 1/φ, where φ is the Golden ratio. A palstar is a concatenation of palindromic strings, excluding the trivial one-letter palindromes – otherwise all strings would be palstars. Notable palindromists Dmitry Avaliani (1938–2003) Howard W. Bergerson (1922–2011) Hugo Brandt Corstius (1935–2014) Simo Frangén (b. 1963) Pasi