1D 패턴 일치 문제

개요

이전 1C 역상보 문제의 결과에서 우리는 Vibrio cholerae 의 가장 빈번한 상위 4 종류의 서열 중 ATGATCAAG와 CTTGATCAT가 서로 상보적 관계에 있음을 알 수 있었다. 이 결과는 DnaA box를 찾았다는 결론을 뒷받침하는 근거로 여겨질 수 있을까?

이전 장에서 찾은 위의 결과는 유전체의 처음부터 끝까지 전체 영역에서 등장하는 Pattern이었다. 즉, 우리가 찾은 결과는 분포에 대한 정보를 포함하지 않는다. 따라서 결과 pattern들은 유전체 상에서 고르게 분포 되어있을 수 있다.

이것이 왜 중요할까? 다음의 그림을 통해, 유전체의 복제가 어떻게 진행되는지 그 양상을 확인할 수 있다. Bacteria의 경우 Origin of Replication이 하나의 영역에 존재하는 것을 확인할 수 있고, Eukaryotes의 경우 Origin of Replication이 여러 영역에 걸쳐 밀집되어 있음 을 알 수 있다.

따라서 우리는 이전 장에서 찾은 pattern들이 어느 위치에 존재하는지 아는 것이 중요하다. 위치에 대한 정보를 알게 되면 우리가 찾은 pattern들이 얼마나 밀집되어있는지를 확인할 수 있기 때문이다.

그러므로 이번 장에서는 임의의 입력 pattern이 어느 위치에 존재하는지 그 위치를 반환하는 함수를 구현하였다.

Fig 1. (A) Bacterial Replication Initiation, (B) Eukaryotic Replication Initiation

Problem

Input: 찾을 pattern, 유전체
Output: 유전체 상 pattern이 등장하는 위치
function: 찾으려는 문자열 pattern이 유전체 상에서 등장하는 모든 위치(인덱스)를 리스트로 반환

Pseudo-code

findPatternIndices(genome, pattern)
    patternSize = len(pattern)
    genomeSize = len(genome)
    
    indexList <-- empty List
    
    for i <- 0 to genomeSize
        if genome[i:i+patternSize] == pattern
        add i to indexList

  return indexList

Evaluation

Time Complexity

입력크기: $\left\vert genome \right\vert = n$, $\left\vert pattern \right\vert = k $

line[2] ~ line[5]: 변수 초기화 → $O(1)$
line[7]: 모든 genome의 시작점을 순회 → $O(n)$
line[8]: 문자열 비교 연산 → $O(k)$¹
line[9]: (일반적으로) $O(1)$²

어떠한 경우에도 모든 문자열을 순회해야 correct solution이 도출됨

Total Time Complexity: $O(1) + O(n) \times O(k) \approxeq O(nk)$

Implementation

# 주어진 text 문자열에서 pattern이 발생한 문자열의 인덱스를 리스트로 반환하는 함수
def findPatternIndices(text, pattern):
    
    # 발생 빈도를 저장할 배열 선언
    OccList = []
    
    # pattern을 셀 수 있는 모든 문자열을 시작점으로 순회
    for idx in range(len(text) - len(pattern) + 1):
        
        # 시작 문자열부터 pattern 길이만큼의 부분문자열(substring)이 pattern을 형성하면 그 인덱스를 배열에 저장
        if(text[idx:idx + len(pattern)] == pattern):
            OccList.append(idx)

    return OccList

Discussion Points

Summary

이전 결과는 유전체 상에서 pattern이 고르게 등장하는 경우를 포함할 수 있음 (밀집된 경우보다 Randomness가 더 큼)
따라서 빈번한 pattern이 얼마나 밀집되어있는지 (Localization)에 대한 정보가 필요함
이를 알기 위해서는 특정 Pattern이 등장하는 위치를 찾아야 함

Implementation Strategy

유전체 문자열을 순회하며 주어진 pattern만큼 문자열을 가져옴
가져온 유전체의 부분 문자열과 주어진 pattern을 비교
서로 같으면 그 위치를 저장 후 순회가 끝나면 모든 위치를 반환

Implications

이를 통해 찾은 이전 결과 ATGATCAAG의 등장 위치는 116556, 149355, 151913, 152013, 152394, 186189, 194276, … 으로 총 17번임
이 중 위의 151913, 152013, 152394은 매우 가까이 위치한 곳으로, 나머지 경우에서는 이와 같이 군집을 이루지 않음
즉, 이 영역이 DnaA box의 영역일 수 있음을 시사함 ³

Reference

Compeu, P., Pevzner, P. (2018). Bioinformatics Algorithms 3/e. 에이콘 출판사
Replication Initiation figure: https://en.wikipedia.org/wiki/Origin_of_replication

두 문자열 중 가장 긴 것만큼 포인터가 순회하여 비교할 수 있음. strcmp(str1, str2) → O(s), where s = max(str1, str2) ↩
초기 할당된 메모리 크기를 벗어날 경우, 배열의 크기 재조정을 위해 값 복사가 일어날 수 있음 → O(l), where l =len(indexList) ↩
단순히 가까워서라기보다, 통계적 근거에 기반한 추론임 ↩

PREVIOUS1C 역상보 문제

NEXT1E 군집 찾기 문제