k-mer로 패턴 빈도 구하기

Goal

1. K-mer란?
2. K-mer로 서열 패턴 빈도 구하기

 

K-mer란?

생물정보학에서 k-mer라는 말을 흔히 들어 볼 수 있다. K-mer란 쉽게 얘기해서 k 숫자만큼 길이를 가진 서열을 얘기한다.

 

예를 들어 3-mer라면 3 bp 길이를 가진 "ATA", "ATT", "GCT", "AGT" 등 3개의 염기로 이루어진 DNA 서열 같은걸 얘기하는 것이다.

 

K-mer로 패턴 빈도 구하기 문제

DNA 복제를 시작하는 시점을 origin of replication, 즉 ori 라고 부른다. Vibrio cholerae라는 균의 ori 서열은 아래와 같다.

atcaatgatcaacgtaagcttctaagcatgatcaaggtgctcacacagtttatccacaacctgagtggatgacatcaagatag
gtcgttgtatctccttcctctcgtactctcatgaccacggaaagatgatcaagagaggatgatttcttggccatatcgcaatgaa
tacttgtgacttgtgcttccaattgacatcttcagcgccatattgcgctggccaaggtgacggagcgggattacgaaagcatg
atcatggctgttgttctgtttatcttgttttgactgagacttgttaggatagacggtttttcatcactgactagccaaagccttactc
tgcctgacatcgaccgtaaattgataatgaatttacatgcttccgcgacgatttacctcttgatcatcgatccgattgaagatctt
caattgttaattctcttgcctcgactcatagccatgatgagctcttgatcatgtttccttaaccctctattttttacggaagaatgat
caagctgctgctcttgatcatcgtttc

 

위의 ori 서열에서 단백질이 결합해 중요한 역할을 하는 서열이 "TGATCA"라고 했을 때, "TGATCA"가 몇 군데 있는지 확인하고 싶다. 이것을 코드로 구현할 때 k-mer의 원리를 이용하면 되는데 k-mer를 sliding window 형식으로 만들어 확인하면 된다.

 

예를 들어, 3-mer sliding window를 만든다면 아래와 같이 3 bp 길이로 한 칸씩 옆으로 움직이면서 해당 서열의 모든 3-mer 서열을 확인할 수 있다. (아래 그림은 "ATA"라는 3-mer를 찾는 예시이다.)

위와 같이 sliding window를 사용한다면 3-mer의 시작점은 0에서부터 11까지인 것을 볼 수 있다. 즉, 전체 길이의 3을 뺀 포지션까지의 3-mer 서열을 확인하면 된다.

즉, 찾고 싶은 패턴의 길이인 k 만큼 전체 길이에서 뺀 포지션까지의 k-mer를 확인하면 된다.

def PatternCount(text, pattern):
    count = 0
    text, pattern = text.upper(), pattern.upper()
    
    for i in range(0, len(text)-len(pattern)+1):
        if text[i:i+len(pattern)] == pattern:
            count += 1
    
    return count

 

 

참고

https://stepik.org/lesson/23143/step/7?unit=6783