Finding Disjoint Motifs in a Gene

https://rosalind.info/problems/itwv/

ROSALIND | Finding Disjoint Motifs in a Gene

Problem

Given three strings ss, tt, and uu, we say that tt and uu can be interwoven into ss if there is some substring of ss made up of tt and uu as disjoint subsequences.

For example, the strings "ACAGACAG" and "CCGCCG" can be interwoven into "GACCACGGTTGACCACGGTT". However, they cannot be interwoven into "GACCACAAAAGGTTGACCACAAAAGGTT" because of the appearance of the four 'A's in the middle of the subsequences. Similarly, even though both "ACACGACACG" is a shortest common supersequence of ACAGACAG and CCGCCG, it is not possible to interweave these two strings into "ACACGACACG" because the two desired subsequences must be disjoint; see “Interleaving Two Motifs” for details on finding a shortest common supersequence of two strings.

Given: A text DNA string ss of length at most 10 kbp, followed by a collection of nn (n≤10n≤10) DNA strings of length at most 10 bp acting as patterns.

Return: An n×nn×n matrix MM for which Mj,k=1Mj,k=1 if the jjth and kkth pattern strings can be interwoven into ss and Mj,k=0Mj,k=0 otherwise.

Sample Dataset

GACCACGGTT
ACAG
GT
CCG

Sample Output

0 0 1
0 1 0
1 0 0

 

 이 문제는 1개의 DNA 서열과 n개의 DNA 서열이 주어지고 n개의 DNA 서열 중 2개의 interwoven한 서열이 1개의 DNA 서열에 존재하느냐 마느냐를 기록한 매트릭스를 출력하는 문제이다.

 먼저 interwoven 한 서열이 무엇인지를 알아야한다. 예를 들어 ACA와 GTG라는 서열이 있고, AAACGATGG라는 서열이 있다고 쳐보자. 그러면 ACA와 GTG를 순서에 맞게 잘 조합하면 ACGATG 라는 서열을 만들 수 있고, 이는 AA ACGATGG안에 들어 있다. 이럴 시에 ACA와 GTG는 ACGATG에 interwoven한다고 본다. interwoven은 두 서열에서 글자를 없애지 않고 순서에만 잘 맞게 조합해야 한단 점이 common supersequence와의 다른 점이다. 

 필자는 이러한 interwoven을 다이나믹프로그래밍 방법을 이용하여 풀었다. 자세한 사항은 코드와 함께 알아보자.

def inter_woven(main,n1,n2):
    dp_matrix = [[set() for _ in range(len(n2))] for _ in range(len(n1))]#[n1][n2]

    for nn1 in range(len(n1)):
        for nn2 in range(len(n2)):
            if nn1 == 0 and nn2==0:#끝부분
                dp_matrix[nn1][nn2] = set()
            elif nn1==0 and n2[1:nn2+1] in main:
                dp_matrix[nn1][nn2] = set([n2[1:nn2+1]])
            elif nn2==0 and n1[1:nn1+1] in main:
                dp_matrix[nn1][nn2] = set([n1[1:nn1+1]])
            else:#통상적일때
                if dp_matrix[nn1-1][nn2]:#존재함
                    for a in dp_matrix[nn1-1][nn2]:
                        if a+n1[nn1] in main:#즉 interwoven
                            dp_matrix[nn1][nn2].add(a+n1[nn1])
                if dp_matrix[nn1][nn2-1]:
                    for b in dp_matrix[nn1][nn2-1]:
                        if b+n2[nn2] in main:#즉 interwoven
                            dp_matrix[nn1][nn2].add(b+n2[nn2])
                        
    if dp_matrix[len(n1)-1][len(n2)-1]:#존재시
        return 1
    else:
        return 0




if __name__ == '__main__':
    with open(r"파일경로",'r') as f:
        temp=[]
        for i in f.readlines():
            temp.append((' '+i.rstrip()))
        
        s=temp[0][1:]
        n_list = temp[1:]

matrix_M=[[0 for _ in range(len(n_list))] for _ in range(len(n_list))]

for i in range(len(n_list)):
    for j in range(len(n_list)):
        matrix_M[i][j] = inter_woven(s,n_list[i],n_list[j])

f=open(r"파일경로",'w')
for l1 in matrix_M:
    print(*l1,file=f)

간편하게 어떠한 자리에 있는 interwoven을 알고 싶다면 그보다 한개씩 부족한 서열에서는 존재했는가?, 그 서열에 한개를 더해도 interwoven이 되는가를 따져가며 만들면 알 수 있다/