Terjemahan RNA ke Protein

18

RNA , seperti DNA, adalah molekul yang ditemukan dalam sel yang mengkode informasi genetik. Ini terdiri dari nukleotida , yang diwakili oleh basa adenin (A), sitosin (C), guanin (G) dan urasil (U). * Kodon adalah urutan dari tiga nukleotida.

Protein adalah molekul besar yang melakukan beragam fungsi, seperti keratin yang ditemukan pada rambut dan kuku serta hemoglobin yang membawa oksigen dalam sel darah. Mereka terbuat dari asam amino , yang dikodekan sebagai kodon dalam molekul RNA. Terkadang kodon yang berbeda dapat dikodekan untuk asam amino yang sama. Setiap asam amino biasanya diwakili oleh satu huruf, misalnya H berarti histidin.

Dengan urutan ACGU, dapatkah Anda menerjemahkannya ke dalam string protein yang sesuai?

* DNA terdiri dari ACGT, di mana T adalah timin. Selama transkripsi DNA ke RNA, timin digantikan oleh urasil.


Memasukkan

Input akan berupa string tunggal yang hanya terdiri dari karakter ACGUdalam huruf besar. Anda dapat menulis fungsi atau program lengkap untuk tantangan ini.

Keluaran

Anda dapat memilih untuk mencetak melalui pencetakan atau pengembalian string (pilihan terakhir hanya tersedia dalam kasus fungsi).

Penerjemahan harus dimulai dengan kodon awal ( AUG, direpresentasikan sebagai M) dan berakhir pada kodon berhenti (salah satu UAA, UAGatau UGA, diwakili sebagai *). Ada empat kasus di mana input mungkin tidak valid:

  • Input tidak dimulai dengan kodon start
  • Input tidak diakhiri dengan kodon stop
  • Panjang input bukan kelipatan 3
  • Input berisi kodon stop di tempat lain selain di akhir

Dalam semua kasus ini, Errorharus dikeluarkan. Perhatikan bahwa, tidak seperti stop kodon, kodon start dapat muncul setelah dimulainya string.

Jika tidak, Anda harus mengubah setiap kodon menjadi asam amino masing-masing melalui tabel kodon RNA berikut :

* 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

... dan tampilkan string yang diterjemahkan.

Contohnya

Kasus tidak valid:

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

Kasus yang valid:

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

Sunting: Menambahkan lebih banyak kasus uji

Mencetak gol

Ini adalah kode golf, jadi kode dalam byte paling sedikit menang.

Catatan: Saya bukan ahli dalam biologi molekuler, jadi jangan ragu untuk mengoreksi saya jika saya salah menyatakan :)

Sp3000
sumber
1
Seorang penerjemah yang tepat harus dapat menemukan bingkai bacaan terbuka dalam string apa pun, bukan hanya yang dimulai dengan AUG!
canadianer
@canadianer Ahaha ya saya awalnya menganggap itu, tapi saya tidak ingin membuat pertanyaan terlalu rumit dengan membawa bingkai bacaan terbuka (atau bahkan menerjemahkan beberapa protein dari satu string) :)
Sp3000
String kosong akan menjadi kasus uji yang berguna, karena akan merusak beberapa pendekatan untuk pengujian yang dimulai dengan urutan Mdan diakhiri dengan *.
Peter Taylor
@PeterTaylor Ditambahkan, bersama dengan beberapa test case pendek lagi :)
Sp3000
1
Jika Anda ingin benar-benar sakit, Anda bisa menggunakan DNA alih-alih RNA, jadi Anda juga harus membaca bingkai.
user137

Jawaban:

6

CJam ( 97 93 92 91 byte)

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

Ini adalah port dari solusi GolfScript saya dengan fungsi hash yang sedikit berubah karena yang mengejutkan saya satu hal yang CJam belum pinjam dari GolfScript adalah memperlakukan string sebagai array bilangan bulat.

6 byte disimpan berkat saran dari Pengoptimal (termasuk dua byte dari sesuatu yang saya pikir saya sudah mencoba dan tidak berfungsi - ya).

Peter Taylor
sumber
1
q"GACU"f#3/{4b"GGEDAAVVRSKNTTMIRRQHPPLLWC*YSSLF"{_s"MW""I*"er}%=}%s_'*/(1<"M"=*Q="Error"@?- 90
Pengoptimal
@Optimizer, beberapa di antaranya sepertinya merupakan peningkatan. Namun, hal itu memberikan error, dan dibandingkan dengan Qbukan [Q]hanya tidak benar.
Peter Taylor
1. Anda belum menyalin kode dengan benar, ketika kode tersebut membentang beberapa baris dalam komentar, kode karakter aneh akan diuraikan pada baris pertama. Anda harus mengetikkan kode sendiri secara manual. 2. Lihat logika, telah diubah untuk benar bekerja, sehingga [Q]untuk Qperubahan adalah benar.
Pengoptimal
@Optimizer, coba test caseAUGUAGUGA
Peter Taylor
1
Ah baiklah. Tetap [Q]->Qa
Pengoptimal
10

JavaScript (ES6) 167 177 karakter dikodekan dalam UTF8 sebagai 167 177 byte

... jadi saya harap semua orang senang.

Edit Bahkan, tidak perlu untuk kasus khusus untuk blok terakhir terlalu pendek. Jika 2 karakter terakhir (atau 1) tidak dipetakan, string hasil tidak diakhiri dengan '*' dan itu tetap memberikan kesalahan.

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'

Dijelaskan

Setiap karakter dalam triplet dapat memiliki 4 nilai, jadi ada tepat 4 ^ 3 == 64 triplet. Fungsi C memetakan setiap triplet ke angka antara 0 dan 63. Tidak diperlukan pemeriksaan kesalahan karena karakter input hanya ACGU.

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

Setiap triplet memetakan asam amino yang diidentifikasi oleh satu arang. Kami dapat menyandikan ini dalam string 64 karakter. Untuk mendapatkan string, mulailah dengan Peta Codon:

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('')

... memperoleh "KNKNTTTTRSRSIIMIQHQHPPPPRRRLLLEDEDAAAAGGGGVVVV * Y * YSSSS * CWCLFLF"

Jadi kita dapat memindai string input dan menggunakan logika fungsi C yang sama untuk mendapatkan kode 0..63, dan dari kode char aminoacid. Fungsi ganti akan membagi string input menjadi 3 blok karakter, akhirnya meninggalkan 1 atau 2 karakter tidak terkelola (yang akan memberikan string hasil yang tidak valid, tidak berakhir pada '*').

Akhirnya, periksa apakah string yang disandikan valid menggunakan regexp: itu harus dimulai dengan 'M', tidak boleh mengandung '*' dan harus diakhiri dengan '*'

Uji di konsol FireBug / FireFox

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

Keluaran

AUGCUAG -> Error
GGGCACUAG -> Error
AUGAACGGA -> Error
AUGUAGUGA -> Error
AAAAAAA -> Error
AUGUUUGUUCCGUCGAAAUACCUAUGAACACGCUAA -> Error
AUGAGGUGUAGCUGA -> MRCS*
AUGCCAGUCGCACGAUUAGUUCACACGCUCUUGUAA -> MPVARLVHTLL*
AUGCUGCGGUCCUCGCAUCUAGCGUUGUGGUUAGGGUGUGUAACUUCGAGAACAGUGAGUCCCGUACCAGGUAGCAUAAUGCGAGCAAUGUCGUACGAUUCAUAG -> MLRSSHLALWLGCVTSRTVSPVPGSIMRAMSYDS*
edc65
sumber
Ide bagus! Hanya berpikir untuk melakukan ini. Anda mengalahkan saya untuk itu!
Pengoptimal
8

C, 190 byte (fungsi)

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 byte (program)

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);}

Disimpan beberapa byte dengan meningkatkan formula hash.

Berikut ini adalah test case yang menyenangkan:

AUGUAUCAUGAGCUCCUUCAGUGGCAAAGACUUGACUGA --> MYHELLQWQRLD* 

Penjelasan

Tiga huruf diubah menjadi nomor basis 4. Setiap huruf di-hash sebagai berikut.

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

Ini memberikan angka dalam kisaran 0..63 . Idenya sekarang adalah menggunakan tabel pencarian yang mirip dengan yang digunakan oleh edc65 dan Pengoptimal. Namun, hash dirancang sedemikian rupa sehingga G dan A saling bersebelahan dan U dan C saling bersebelahan.

Melihat tabel di https://en.wikipedia.org/wiki/Genetic_code#RNA_codon_table , kita melihat bahwa dengan huruf yang dipesan dengan cara ini, umumnya bit terakhir dapat diabaikan. Hanya tabel pencarian 32 karakter yang diperlukan, kecuali dalam dua kasus khusus.

Lihat di bawah dua huruf pertama, dan asam amino yang sesuai (di mana huruf ke-3 adalah G / A, dan di mana huruf ke-3 adalah U / C). Koreksi untuk dua kasus khusus yang tidak sesuai dengan tabel 32 karakter hardcoded.

     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

Kode yang dikomentari

Dalam versi golf, i%3kode berada pada posisi tambahan forbraket, tetapi dipindahkan ke posisi yang lebih mudah dibaca dalam kode komentar.

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
sumber
Kalau saja ada O! Saya menambahkan test case untuk itu MGENETICS*, karena itu adalah kata yang paling tematis yang bisa saya buat: P
Sp3000
6

CJam, 317 121 104 byte

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"?

Ini masih bisa bermain golf lebih lanjut.

Memperbarui mekanisme pemetaan ke yang digunakan dalam jawaban edc65. Meskipun saya datang dengan ini sendiri, dia mengalahkan saya untuk itu :)

UPDATE : Mempersingkat peta tabel kodon dengan mengamati pola di dalamnya.

Cobalah online di sini

Pengoptimal
sumber
Ini rusak jika inputnya adalah string kosong.
Peter Taylor
@PeterTaylor Aturan yang ditambahkan pada saran Anda setelah jawaban diposting;). Saya akan segera memperbarui kode.
Pengoptimal
1
Itu bukan aturan yang ditambahkan, itu adalah ujian yang secara implisit diperlukan oleh aturan.
Peter Taylor
3

GolfScript (103 byte)

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

Demo online (NB tidak termasuk dua kasus uji terbesar karena perlu dijalankan dalam 15 detik).

Pembedahan

Seperti yang ditunjukkan Steve Verrill di kotak pasir, tabel pencarian dapat dikurangi menjadi 32 elemen ditambah dua case khusus. Ternyata kasus khusus keduanya melibatkan karakter ( Mdan Wmasing - masing) yang hanya terjadi sekali, dan dengan pemetaan karakter yang tepat untuk mendasarkan 4 digit dimungkinkan untuk membangun tabel pencarian 64-elemen penuh dari 32 elemen dengan melakukan duplikat -dan- tr:

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

Kemudian setelah kita melakukan decode, validasi memungkinkan banyak pendekatan. Yang terpendek yang saya temukan adalah

.'*'/       # 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
sumber
1 byte. Tantangan diterima!
Pengoptimal
@Optimizer, terjemahan langsung ke CJam akan menghemat beberapa byte karena memiliki banyak built-in yang relevan.
Peter Taylor
Fungsi hashing saya adalah 57 byte, sedangkan milik Anda 52. Jadi saya hanya dapat melihat penghematan paling banyak 5 byte ...
Pengoptimal
Saya senang komentar saya di kotak pasir bermanfaat. Saya berharap mungkin untuk menggunakan fakta yang Mmerupakan salah satu kasus khusus untuk menguji awal yang valid, tetapi tidak berhasil seperti itu. Masih ada 8 pasang huruf identik dalam string itu. Saya bertanya-tanya apakah mereka dapat dikompres sebagai huruf kecil: g-->GG a-->AAdll. Jika dekompresi dapat dicapai di bawah 8 karakter itu akan bermanfaat.
Level River St
1

Python, 473 byte

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
sumber
1

Python 2, 370 358 354 byte

Ini adalah pendekatan yang sangat lurus ke depan tanpa menggunakan kompresi, hanya mencoba mengemas informasi dengan cukup padat:

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')]

Sunting: Memotong beberapa karakter mengikuti saran xnor.

Emil
sumber
Saya yakin Anda bisa menulis slebih pendek secara rekursif s=lambda x:x and[x[:3]]+s(x[3:]).
xnor
@ xnor Hebat, saya tidak memikirkan itu. Ini tidak berfungsi seperti itu, karena pada akhir rekursi itu akan menghasilkan string kosong bukan daftar kosong. Tetapi dengan empat karakter lagi saya bisa membuatnya bekerja. Terima kasih!
Emil
1

Scala (317 karakter)

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}

Fungsi utamanya adalah f. Tentu saja, pilihan yang lebih baik adalah mengembalikan Option[String].

bb94
sumber
0

JavaScript (ES6), 143 byte

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

Cobalah online!

Arnauld
sumber