[ROSALIND] DNA가 공유하는 motif 찾기

문제 설명

유전자(Gene)란 단백질로 번역될 수 있는 DNA의 영역을 얘기한다. 모티프(Motif)는 유전자의 기능과 관련있는 DNA의 작은 단위인데 모티프 서열은 잘 보존돼 있어 모티프를 통해 서로 다른 종 간의 DNA 유사성을 확인 할 수 있다.

이번 문제에서는 여러 DNA 서열들 간에 공유하고 있는 최대한 긴 모티프를 찾는 것이다(모티프가 길수록 공유하는 기능 또한 더 유사하다고 할 수 있기 때문이다!).

---

문제 (Finding a Shared Motif)

최대 100개의 DNA 서열( <= 1kbp)이 FASTA 파일 포맷으로 주어졌을 때 모든 DNA 서열이 공유하고 있는 가장 긴 문자열을 출력하시오.

예시

>Rosalind_1
GATTACA
>Rosalind_2
TAGACCA
>Rosalind_3
ATACA

예상 결과

AC

 

해결

def find_kmers(seq, k):
    return sorted([seq[i:i+k] for i in range(len(seq)-k+1)], reverse=True)

def find_shared_motif(dnas):
    dnas = sorted(dnas, key=lambda x: len(x))
    motifs = [dnas[0]]
    k = len(dnas[0])

    while motifs:
        motif = motifs.pop()
        included = 1
        for dna in dnas:
            if motif not in dna:
                included = 0
                break
        
        if included:
            break
        
        if not motifs and k-1 > 0:
            k -= 1
            motifs = find_kmers(dnas[0], k)

    return motif

dnas = []
with open("rosalind_lcsm.txt", "r") as f:
    lines = f.readlines()
    seq = ''
    for line in lines:
        if line.startswith(">"):
            if seq:
                dnas.append(seq)
            seq = ''
        else:
            seq += line.strip()
            
print(find_shared_motif(dnas))