Open Reading Frames (오픈 리딩 프레임)

https://rosalind.info/problems/orf/

ROSALIND | Open Reading Frames

Problem

Either strand of a DNA double helix can serve as the coding strand for RNA transcription. Hence, a given DNA string implies six total reading frames, or ways in which the same region of DNA can be translated into amino acids: three reading frames result from reading the string itself, whereas three more result from reading its reverse complement.

An open reading frame (ORF) is one which starts from the start codon and ends by stop codon, without any other stop codons in between. Thus, a candidate protein string is derived by translating an open reading frame into amino acids until a stop codon is reached.

Given: A DNA string ss of length at most 1 kbp in FASTA format.

Return: Every distinct candidate protein string that can be translated from ORFs of ss. Strings can be returned in any order.

Sample Dataset

>Rosalind_99
AGCCATGTAGCTAACTCAGGTTACATGGGGATGACCCCGCGACTTGGATTAGAGTCTCTTTTGGAATAAGCCTGAATGATCCGAGTAGCATCTCAG

Sample Output

MLLGSFRLIPKETLIQVAGSSPCNLS
M
MGMTPRLGLESLLE
MTPRLGLESLLE

 이 문제는 FASTA 형식으로 주어진 하나의 서열이 주어진다. 우리는 그 서열을 이용해서 나올 수 있는 모든 경우의 단백질 서열을 출력해야한다. 여기서 알아야할 점은 단백질 서열은 무조건 처음은 시작 코돈, 끝은 종결 코돈으로 이루어져야 한단 점이다. 그리고 저 가닥을 주형가닥,코딩가닥으로 다 써서 단백질을 만드는 경우까지 따지고, 각각의 가닥에서 ORF(open redaing frame)을 고려하여 단백질을 추정해야 한다. 

 필자는 저 DNA가 주형가닥, 코딩가닥일 때 2가지로 나누고, 그 다음 그 두 가닥에서 ORF를 따져 3가지 경우로 단백질을 번역하니 총 6가지 경우의 단백질 서열이 나온다. ORF를 따질 때 염기서열의 길이를 3의 배수로 맞추거나 염기를 3개씩 추출해서 따져야 한다.

 이 후 각 단백질 서열에서 시작 코돈으로 만들어지는 메싸이오닌(M)과 종결을 뜻하는 *을 각각 리스트에 인덱스를 저장해서, 메싸이오닌과 종결코돈으로 감싸여지는 단백질 서열을 모은다. 이후 이 단백질 서열들 중 중복된 것을 제하고 출력한다.

 필자는 바이오파이썬 모듈내장 함수를 많이 쓴 풀이와 적당히 쓴 풀이 두 가지로 풀었다.

바로 아래 풀이는 내장함수들을 써서 단백질 서열을 먼저 구한다음. M과 *을 따져 구했다. 이 풀이는 간편하긴 하지만 쓸데없이 for문을 많이 돌고 시간복잡도를 더 줄일 요소가 보여 다음 풀이를 썼다.

from Bio import SeqIO

def trimming(dna,strt):#염기서열을 3의 배수로 자르기
    trim_dna=dna[strt:]
    trim_dna=trim_dna[:len(trim_dna)-len(trim_dna)%3]
    return trim_dna

Aseq = SeqIO.parse(r'파일경로','fasta')
dna1 = next(Aseq).seq#1개인걸 아니
dna2=dna1.reverse_complement()#역상보적인 서열

strt_lst=[]
orf_lst=[]

for strt in range(3):#시작을 0,1,2로 해서 orf따지기
    trim_dna1=trimming(dna1,strt)
    trim_dna2=trimming(dna2,strt)

    pep1=trim_dna1.translate()#단백질서열
    pep2=trim_dna2.translate()

    for i in range(len(pep1)):
        if pep1[i]=='M':#시작만 따지기
            strt_lst.append(pep1[i:])
        if pep2[i]=='M':
            strt_lst.append(pep2[i:])

for pp in strt_lst:
    for b in range(len(pp)):
        if pp[b]=='*':#시작된 서열 중 종결 만나면
            orf_lst.append(pp[:b])#*은 안 포함되게
            break#종결되었으니 다음 시작

for final in set(orf_lst):#출력
    print(final)

아래 풀이는 각 서열에서 한 코돈씩 번역하면서 M과 *을 따져 미리 인덱스로 저장해놓아, 인덱스의 숫자만을 따져 만들어질 수 있는 단백질을 저장했다. 이렇게 한다면 번역과 동시에 시작,종결 인덱스를 따질 수 있고, 시작이랑 종결을 짝 지을때 서열의 모든 문자를 훑을 필요가 없어 더 빠르다.

from Bio import SeqIO

def find_orf(dna,strt):
    pep=''#단백질 서열저장
    strt_lst=[]#시작 인덱스
    end_lst=[]#종결 인덱스
    for ind in range(strt,l,3):#스타트부터 3씩 뜀
        if ind+3 > l:#넘어갔을 경우
            continue
        p=dna[ind:ind+3].translate()#한 코돈씩 
        pep = pep+p
        if p=='M':#시작이면
            strt_lst.append(ind//3)#시작의 인덱스
        elif p=='*':#종결이면
            end_lst.append(ind//3)#종결의 인덱스
    for st in strt_lst:#시작 인데스들
        for ed in end_lst:
            if ed>st:#시작과 가장 가깝고 큰 종결인덱스에서
                orf_lst.append(pep[st:ed])#컷
                break#다시 시작으로

    

Aseq = SeqIO.parse(r'파일경로','fasta')
dna1 = next(Aseq).seq
dna2=dna1.reverse_complement()

l=len(dna1)
orf_lst=[]

for strt in range(3):
    find_orf(dna1,strt)
    find_orf(dna2,strt)

for i in set(orf_lst):
    print(i)