The war between viruses and bacteria has been waged for over a billion years.
Viruses called bacteriophages (or simply phages) require
a bacterial host to propagate, and so they must somehow infiltrate the bacterium;
such deception can only be achieved if the phage understands the genetic framework
underlying the bacterium's cellular functions. The phage's goal is to insert DNA that will be
replicated within the bacterium and lead to the reproduction of as many copies of the phage as possible,
which sometimes also involves the bacterium's demise.
To defend itself, the bacterium must either obfuscate its cellular functions so that the phage cannot infiltrate it,
or better yet, go on the counterattack by calling in the air force.
Specifically, the bacterium employs aerial scouts called restriction enzymes,
which operate by cutting through viral DNA to cripple the phage.
But what kind of DNA are restriction enzymes looking for?
The restriction enzyme is a homodimer, which means that it is composed of two identical substructures.
Each of these structures
separates from the restriction enzyme in order to bind to and cut one strand of the phage DNA molecule;
both substructures are pre-programmed with the same target
string containing 4 to 12 nucleotides to search for within the phage DNA (see Figure 1.).
The chance that both strands of phage DNA will
be cut (thus crippling the phage) is greater if the target is located on both strands of phage DNA, as close to each other as possible.
By extension, the best chance of disarming the phage occurs when the two target copies appear
directly across from each other along the phage DNA, a phenomenon that occurs precisely when the target is equal
to its own reverse complement. Eons of evolution have made sure that most restriction enzyme targets
now have this form.
Problem
Figure 2. Palindromic recognition site
A DNA string is a reverse palindrome if it is equal to its reverse complement.
For instance, GCATGC is a reverse palindrome because its reverse complement is GCATGC. See Figure 2.
Return: The position and length of every reverse palindrome
in the string having length between 4 and 12. You may return these pairs in any order.
Sample Dataset
>Rosalind_24
TCAATGCATGCGGGTCTATATGCAT
Sample Output
4 6
5 4
6 6
7 4
17 4
18 4
20 6
21 4
Extra Informationclick to expand
You may be curious how the bacterium prevents its own DNA from being cut by restriction
enzymes. The short answer is that it locks itself from being cut through a chemical
process called DNA methylation.