RNA Splicing(RNA 스플라이싱)

https://rosalind.info/problems/splc/

ROSALIND | RNA Splicing

Problem

After identifying the exons and introns of an RNA string, we only need to delete the introns and concatenate the exons to form a new string ready for translation.

Given: A DNA string ss (of length at most 1 kbp) and a collection of substrings of ss acting as introns. All strings are given in FASTA format.

Return: A protein string resulting from transcribing and translating the exons of ss. (Note: Only one solution will exist for the dataset provided.)

Sample Dataset

>Rosalind_10
ATGGTCTACATAGCTGACAAACAGCACGTAGCAATCGGTCGAATCTCGAGAGGCATATGGTCACATGATCGGTCGAGCGTGTTTCAAAGTTTGCGCCTAG
>Rosalind_12
ATCGGTCGAA
>Rosalind_15
ATCGGTCGAGCGTGT

Sample Output

MVYIADKQHVASREAYGHMFKVCA

 

 이 문제는 여러 개의 서열이 들어있는 fasta 파일을 주고 이 파일의 첫 번째가 스플라이싱 해야할 RNA이고 그 이후는 인트론의 서열들이 주어진다. 즉 첫 번째 RNA 중 뒤의 RNA 서열들을 제거해야 한다. 

 필자는 이 문제를 두 가지 방식을 이용하여 풀었다. 하나는 파이썬의 내장모듈들을 사용해서 푸는 방식. 다른 하나는 KMP 알고리즘을 이용하여 푸는 방식이다. 실상 내장모듈이 그러한 알고리즘을 이용하니 어떻게 푸나 똑같다.

 파이썬의 내장함수 문자열.replace()를 사용하면 손 쉽게 문자열 안의 타겟 문자열을 다른 걸로 바꿀 수 있다.

from Bio import SeqIO

subseq_lst=[]
file = SeqIO.parse(r'파일경로','fasta')
for i in file:
    subseq_lst.append(i.seq)
ori_seq=subseq_lst.pop(0)

for i in subseq_lst:
    ori_seq=ori_seq.replace(i,'')#인트론을 제거

print(ori_seq.translate(to_stop=True))#생물학적 룰을 따라 번역

  

 위의 방식대로 푸는 것이 편하긴 하나 필자는 KMP알고리즘이 쓰고 싶어 KMP알고리즘을 이용하여 문제를 푸는 방법도 서술해놓겠다.

from Bio import SeqIO

def get_pi(seq):#pi배열을 구하기
    pi=[]
    for i in range(1,len(seq)+1):
        part_seq = seq[:i]
        f=0
        for fix in range(1,i//2+1):
            if part_seq[:fix] == part_seq[-(fix):]:
                f=len(part_seq[:fix])
        pi.append(f)

    return pi

def KMP(ori,want,pi):#KMP알고리즘
    ind=0
    while True:
        p=0
        if ind>len(ori)-1:
            break
        for ima in range(0,len(want)):
            if ind+ima>len(ori)-1 or (want[ima] != ori[ind+ima]):
                break
            p=p+1
        if p==len(want):
            ind_lst.append([ind,ind+len(want)])#시작과 끝 저장
        ind+=pi[p-1]+1
    return(ind_lst)

subseq_lst=[]

file = SeqIO.parse(r'파일경로','fasta')
for i in file:
    subseq_lst.append(i.seq)
ori_seq=subseq_lst.pop(0)
ind_lst=[]
for sub in subseq_lst:
    pi=get_pi(sub)
    ind_lst=KMP(ori_seq,sub,pi)


ind_lst.sort(key=lambda x:x[0],reverse=True)#크기순으로 내림차순으로 정렬
for start,end in ind_lst:
    ori_seq=ori_seq[:start]+ori_seq[end:]#뒤에서부터 잘라가면 앞의 인덱스는 영향 안 받음

print(ori_seq.translate(to_stop=True))#생물학적 룰을 따라 번역