As you may know, in DNA there are four bases — adenine (
A), cytosine (
C), guanine (
G) and thymine (
A bonds with
C bonds with
G, forming the "rungs" of the DNA double helix structure.
We define the complement of a base to be the base it bonds to — i.e. the complement of
T, the complement of
A, the complement of
G and the complement of
C. We can also define the complement of a DNA string to be the string with each base complemented, e.g. the complement of
Because of the double-stranded structure of DNA, the bases on one strand are complementary to the bases on the other strand. However DNA has a direction, and DNA transcription occurs in opposite directions on the two strands. Hence molecular biologists are often interested in the reverse complement of a DNA string — quite literally the reverse of the complement of the string.
To extend our previous example, the reverse complement of
CTATAG backwards, so
GATATC. As you may have noticed, in this example the reverse complement is equal to the original string — we call such a string a reverse palindrome.*
Given a string of DNA, can you find the longest substring which is a reverse palindrome?
*I use the term "reverse palindrome", taken from Rosalind, to differentiate from the usual meaning of palindrome.
Input will be a single string consisting of only the characters
ACGT in upper case. You may write either a function or a full program for this challenge.
You may choose to output via either printing or returning (the latter choice is only available in the case of a function).
Your program should output the longest reverse palindromic substring of the input string, if there is a unique solution. If multiple solutions exist, then you may either output any single one of them, or all of them (your choice). Duplicates are okay if you choose to output all of them.
The input is guaranteed to have a solution of at least length 2.
ATGGATCCG -> GGATCC
The reverse complement of
GGATCC is itself (
GGATCC --complement--> CCTAGG --reverse--> GGATCC), so
GGATCC is a reverse palindrome.
GATC is also a reverse palindome, but it is not the longest one.
AT -> AT CGT -> CG AGCA -> GC GATTACA -> AT, TA ATGGATCCG -> GGATCC CCCCCGGGGG -> CCCCCGGGGG ACATATATAGACT -> ATATAT, TATATA ATTCGATCTATGTAAAGAGG -> TCGA, GATC CGCACGTCTACGTACCTACGTAG -> CTACGTAG TCAATGCATGCGGGTCTATATGCAT -> ATGCAT, GCATGC [, ATGCAT] CGCTGAACTTTGCCCGTTGGTAGAACGGACTGATGTGAACGAGTGACCCG -> CG, GC, TA, AT [, GC, CG, CG, CG, CG] CTCGCGTTTGCATAACCGTACGGGCGGAACAGTCGGCGGTGCCTCCCAGG -> CCGTACGG
This is code golf, so the solution in the fewest bytes wins.