Finding a Shared Motif(공유 모티브 찾기)

https://rosalind.info/problems/lcsm/

ROSALIND | Finding a Shared Motif

Problem

A common substring of a collection of strings is a substring of every member of the collection. We say that a common substring is a longest common substring if there does not exist a longer common substring. For example, "CG" is a common substring of "ACGTACGT" and "AACCGTATA", but it is not as long as possible; in this case, "CGTA" is a longest common substring of "ACGTACGT" and "AACCGTATA".

Note that the longest common substring is not necessarily unique; for a simple example, "AA" and "CC" are both longest common substrings of "AACC" and "CCAA".

Given: A collection of kk (k≤100k≤100) DNA strings of length at most 1 kbp each in FASTA format.

Return: A longest common substring of the collection. (If multiple solutions exist, you may return any single solution.)

Sample Dataset

>Rosalind_1
GATTACA
>Rosalind_2
TAGACCA
>Rosalind_3
ATACA

Sample Output

AC

 이 문제는 fasta 형식으로 주어진 서열들 간에 공유하는 가장 긴 서열 즉 모티브를 찾는 문제이다. 이 문제의 경우는 AGCT 4가지 염기서열만 다루므로 필자는 좀 무식한 방법으로 DFS를 이용해서 모든 AGCT의 가짓수를 따져가며 가능한 모든 경우를 리스트에 저장했다. 이 후 이 리스트에서 가장 긴 문자열을 출력하는 식으로 문제를 풀었다.

from Bio import SeqIO

def DFS(motif): #DFS
    for c in seq_list:
        if motif not in c:
            return#만약 이 모티브가 서열에 없다면 리턴
    M.append(motif)#있다면 저장
    for a in 'AGCT':
        DFS(motif+a)#AGCT 추가해서 다시 

file = SeqIO.parse(r'파일경로','fasta')
seq_list=[]
M=[]
for i in file:
    seq_list.append(i.seq)
for a in 'AGCT':
    DFS(a)
print(max(M,key=len))#가장 긴 문자열 출력