Como sabrán, en el ADN hay cuatro bases: adenina ( A), citosina ( C), guanina ( G) y timina ( T). Típicamente se Aune Ty se Cune con G, formando los "peldaños" de la estructura de doble hélice del ADN .

Definimos el complemento de una base como la base a la que se une, es decir, el complemento de Ais T, el complemento de Tis A, el complemento de Cis Gy el complemento de Gis C. También podemos definir que el complemento de una cadena de ADN sea la cadena con cada base complementada, por ejemplo, el complemento de GATATCis CTATAG.

Debido a la estructura bicatenaria del ADN, las bases en una cadena son complementarias de las bases en la otra cadena. Sin embargo, el ADN tiene una dirección, y la transcripción del ADN ocurre en direcciones opuestas en las dos cadenas. Por lo tanto, los biólogos moleculares a menudo están interesados ​​en el complemento inverso de una cadena de ADN, literalmente, el reverso del complemento de la cadena.

Para ampliar nuestro ejemplo anterior, el complemento inverso de GATATCes CTATAGhacia atrás, entonces GATATC. Como habrás notado, en este ejemplo el complemento inverso es igual a la cadena original: llamamos a esta cadena un palíndromo inverso . *

Dada una cadena de ADN, ¿puedes encontrar la subcadena más larga que es un palíndromo inverso?

^{* Uso el término "palíndromo inverso", tomado de Rosalind , para diferenciarlo del significado habitual de palíndromo.}

Entrada

La entrada será una sola cadena que constará solo de los caracteres ACGTen mayúscula. Puede escribir una función o un programa completo para este desafío.

Salida

Puede elegir imprimir mediante impresión o devolución (la última opción solo está disponible en el caso de una función).

Su programa debería generar la subcadena palindrómica inversa más larga de la cadena de entrada, si hay una solución única. Si existen varias soluciones, puede generar cualquiera de ellas o todas (su elección). Los duplicados están bien si elige generarlos todos.

Se garantiza que la entrada tendrá una solución de al menos longitud 2.

Ejemplo trabajado

ATGGATCCG -> GGATCC

El complemento inverso de GGATCCes sí mismo ( GGATCC --complement--> CCTAGG --reverse--> GGATCC), por lo que GGATCCes un palíndromo inverso. GATCTambién es un palíndomo inverso, pero no es el más largo.

Casos de prueba

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

Puntuación

Este es el código de golf, por lo que la solución en la menor cantidad de bytes gana.

Pyth, 37 36 28 24 bytes

ef&}TzqmaCd6T_mx4aCk6Tyz

Combinando los consejos de FryAmTheEggman y el truco de verificación del palíndromo inverso de Peter, esta es una versión súper corta.

Sin embargo, esto solo funciona con Pyth 3.0.1, que puede descargar desde este enlace y ejecutar como

python3 pyth.py -c "ef&}TzqmaCd6T_mx4aCk6Tyz" <<< "ATTCGATCTATGTAAAGAGG"

(solo Linux bash. En Windows, presione Entrar en lugar de <<< y luego escriba la entrada)

Esta es mi presentación anterior: solución de 28 bytes

J"ACGT"ef&}TzqTjk_m@_JxJdTyz

Gracias a FryAmTheEggman por esta versión. Éste crea todos los subconjuntos posibles de la cadena de ADN de entrada, filtra los subconjuntos con la condición de que el subconjunto sea una subcadena de entrada y el reverso de la transformación sea igual al subconjunto mismo.

Debido a toda la posible creación de subconjuntos, esto ocupa aún más memoria que la respuesta de Peter.

Esta es mi primera presentación: solución de 36 bytes.

J"ACGT"eolNfqTjk_m@_JxJdTm:zhkek^Uz2

Esta es la traducción exacta de mi respuesta CJam . Esperaba que esto fuera mucho más pequeño, pero resulta que la falta de método de traducción lo hizo de un tamaño casi similar (aunque 2 bytes más pequeño)

Pruébalo en línea aquí

GolfScript ( 35 34 bytes)

]{{..(;\);}%)}do{{6&}%.{4^}%-1%=}?

Para fines de prueba, es posible que desee utilizar

]{{..(;\);}%.&)}do{{6&}%.{4^}%-1%=}?

que agrega una .&para reducir el esfuerzo duplicado.

Disección

]{         # Gather string into an array and do-while...
  {        #   Map over each string in the array
    ..     #     Make a couple of copies of the string
    (;     #     Remove the first character from one of them
    \);    #     Remove the last character from the other
  }%
  )        #   Extract the last string from the array
}do        # Loop until that last string is ''
           # Because of the duplication we now have an array containing every substring
           # of the original string, and if we filter to the first occurrence of each
           # string then they're in descending order of length
{          # Find the first element in the string satisfying the condition...
  {6&}%    #   Map each character in the string to its bitwise & with 6
  .{4^}%   #   Duplicate, and map each to its bitwise ^ with 4
           #   This serves to test for A <-> T, C <-> G
  -1%=     #   Reverse and test for equality
}?

CJam, 39 38 bytes

Estoy seguro de que esto se puede jugar más golf ...

q:Q,,_m*{~Q<>}%{,~}${_"ACGT"_W%erW%=}=

Toma la cadena de ADN de STDIN y envía el ADN palindrómico inverso más largo a STDOUT

Pruébalo en línea aquí

(Explicación pronto) (Guardado 1 byte gracias a Peter)

Python 3, 125 caracteres

S=input()
l=[]
while S:
 s=_,*S=S
 while s:l+=[s]*all(x+y in"ATA CGC"for x,y in zip(s,s[::-1]));*s,_=s
print(*max(l,key=len))

Mira ma, sin indexación! (Bueno, excepto para invertir la cadena, eso no cuenta).

La iteración sobre las subcadenas se realiza quitando caracteres del frente y del final mediante la asignación de estrellas . El bucle externo elimina los caracteres para el inicio Sy, para cada uno de estos sufijos, srecorre todos los prefijos del mismo, probándolos uno por uno.

La prueba para palíndromo inverso se realiza mediante el código

all(x+y in"ATA CGC"for x,y in zip(s,s[::-1]))

que verifica que cada símbolo y su contraparte de cadena inversa sean uno de "AT", "TA", "CG" y "GC". También encontré que una solución basada en conjuntos tiene un carácter más corto, pero pierde dos caracteres al requerir parens externos cuando se usa.

set(zip(s,s[::-1]))<=set(zip("ACTG","TGAC"))

Esto todavía parece que se puede acortar.

Finalmente, se imprime el palíndromo más largo.

print(*max(l,key=len))

Espero que las salidas separadas por espacios estén bien. Si una lista también está bien, la estrella podría eliminarse. Intenté seguir el máximo de ejecución en el bucle, así como incluir los bucles internos en una lista de comprensión para poder tomar el máximo directamente sin construir l, y ambos resultaron un poco más largos. Pero, fue lo suficientemente cerca como para que sea difícil saber qué enfoque es realmente el mejor.

J (45)

{.@(\:#&.>)@,@(('ACGT'&(|.@]-:[{~3-i.)#<)\\.)

Esta es una función que toma una cadena:

   {.@(\:#&.>)@,@(('ACGT'&(|.@]-:[{~3-i.)#<)\\.) 'ATGGATCCG'
┌──────┐
│GGATCC│
└──────┘

Explicación:

{.@(\:#&.>)@,@(('ACGT'&(|.@]-:[{~3-i.)#<)\\.) 

              (                          \\.)  for each prefix of each suffix
               (                      #<)      include the argument if,
                        |.@]                      its reverse
                            -:                    is equal to
                'ACGT'&(      [{~3-i.)            the complement
            ,@                                 ravel
   (\:#&.>)@                                   sort by length of item
{.@                                            take the first one   

Perl - 59 bytes

#!perl -p
$_=$_[~!map$_[length]=$_,/((.)(?R)?(??{'$Q5'^$+.-$+}))/gi]

Contando el shebang como uno, la entrada se toma de STDIN.

Uso de la muestra:

$ echo CTCGCGTTTGCATAACCGTACGGGCGGAACAGTCGGCGGTGCCTCCCAGG | perl dna.pl
CCGTACGG

Python 2 - 177 bytes

s=raw_input()
r,l,o=range,len(s),[]
for a in[s[i:j+1]for i in r(l)for j in r(i,l)]:q=['TC GA'.index(c)-2for c in a];o+=[a if[-n for n in q][::-1]==q else'']
print max(o,key=len)

Fuerza bruta simple. La verificación real "palindrómica inversa" es la única parte interesante. Aquí está escrito de manera más legible:

check = ['TC GA'.index(c)-2 for c in substring]
if [-n for n in check][::-1] == check:
    # substring is reverse palindromic

Hago eso en cada posible subcadena y las pongo en una lista si es verdad. Si es falso, pongo una cadena vacía en su lugar. Cuando se realizan todas las comprobaciones, saco el elemento más largo de la lista. Utilicé una cadena vacía porque ahorra bytes al no poner nada, pero también significa que el programa no se ahogará si no hay solución. Produce una línea vacía y sale con gracia.