DNA 번역

디옥시리보핵산(DNA)은 뉴클레오타이드 염기들이 짝을 이루어 이중 나선 구조를 만드는 서열이다. 여러 생화학 과정을 거쳐 생물의 DNA에 담긴 염기 서열은 생명 활동에 필요한 단백질로 번역된다. 이 문제의 목표는 DNA 가닥을 입력받아 그로부터 만들어지는 단백질이 있다면 무엇인지 출력하는 프로그램을 작성하는 것이다.

DNA를 이루는 네 가지 염기는 아데닌, 사이토신, 구아닌, 타이민이며 각각 A, C, G, T로 쓴다. 이 염기들이 사슬처럼 연결되어 DNA의 한쪽 가닥을 이룬다. 반대쪽 가닥도 비슷한 사슬이지만 각 염기가 상보 염기로 바뀐다. A와 T가 서로 상보이고, C와 G가 서로 상보이다. 두 반쪽 가닥은 이 상보 염기쌍으로 결합해 하나의 이중 가닥 DNA를 이룬다.

보통 DNA 가닥은 주 가닥(primary strand)의 염기만 적어 나타내며, 상보 가닥은 각 염기의 상보 염기를 적어 얻는다. 예를 들어 가닥 TACTCGTAATTCACT의 상보 가닥은 ATGAGCATTAAGTGA이다. (A는 항상 T와, C는 항상 G와 짝을 이룬다.)

주 가닥으로부터 전사(transcription) 과정을 통해 전령 RNA(mRNA)가 만들어진다. 전사된 mRNA는 상보 DNA 가닥과 같되, 타이민(T)이 유라실(U)로 바뀐다는 점만 다르다. 예를 들어 위 가닥의 mRNA는 AUGAGCAUUAAGUGA이다.

어떤 단백질이 합성될지는 mRNA의 염기 서열이 결정한다. mRNA는 정확히 세 염기로 이루어진 코돈(codon)이 이어진 것으로 본다. 코돈 AUG는 단백질 서열의 시작을 나타내고, 코돈 UAA, UAG, UGA 중 하나는 끝을 나타낸다. 시작 코돈과 종료 코돈 사이에 있는 하나 이상의 코돈이 합성될 아미노산 서열이 된다. 예를 들어 AGC는 세린(Ser), AUU는 아이소류신(Ile), AAG는 라이신(Lys)에 대응하므로 위 mRNA가 만드는 단백질은 Ser-Ile-Lys이다.

코돈을 아미노산으로 번역하는 전체 유전 부호는 아래 표와 같다. (아미노산 약자만 표시했으며, Stop은 종료 코돈을 뜻한다.) 이미 시작 코돈으로 지정된 AUG는 메싸이오닌(Met)에도 대응한다. 즉 mRNA에서 처음 나오는 AUG는 시작 코돈이지만, 그 뒤에 나오는 AUG는 일반적인 Met로 번역된다. 표에서 맨 왼쪽 열은 코돈의 첫째 염기, U·C·A·G로 표시된 가운데 네 열은 둘째 염기, 맨 오른쪽 열은 셋째 염기를 나타낸다.

입력은 DNA 가닥들로 이루어지며, 한 줄에 한 가닥씩 주어지고, 별표(*) 하나만 있는 줄로 끝난다. 각 가닥에 대해 그것이 만들어 내는 단백질이 있다면 무엇인지 판별해 출력해야 한다.

주어진 가닥은 주 가닥일 수도, 상보 가닥일 수도 있으며, 정방향 또는 역방향으로 적혀 있을 수 있다. 시작 서열과 종료 서열이 반드시 가닥의 양 끝에 오는 것은 아니다. 따라서 각 가닥을 네 가지 해석 — 적힌 그대로, 뒤집은 것, 상보로 바꾼 것, 상보로 바꾼 뒤 뒤집은 것 — 으로 살펴보고, 각 경우마다 T를 U로 바꾸어 후보 mRNA를 얻어야 한다. 예를 들어 ATACTCGTAATTCACTCC, CCTCACTTAATGCTCATA, TATGAGCATTAAGTGAGG, GGAGTGAATTACGAGTAT 중 어느 것이든 단백질 Ser-Ile-Lys를 만든다.

모든 가닥은 대문자 DNA 염기 A, C, G, T로만 이루어진다. 각 줄의 길이는 255자를 넘지 않으며, 입력에 빈 줄이나 공백은 없다.

각 입력 가닥에 대해, 그 가닥이 부호화하는 단백질을 아미노산 약자를 하이픈(-)으로 이은 형태로 한 줄에 출력한다. (예: Ser-Ile-Lys)

후보 mRNA를 읽을 때는 왼쪽에서 오른쪽으로 훑어 처음 나오는 시작 코돈 AUG를 찾는다. 그 AUG 바로 뒤부터 세 염기씩 코돈을 차례로 읽어, 처음 만나는 종료 코돈(UAA, UAG, UGA)까지 진행한다. 그 사이 코돈들이 순서대로 단백질의 아미노산이 된다. 유효한 단백질은 아미노산을 적어도 하나 포함해야 하며 반드시 종료 코돈에 도달해야 한다.

어떤 가닥은 올바른 DNA이지만 유효한 단백질을 만들지 못한다. 한 가닥의 네 해석 어느 것도 유효한 단백질을 만들지 못하면 *** No translatable DNA found *** 를 출력한다.

네 해석 중 둘 이상이 유효한 단백질을 만든다면, 그 단백질 문자열들을 일반 텍스트(ASCII 순서)로 비교해 사전순으로 가장 큰 것을 출력한다. 이렇게 하면 각 가닥의 답이 유일해진다.