Traducción de ARN a Proteína

18

El ARN , como el ADN, es una molécula que se encuentra en las células que codifican la información genética. Consiste en nucleótidos , que están representados por las bases adenina (A), citosina (C), guanina (G) y uracilo (U). * Un codón es una secuencia de tres nucleótidos.

Las proteínas son moléculas grandes que realizan una amplia gama de funciones, como la queratina que se encuentra en el cabello y las uñas y la hemoglobina que transporta oxígeno en las células sanguíneas. Están formados por aminoácidos , que están codificados como codones en las moléculas de ARN. A veces, codones diferentes pueden codificar para el mismo aminoácido. Cada aminoácido está comúnmente representado por una sola letra, por ejemplo, H significa histidina.

Dada una secuencia de ACGU, ¿puedes traducirla a la cadena de proteínas correspondiente?

* El ADN consiste en ACGT, donde la T es timina. Durante la transcripción de ADN a ARN, la timina es reemplazada por uracilo.


Entrada

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

Salida

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

La traducción debe comenzar en un codón de inicio ( AUG, representado como M) y finalizar en un codón de detención (uno de UAA, UAGo UGA, representado como *). Hay cuatro casos donde la entrada puede ser inválida:

  • La entrada no comienza con un codón de inicio
  • La entrada no termina con un codón de parada
  • La longitud de la entrada no es múltiplo de 3
  • La entrada contiene un codón de parada en otro lugar que no sea al final

En todos estos casos, se Errordebe generar. Tenga en cuenta que, a diferencia de los codones de detención, los codones de inicio pueden aparecer después del inicio de la cadena.

De lo contrario, debe convertir cada codón en su aminoácido respectivo a través de la siguiente tabla de codones de ARN :

* UAA UAG UGA
A GCU GCC GCA GCG
C UGU UGC
D GAU GAC
E GAA GAG
F UUU UUC
G GGU GGC GGA GGG
H CAU CAC
I AUU AUC AUA
K AAA AAG
L UUA UUG CUU CUC CUA CUG
M AUG
N AAU AAC
P CCU CCC CCA CCG
Q CAA CAG
R CGU CGC CGA CGG AGA AGG
S UCU UCC UCA UCG AGU AGC
T ACU ACC ACA ACG
V GUU GUC GUA GUG
W UGG
Y UAU UAC

... y genera la cadena traducida.

Ejemplos

Casos inválidos:

<empty string> -> Error
AUG -> Error
UAA -> Error
AUGCUAG -> Error
AAAAAAA -> Error
GGGCACUAG -> Error
AUGAACGGA -> Error
AUGUAGUGA -> Error
AUGUUUGUUCCGUCGAAAUACCUAUGAACACGCUAA -> Error

Casos válidos:

AUGUGA -> M*
AUGAGGUGUAGCUGA -> MRCS*
AUGGGUGAGAAUGAAACGAUUUGCAGUUAA -> MGENETICS*
AUGCCAGUCGCACGAUUAGUUCACACGCUCUUGUAA -> MPVARLVHTLL*
AUGCUGCGGUCCUCGCAUCUAGCGUUGUGGUUAGGGUGUGUAACUUCGAGAACAGUGAGUCCCGUACCAGGUAGCAUAAUGCGAGCAAUGUCGUACGAUUCAUAG -> MLRSSHLALWLGCVTSRTVSPVPGSIMRAMSYDS*
AUGAAAAACAAGAAUACAACCACGACUAGAAGCAGGAGUAUAAUCAUGAUUCAACACCAGCAUCCACCCCCGCCUCGACGCCGGCGUCUACUCCUGCUUGAAGACGAGGAUGCAGCCGCGGCUGGAGGCGGGGGUGUAGUCGUGGUUUACUAUUCAUCCUCGUCUUGCUGGUGUUUAUUCUUGUUUUAA -> MKNKNTTTTRSRSIIMIQHQHPPPPRRRRLLLLEDEDAAAAGGGGVVVVYYSSSSCWCLFLF*

Editar: se agregaron más casos de prueba

Puntuación

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

Nota: No soy un experto en biología molecular, así que siéntete libre de corregirme si he expresado algo incorrecto :)

Sp3000
fuente
1
¡Un traductor adecuado debería poder encontrar el marco de lectura abierto en cualquier cadena, no solo en aquellas que comienzan con AGO!
canadiense
@canadianer Ahaha, sí, inicialmente lo consideré, pero no quería complicar la pregunta al incluir marcos de lectura abiertos (o incluso traducir múltiples proteínas de una sola cadena) :)
Sp3000
La cadena vacía sería un caso de prueba útil, porque romperá algunos enfoques para probar que la secuencia decodificada comienza My termina con *.
Peter Taylor
@PeterTaylor Agregado, junto con algunos casos de prueba más cortos :)
Sp3000
1
Si quisieras ser un verdadero dolor, podrías usar ADN en lugar de ARN, por lo que también tienes marcos de lectura hacia atrás.
usuario137

Respuestas:

6

CJam ( 97 93 92 91 bytes)

q"GACU"f#3/{4b"GGEDAAVVRSKNTTMIRRQHPPLLWC*YSSLF"{_s"MW""I*"er}%=}%s_'*/(1<"M"=*Qa=\"Error"?

Este es un puerto de mi solución GolfScript con una función hash ligeramente modificada porque, para mi sorpresa, una cosa que CJam no ha tomado prestada de GolfScript es tratar las cadenas como conjuntos de enteros.

6 bytes guardados gracias a las sugerencias de Optimizer (incluidos dos bytes de algo que pensé que había intentado y no funcionó, eh).

Peter Taylor
fuente
1
q"GACU"f#3/{4b"GGEDAAVVRSKNTTMIRRQHPPLLWC*YSSLF"{_s"MW""I*"er}%=}%s_'*/(1<"M"=*Q="Error"@?- 90
Optimizer
@Optimizer, algo de eso parece ser una mejora. Sin embargo, da un error de tiempo de ejecución, y la comparación en Qlugar de [Q]simplemente es incorrecta.
Peter Taylor
1. no ha copiado el código correctamente, cuando el código abarca varias líneas en los comentarios, obtiene un carácter unicode extraño en el salto de línea. Tendrá que escribir manualmente el código urself entonces. 2. Ver la lógica, se ha alterado para correctamente el trabajo, por lo [Q]que Qel cambio es correcto.
Optimizador
@Optimizer, prueba el caso de pruebaAUGUAGUGA
Peter Taylor
1
Ah bien. Todavía [Q]->Qa
Optimizer
10

JavaScript (ES6) 167 177 caracteres codificados en UTF8 como 167 177 bytes

... así que espero que todos estén felices.

Editar De hecho, no es necesario un caso especial para el último bloque demasiado corto. Si los últimos 2 (o 1) caracteres no están asignados, la cadena de resultados no termina con '*' y eso da error de todos modos.

F=s=>/^M[^*]*\*$/.test(s=s.replace(/.../g,x=>
"KNKNTTTTRSRSIIMIQHQHPPPPRRRRLLLLEDEDAAAAGGGGVVVV*Y*YSSSS*CWCLFLF"
[[for(c of(r=0,x))r=r*4+"ACGU".search(c)]|r]))?s:'Error'

Explicado

Cada char en un triplete puede tener 4 valores, por lo que hay exactamente 4 ^ 3 == 64 tripletas. La función C asigna cada triplete a un número entre 0 y 63. No se necesita verificación de errores ya que los caracteres de entrada son solo ACGU.

C=s=>[for(c of(r=0,s))r=r*4+"ACGU".search(c)]|r

Cada triplete se asigna a un aminoácido identificado por un único carácter. Podemos codificar esto en una cadena de 64 caracteres. Para obtener la cadena, comience con el Mapa de codones:

zz=["* UAA UAG UGA","A GCU GCC GCA GCG","C UGU UGC","D GAU GAC","E GAA GAG"
,"F UUU UUC","G GGU GGC GGA GGG","H CAU CAC","I AUU AUC AUA","K AAA AAG"
,"L UUA UUG CUU CUC CUA CUG","M AUG","N AAU AAC","P CCU CCC CCA CCG","Q CAA CAG"
,"R CGU CGC CGA CGG AGA AGG","S UCU UCC UCA UCG AGU AGC","T ACU ACC ACA ACG"
,"V GUU GUC GUA GUG","W UGG","Y UAU UAC"]
a=[],zz.map(v=>v.slice(2).split(' ').map(x=>a[C(x)]=v[0])),a.join('')

... obteniendo "KNKNTTTTRSRSIIMIQHQHPPPPRRRRLLLLEDEDAAAAGGGGVVVV * Y * YSSSS * CWCLFLF"

Entonces podemos escanear la cadena de entrada y usar la misma lógica de la función C para obtener el código 0..63, y del código el aminoácido char. La función de reemplazo dividirá la cadena de entrada en bloques de 3 caracteres, dejando eventualmente 1 o 2 caracteres no administrados (eso dará una cadena de resultado no válida, que no terminará en '*').

Por último, verifique si la cadena codificada es válida utilizando una expresión regular: debe comenzar con 'M', no debe contener '*' y debe terminar con '*'

Prueba en la consola FireBug / FireFox

;['AUGCUAG','GGGCACUAG','AUGAACGGA','AUGUAGUGA','AAAAAAA',
'AUGUUUGUUCCGUCGAAAUACCUAUGAACACGCUAA',
'AUGAGGUGUAGCUGA','AUGCCAGUCGCACGAUUAGUUCACACGCUCUUGUAA',
'AUGCUGCGGUCCUCGCAUCUAGCGUUGUGGUUAGGGUGUGUAACUUCGAGAACAGUGAGUCCCGUACCAGGUAGCAUAAUGCGAGCAAUGUCGUACGAUUCAUAG']
.forEach(c=>console.log(c,'->',F(c)))

Salida

AUGCUAG -> Error
GGGCACUAG -> Error
AUGAACGGA -> Error
AUGUAGUGA -> Error
AAAAAAA -> Error
AUGUUUGUUCCGUCGAAAUACCUAUGAACACGCUAA -> Error
AUGAGGUGUAGCUGA -> MRCS*
AUGCCAGUCGCACGAUUAGUUCACACGCUCUUGUAA -> MPVARLVHTLL*
AUGCUGCGGUCCUCGCAUCUAGCGUUGUGGUUAGGGUGUGUAACUUCGAGAACAGUGAGUCCCGUACCAGGUAGCAUAAUGCGAGCAAUGUCGUACGAUUCAUAG -> MLRSSHLALWLGCVTSRTVSPVPGSIMRAMSYDS*
edc65
fuente
¡Buena idea! Estaba pensando en hacer esto. ¡Me ganaste!
Optimizador
8

C, 190 bytes (función)

f(char*x){int a=0,i=0,j=0,s=1;for(;x[i];i%3||(s-=(x[j++]=a-37?a-9?"KNRSIITTEDGGVVAA*Y*CLFSSQHRRLLPP"[a/2]:77:87)==42,x[j]=a=0))a=a*4+(-x[i++]/2&3);puts(*x-77||i%3||s||x[j-1]-42?"Error":x);}

199 194 bytes (programa)

a,i,j;char x[999];main(s){for(gets(x);x[i];i%3||(s-=(x[j++]=a-37?a-9?"KNRSIITTEDGGVVAA*Y*CLFSSQHRRLLPP"[a/2]:77:87)==42,x[j]=a=0))a=a*4+(-x[i++]/2&3);puts((*x-77||i%3||s||x[j-1]-42)?"Error":x);}

Ahorró algunos bytes al mejorar la fórmula hash.

Aquí hay un divertido caso de prueba:

AUGUAUCAUGAGCUCCUUCAGUGGCAAAGACUUGACUGA --> MYHELLQWQRLD* 

Explicación

El triplete de letras se convierte en un número base 4. Cada letra se codifica de la siguiente manera.

x[i]       ASCII code       Hashed to (-x[i]/2&3) 
A        64+ 1  1000001            00   
G        64+ 7  1000111            01
U        64+21  1010101            10   
C        64+ 3  1000011            11

Esto le da un número en el rango 0..63 . La idea ahora es utilizar una tabla de búsqueda similar a las utilizadas por edc65 y Optimizer. Sin embargo, el hash está diseñado para que G y A estén uno al lado del otro y U y C estén uno al lado del otro.

Mirando la tabla en https://en.wikipedia.org/wiki/Genetic_code#RNA_codon_table , vemos que con las letras ordenadas de esta manera, generalmente se puede ignorar el último bit. Solo se necesita una tabla de búsqueda de 32 caracteres, excepto en dos casos especiales.

Vea a continuación las dos primeras letras y los aminoácidos correspondientes (donde la tercera letra es G / A y la tercera letra es U / C). Las correcciones para los dos casos especiales que no se ajustan a la tabla de 32 caracteres están codificadas.

     A/G U/C          A/G U/C            A/G U/C         A/G U/C  
AAX> K   N       AGX> R   S         AUX> I   I      ACX> T   T
GAX> E   D       GGX> G   G         GUX> V   V      GCX> A   A
UAX> *   Y       UGX> *   C         UUX> L   F      UCX> S   S
CAX> Q   H       CGX> R   R         CUX> L   L      CCX> P   P

Corrections for special cases (where last bit cannot be ignored)
AUG 001001=9 -->  M
UGG 100101=37-->  W

Código comentado

En la versión de golf, el i%3código está en la posición de incremento del forsoporte, pero se mueve a una posición más legible en el código comentado.

a,i,j;char x[999];                                                             //Array x used for storing both input and output. i=input pointer, j=output pointer.
main(s){                                                                       //s is commandline string count. if no arguments, will be set to zero. Will be used to count stops.
  for(gets(x);x[i];)                                                           //Get a string, loop until end of string (zero byte) found
    a=a*4+(-x[i++]/2&3),                                                       //Hash character x[i] to a number 0-3. leftshift any value already in a and add the new value. Increment i.
    i%3||(                                                                     //if i divisible by 3,
      s-=(x[j++]=a-37?a-9?"KNRSIITTEDGGVVAA*Y*CLFSSQHRRLLPP"[a/2]:77:87)==42,  //lookup the correct value in the table. for special cases a=24 and a=32 map to 'M' and 'W' (ASCII 77 and 87). If character is '*' (ASCII42) decrement s.   
      x[j]=a=0                                                                 //reset a to 0. clear x[j] to terminate output string.                                                     
    );   
  puts((*x-77||i%3||s||x[j-1]-42)?"Error":x);                                  //if first character not M or i not divisible by 3 or number of stops not 1 or last character not * print "Error" else print amino acid chain.
}
Level River St
fuente
¡Ojalá hubiera un O! Sin MGENETICS*embargo, agregué un caso de prueba , porque es la palabra más temática que podría hacer: P
Sp3000
6

CJAM, 317 121 104 bytes

q3/{{"ACGU"#}%4b"KN T RS IIMI QH P R L ED A G V *Y S *CWC LF"S/{_,4\/*}%s=}%_('M=\)'*=\'*/,1=**\"Error"?

Esto todavía se puede jugar más al golf.

Se actualizó el mecanismo de mapeo al utilizado en la respuesta de edc65. Aunque se me ocurrió esto por mi cuenta, él me ganó :)

ACTUALIZACIÓN : acortó el mapa de la tabla de codones al observar el patrón en él.

Pruébalo en línea aquí

Optimizador
fuente
Esto se rompe si la entrada es la cadena vacía.
Peter Taylor
@PeterTaylor Una regla que se agregó a su sugerencia después de que se publicó la respuesta;). Actualizaré el código pronto.
Optimizador
1
No se agregó una regla, se trataba de un caso de prueba que las reglas ya requerían implícitamente.
Peter Taylor
3

GolfScript (103 bytes)

{)7&2/}%3/{4base'GGEDAAVVRSKNTTMIRRQHPPLLWC*YSSLF'{..'MW'?'I*'@),+=}%=}%''+.'*'/(1<'M'=*['']=*'Error'or

Demostración en línea (NB no incluye los dos casos de prueba más grandes porque debe ejecutarse en 15 segundos).

Disección

Como Steve Verrill señaló en el sandbox, la tabla de búsqueda se puede reducir a 32 elementos más dos casos especiales. Resulta que los casos especiales involucran caracteres ( My Wrespectivamente) que solo ocurren una vez, y con el mapeo correcto de los caracteres a 4 dígitos base es posible construir la tabla de búsqueda completa de 64 elementos a partir de los 32 elementos haciendo un duplicado -y- tr:

'GGEDAAVVRSKNTTMIRRQHPPLLWC*YSSLF'  # 32-element lookup table
{                                   # Map over the 32 elements...
  .                                 #   Duplicate the element
  .'MW'?'I*'@),+=                   #   Apply tr/MW/I*/ to the duplicate
}%

Luego, una vez que hemos hecho la decodificación, la validación permite muchos enfoques. Lo más corto que he encontrado es

.'*'/       # Duplicate and split the copy around '*' retaining empty strings
(1<'M'=*    # Pull out the first string from the split (guarantee to exist even if input is
            # the empty string); if it starts with 'M' leave the rest of the split intact;
            # otherwise reduce it to the empty array
['']=       # Check whether we have ['']. If so, the split produced [prefix ''] where
            # prefix begins with 'M'. Otherwise we want an error.
*           # If we have an error case, reduce the original decoded string to ''
'Error'or   # Standard fallback mechanism
Peter Taylor
fuente
1 byte ¡Desafío aceptado!
Optimizador
@Optimizer, una traducción directa a CJam ahorrará unos pocos bytes porque tiene muchas funciones integradas relevantes.
Peter Taylor
Mi función de hashing es de 57 bytes, mientras que la tuya es de 52. Así que solo puedo ver como máximo 5 bytes de ahorro ...
Optimizer
Me alegra que mi comentario en el sandbox haya sido útil. Esperaba que fuera posible utilizar el hecho de que Mera uno de los casos especiales para probar un comienzo válido, pero no ha funcionado de esa manera. Todavía hay 8 pares de letras idénticas en esa cadena. Me pregunto si se pueden comprimir como letras minúsculas: g-->GG a-->AAetc. Si la descompresión se puede lograr en menos de 8 caracteres, valdría la pena.
Level River St
1

Python, 473 bytes

t={'U(A[AG]|GA)':'*','GC.':'A','UG[UC]':'C','GA[UC]':'D','GA[AG]':'E','UU[UC]':'F','GG.':'G','CA[UC]':'H','AU[UCA]':'I','AA[AG]':'K','(UU[AG]|CU.)':'L','AUG':'M','AA[UC]':'N','CC.':'P','CA[AG]':'Q','(CG.|AG[AG])':'R','(UC.|AG[UC])':'S','AC.':'T','GU.':'V','UGG':'W','UA[UC]':'Y'}
import re
i=raw_input()
a=''
for x in[i[y:y+3]for y in range(0,len(i),3)]:
 a+=[t[u]for u in t.keys()if re.match(u, x)][0]
print["Error",a][all((a[0]+a[-1]=="M*",len(i)%3==0,not"*"in a[1:-1]))]
James Williams
fuente
1

Python 2, 370 358 354 bytes

Este es un enfoque muy sencillo que no utiliza compresión, solo trata de empaquetar la información con bastante densidad:

s=lambda x:x and[x[:3]]+s(x[3:])or[]
def f(I):O=''.join(d*any(0==x.find(p)for p in e)for x in s(I)for d,e in zip('*ACDEFGHIKLMNPQRSTVWY',map(s,'UAAUAGUGA,GC,UGUUGC,GAUGAC,GAAGAG,UUUUUC,GG,CAUCAC,AUUAUCAUA,AAAAAG,UUAUUGCU,AUG,AAUAAC,CC,CAACAG,AGAAGGCG,AGUAGCUC,AC,GU,UGG,UAUUAC'.split(','))));return['Error',O][len(I)%3==0==len(O)-O.find('*')-(O[0]=='M')]

Editar: Afeitado algunos caracteres siguiendo la sugerencia de xnor.

Emil
fuente
Creo que puedes escribir smás corto de forma recursiva como s=lambda x:x and[x[:3]]+s(x[3:]).
xnor
@xnor Genial, no pensé en eso. No funciona así, porque al final de la recursión generará una cadena vacía, no una lista vacía. Pero con cuatro personajes más puedo hacer que funcione. ¡Gracias!
Emil
1

Scala (317 caracteres)

def g(c:Char)="ACGU"indexOf c;def h(s:String,i:Int)=g(s(i))*16+g(s(i+1))*4+g(s(i+2));def p(a:Int)=a!=48&&a!=50&&a!=56;def f(s:String)=if(s.length%3!=0||h(s,0)!=14||p(h(s,s.length-3)))"Error"else{var r="";for(i<-0 to s.length-3 by 3)r+="KNKNTTTTRSRSIIMIQHQHPPPPRRRRLLLLEDEDAAAAGGGGVVVV*Y*YSSSS*CWCLFLF"charAt h(s,i);r}

La función principal es f. Por supuesto, una mejor opción sería devolver un Option[String].

bb94
fuente
0

JavaScript (ES6), 143 bytes

s=>/^M\w*\*$/.test(s=s.replace(/.../g,c=>"PVLVLHDVLGRGRAPGR*KYNVL*KTSTSGRTSILIFYNMLR*SCTSRWEQDHIFEQPAPASC.A"[parseInt(c,36)%128%65]))?s:'Error'

Pruébalo en línea!

Arnauld
fuente