Enumerating k-mers Lexicographically

문제 원본

concept

랩몬 K-mer 를 참고 했습니다.

K-mer는 유전체의 리드 데이터를 mapping 하는데 상요되며, de novo assembly에도 사용된다고 합니다. K-mer란 간단하게 어떤 특정 길이의 서열이 주어졌을 때, K개로 서열을 쪼개지는 부분문자열들이라고 할 수 있습니다. 예를 들어 ATCGTGAGC라는 문자열이 있을 때, 3-mer로 부분분자열로 쪼갤경우

	ATC TCG CGT GTG TGA GAG AGC
    
    ATC
     TCG
      CGT
       GTG
        TGA
         GAG
          AGC

로 쪼개질 수가 있습니다. 그리고 그 양은 전체 주어진 서열의 길이가 L 이라고 했을 때, L-K+1 개가 됩니다. 위의 예제에서도 총 9개의 문자열에서 k=3 을 빼고 1을 더하니 7개가 나오게 됩니다.

그렇다면 이 K-mer가 맵핑과 de novo assembly에서 어떻게 이용이 될까요? (RobEdwards 채널)
예를들어 아래와 같은 2 서열이 있다고 합시다. 이 두서열의 4-mer를 이용하여 첫 예제에서와 같이 ovelapping 되게 4-mer로 쪼갠 서열들을 정렬할 수가 있습니다. (youtube에서 나온 예제를 참고했습니다.)

	AACCGGTTA, GGTTATAC
   	AACC       GGTT
         ACCG       GTTA
          CCGG       TTAT
           CGGT       TATA
            GGTT       ATAC
             GTTA

위의 4-mer 로 쌓아올린 첫번째 서열의 맨 마지막 2개의 조각과 두번째 서열의 첫번째와 두번째 조각이 동일한것을 보실 수 가 있습니다.
이 경우에 AACCGGTTA 서열과 GGTTATAC는 AACCGGTTATAC 라는 서열로 assembly가 될 수 있습니다.

(de Brujin Graph 에 대해서는 따로 나중에 포스팅 하겠습니다 혹시 먼저 알고싶으시다면 이 ppt를 참조하세요.) 생물학 지식이 많이 부족하다는 것을 찾아보면서 깨닫습니다. 혹시 제가 잘못 알고 있는 지식이 있다면 답글 납겨 주세요!

Problem

조합을 구할 문자를 정해주고, 몇글자로 조합할지 n개를 input 값으로 줍니다. 그러면 모든 조합을 구하는 것입니다. 이 쉬운 문제를 왜 그렇게 해맸나 모르겠습니다. 한번 풀어보죠.
만일 n이 정해져 있다면 간단합니다. for문을 2개써서 모든 조합을 리스트에 저장하고 출력하기만 하면 끝입니다. 하지만 2개가 아니라 n개라면 for 문을 계속 써줄 수도 없으니 약간 골치가 아파집니다. 하지만 트리로 생각하면 문제가 너무나도 간단해집니다. 예를들어 문제에서 주어진 예제처럼 A T G C 4가지 글자가 2글자 조합을 모두 구해야 한다고 했을 때 아래와 같이 트리의 맨 마지막에서 모든 조합을 수집할 수 있습니다.

Solution

1. combination
   조합을 구하는 함수입니다. 위의 문제 설명에서와 같은 이론으로 돌아가도록 구현했습니다.

def combination(n, input_data: list):
    global words
    words = [] # 트리의 leaf에서 완성된 데이터를 수집하기 위한 글로벌 변수입니다.
    
    # 모든 경우의 수를 탐지하기 위한 tree 함수입니다.
    def tree(chars, depth, acc):
        if depth == 0: # 마지막 leaf 노드에 도달하면 
            words.append(acc) # 완성된 데이터를 수집하고 반환합니다.
            return
        # chars에는 조합 가능한 문자열이 저장되어 있어 재귀로 깊이 들어갈 때마다 글자 개수만큼 함수가 들어갑니다. (물론 depth가 128 이상이면 에러가 납니다만 다행히도 Rosalind는 관대합니다.)
        for char in chars:
            tree(chars, depth -1 , char + acc) # depth를 하나 줄이고 char와 누적된 데이터를 합쳐서 다시 tree를 호출합니다.
            
    tree(input_data, n, "") # tree 함수 호출
    return words

전체 코드

import toolz as tz
from toolz.curried import *
test_data = "A C G T"
n = 2


input_processor = lambda x: x.split(" ")

@tz.curry
def combination(n, input_data: list):
    global words
    words = []
    def tree(chars, depth, acc):
        if depth == 0:
            words.append(acc)
            return
        
        for char in chars:
            tree(chars, depth -1 , char + acc)
            
    tree(input_data, n, "")
    return words

print_length = lambda x: print(len(list(x)))
    
run = tz.compose(do(print_length), sorted, combination(n), input_processor)

print(*run(test_data), sep="\n")

마치며

k-mer를 파다보니 de Brujin Graph라는 개념에서 막혔네요. 좀더 공부를 해야 할 것 같습니다. 그리고 재귀를 이용한 전체 경우의 수같은 경우에는 python 자체가 stack에 제한을 걸어놔서 제한적인 경우만 가능한것 같습니다. 좀더 개선이 필요한 것 같습니다.