[ROSALIND] (k, d)-motif 찾기

문제 설명

Motif란 비슷한 서열을 가짐으로서 비슷한 기능을 하는 것으로 알려진 DNA 내의 짧은 서열들이다. 예를 들어, A라는 단백질이 DNA에 결합하는 위치는 DNA 상에서 여러 위치에 존재하지만 모두 비슷한 서열을 가져야 A가 결합할 수 있을 것이다. 하지만 motif는 100% 똑같은 서열이 아닐 수 있기 때문에 이러한 motif를 찾기 위해서는 어느 정도 염기서열의 차이를 고려해야 한다.

이 문제에서는 (k, d)-motif를 찾는데 여기서 k는 k 길이를 가진 motif를 뜻하고, d는 최대 d 개수만큼 염기서열 차이가 있을 수 있다는걸 뜻한다. 이러한 (k, d)-motif는 서열에 직접 존재하지 않을 수도 있다. 예를 들어, 우리가 찾은 15 bp 길이를 가진 (k, d)-motif가 AAAAAAAAGGGGGGG 일 때, 유사한 motif들은 AgAAgAAAGGttGGG와 cAAtAAAAcGGGGcG 일 수 있다. 두 서열은 (k, d)-motif에서 4개의 염기서열 밖에 차이가 나지 않지만 서로를 비교했을 때는 8개의 염기서열의 차이가 있다.

염기서열 차이(d)가 8이다

이렇게 (k, d)-motif를 찾는 문제는 실제 서열에는 없을 수도 있는 motif 서열을 찾는 것이기 때문에 motif를 찾는 알고리즘을 만드는 것이 좀 더 까다로울 수 있다.

---

문제 (풀어보기)

첫 줄에 k와 d 값이 주어지고, 나머지 줄에는 여러 DNA 서열들이 주어졌을 때, 모든 서열이 공통적으로 가진 (k, d)-motif를 모두 찾으시오. 

예시

3 1
ATTTGGC
TGCCTTA
CGGTATC
GAAAATT

예상 결과

ATA ATT GTT TTT

 

해결

# a와 b 서열에서 차이나는 염기서열 개수를 반환하는 함수
def hamming_dist(a, b):
    return sum(map(lambda x: x[0] != x[1], zip(a, b)))

# d 차이나는 모든 k-mer 찾는 함수
def neighbors(pattern, d):
    if d == 0:
        return [pattern]
    if len(pattern) == 1:
        return ['A', 'C', 'T', 'G']

    neighborhood = []
    suffix_neighbors = neighbors(pattern[1:], d)
    
    for suffix in suffix_neighbors:
        
        # d 보다 작으면 아직 최소 1개는 더 달라도 된다는 뜻이니까 앞에 A,C,T,G를 다 붙여봐도 됨
        if hamming_dist(pattern[1:], suffix) < d:
            for nuc in ['A', 'C', 'T', 'G']:
                neighborhood.append(nuc + suffix)
        
        # d랑 같다면 더 이상 mismatch가 있으면 안되기 때문에 원래 pattern의 앞글자만 더해줌
        else:
            neighborhood.append(pattern[0] + suffix)

    return neighborhood

# 모든 k-mer의 리스트를 반환하는 함수
def get_kmers(k, dna):
    kmers = []
    for i in range(len(dna) - k + 1):
        kmers.append(dna[i:i+k])
    
    return kmers

# (k, d)-motif 찾는 함수
def motif_enumeration(k, d, dnas):
    kmers = get_kmers(k, dnas[0])    # 첫번째 서열의 모든 kmer 찾기

    kd_motifs = []
    for kmer in kmers:
        neighborhood = neighbors(kmer, d)
        for neighbor in neighborhood:
            available = [1] + [0 for i in range(len(dnas) - 1)]
            for i in range(1, len(dnas)):
                if neighbor in ' '.join(neighbors(dnas[i], d)):
                    available[i] = 1
            if sum(available) == len(dnas):
                kd_motifs.append(neighbor)
    
    return set(kd_motifs)

# 입력값 가져오기
given = []
with open('rosalind_ba2a.txt', 'r') as f:
    for line in f.readlines():
        given.append(line.strip())

# 코드 실행하기
k, d = map(int, given[0].split())
motifs = motif_enumeration(k, d, given[1:])
print(' '.join(motifs))

 

참고

https://www.bioinformaticsalgorithms.org/bioinformatics-chapter-2