Locating Restriction Sites(제한부위 위치)

https://rosalind.info/problems/revp/

ROSALIND | Locating Restriction Sites

Problem

Figure 2. Palindromic recognition site

A DNA string is a reverse palindrome if it is equal to its reverse complement. For instance, GCATGC is a reverse palindrome because its reverse complement is GCATGC. See Figure 2.

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

Return: The position and length of every reverse palindrome in the string having length between 4 and 12. You may return these pairs in any order.

Sample Dataset

>Rosalind_24
TCAATGCATGCGGGTCTATATGCAT

Sample Output

4 6
5 4
6 6
7 4
17 4
18 4
20 6
21 4

 

 이 문제는 1개의 서열이 있는 fasta 파일에서 제한효소의 작용 부위인 역회문의 시작 위치와 길이를 출력하는 문제이다.그 서열의 역상보적인 서열이 그 서열과 같을 떄 그 서열이 역회문이다 라고 한다. 필자는 이 문제를 두 가지 알고리즘을 이용하여 풀었다.

 첫번째는 말 그대로 정의를 응용하여 풀었다. 이 문제에서 출력 부분을 보면 4~12의 길이인 역회문만을 찾고 역회문은 무조건 짝수이다. 그러니 역회문으로 가능한 길이는 4,6,8,10,12만이 나온다. 무식하게 시작점을 처음부터 끝까지로 잡은 후 시작부터 주어진 길이대로 슬라이싱 한다.슬라이싱한 서열의 역상보가 원래 서열과 같다면 시작과 길이를 출력하는 알고리즘으로 풀었다.

from Bio import SeqIO

file = SeqIO.parse(r'파일경로','fasta')
seq = next(file).seq

for strt in range(len(seq)):
    for l in [4,6,8,10,12]:
        if strt+l <= len(seq) and (seq[strt:strt+l]==seq[strt:strt+l].reverse_complement()):
            print(strt+1,l)

 

 하지만 맨 처음 필자가 생각한 알고리즘은 역회문은 중간을 기준으로 양측으로 벌려가며 비교했을때 상보적인 것에 집중하여 만들어졌다. 하나하나 비교해가며 조건을 따져가며 풀어가는 알고리즘이기에 조금 더 복잡하지만 역회문의 길이가 아무리 길어져도 구할 수 있단 점이 장점이다.

from Bio import SeqIO

def pali(strt,end):
    if strt<0 or end>len(seq)-1 or seq[strt] != ACGT[seq[end]]:#탈출조건
        return
    if 4<=end-strt+1<=12:#길이를 따짐
        print(strt+1,end-strt+1)
    pali(strt-1,end+1)#다음으로

file = SeqIO.parse(r"파일경로",'fasta')
seq = next(file).seq
ACGT = {'A':'T','T':'A','C':'G','G':'C'}


for btw in range(len(seq)):#중간을 기준으로
    strt = btw
    end = btw+1
    pali(strt,end)