[Bioinformatics] Multiple Pattern Matching

학부생의 개념정리이니 어리숙한 표현이 있을 수 있습니다.

오류가 있으면 계속해서 수정할 예정입니다.

 

---

1. BruteForcePatternMatching

 

각각의 패턴들을 가지고 와서 하나씩 Text와 비교하는 방법

=> 첫번째 위치부터 한칸씩 slide하여 비교하며, 각 패턴이 주어진 Text의 어느 위치에서 매칭이 되는지 순차적으로 찾아나감

​

 

Runtime : O(|Text|*|Patterns|)

 

|Text|: the length of Text

|Patterns|: sum of the lengths of all strings in Patterns

why? 각 패턴마다 text를 하나하나 읽어나가야 하니까 runtime이 매우 high

​

→ 패턴을 모아서 한번만 reference genome을 읽으며 각 패턴에 맞는 것이 있는지 확인해보자!

​

 

2. Trie

 

모든 패턴을 하나의 트리구조에 전부 표현한 자료구조

 

 

 

Trie의 특징

 

- single root node

- Edge of TRIE(Patterns)is labeled with a letter

- Edges of a given node have distinct labels (특정 노드에서 나가는 edge들은 서로 구별되는 label을 가짐)

- Every path from the foot to a leaf spelss Patterns (root node부터 leaf node까지의 문자들을 연결하면 각각의 패턴을 의미)

 

→ text가 주어지면 trie는 그 패턴이 text의 prefix에 맞는지 여부를 빠르게 확인 할 수 있음

​

 

 

 

 

 

 

Runtime : |Text|*|LongestPatter| + |Patterns|

​

• TRIEMATCHING은 빠르긴 하나, 메모리 소비가 매우 큼
• BruteForce의 경우 하나의 패턴을 reference genome과 비교한 후 그 패턴은 더이상 필요가 없게 되므로 메모리상 삭제가 가능
• 하지만 TRIEMATCHING은 trie 구조를 전부 메모리에 올려야 reference genome과 비교 가능
• 즉, 패턴의 개수가 많아질수록 소비되는 메모리도 비례적으로 증가

​

 

3. Suffix Trie

​

패턴 대신 reference genome을 trie의 구조에 넣는 형태, text의 suffix를 trie에 실어서 모든 패턴과 비교하는 방법

→ 가변적으로 증가하던 요구치를 고정적인 사이즈로 변환가능

 

- $: text의 마지막을 나타내는 문자

- 각 leaf node에는 해당 suffix의 시작지점이 표시됨

​

 

 

위의 사진을 보면 "ana"는 1, 7, 9 leaf node에서 발견할 수 있음

해당 suffix trie를 따라서 패턴이 흘러가게되고, 그 패턴이 spell out을 마무리하는 시점에서

다음과 같은 여러 경로가 존재한다는 뜻은 패턴 "ana" 가 주어진 text에서 여러 번 매칭됨을 의미

=> suffix trie 구조를 이용하면 여러 번 매칭이 되는 정보를 한 번에 파악 가능

​

 

TRIE(Patterms) : O(|Patterns|) runtime and memory

SUFFIXTRIE(Text): O(|Text|^2) runtime and memory

​

​

4. Suffix tree

 

 

edge를 합쳐서 하나의 node로 줄이자! 기존에는 edge 마다 하나의 label 이 기록이 되었다면

suffix tree에서는 branch하지 않는 모든 label을 하나의 dege에 표현

​

 

SUFFIXTREE(Text): 2 * |Text| nodes

Memory required O(|TEXT|)

​

 

그렇다면 왜 suffix tree는 메모리 효율적인가?

 

인덱스 위치(포인터 위치)를 알면 합쳐진 label에 대해 저장할 필요가 없고

단지 시작점과 길이만 저장하게 되므로 메모리 소요가 적음

​

suffix tree가 O(|Text|^2)에서 O(|TEXT|)까지 줄였음에도 여전히 text 길이의 20배 정도의 메모리를 필요로 한다

 

5. Suffix Array

​

suffix tree의 효율적인 버전

모든 suffix를 sorting한 이후, suffix들이 시작되는 위치정보를 리스트업하여 text의 모든 suffix를 사전순서로 정렬

 

Sorting all suffixes takes O(|Text|*log(|Text|))

​

"ana"의 경우 starting point가 1, 7, 9였음을 suffix trie에서 확인했었는데

suffix array는 sorting을 했기 때문에 연속적으로 비슷한 애들끼리 리스트에서 확인할 수 있음

​

→ suffix array로 어떤 패턴이 주어진 text에 매칭이 되는가를 확인하는 것은 

    뭉쳐져 있는 suffix들로 부터 매칭되는 시작, 끝 인덱스를 찾는 것

​

 

​

 

6. Burrows-Wheeler transform (BWT)

 

​BWT를 알아보기 전에 Run-length encoding을 알아보자

 

* Run-length encoding

: 같은 글자가 많이 반복되는 text에 유용한 압축 방법

​

ex ) TTTTTGGGAAAACCCCCCA =>5T3G4A6C1A

 

하지만 GCATCATGCA, ACTGACTACTG =>AAACCCGGTTT

 

다른 string임에도 같은 string으로 압출되는 문제가 발생!

우리는 데이터를 단순히 줄이는 것이 주 목적이 아니라,

DNA sequence가 어디에 매칭되는지를 적은 용량으로 해결하고자 하는 것!

 

 

* BWT(Burrows-Wheeler Transformation)

​

 

1. 변환하고자하는 text의 맨 마지막에 단어의 끝을 알리는 $을 넣음

2. cyclic rotation을 통해 $을 왼쪽으로 한칸씩 이동하여 matrix 생성

3. matrix를 사전순으로 sorting함

4. 정렬된 matrix의 맨 마지막 열의 문자열이 BWT의 결과

​

 

첫번째 column은 원래 text를 사전순서로 sorting 한 데이터

사전순으로 sorting한 데이터는 원래 데이터의 의미를 상실한 것이므로

우리는 마지막 colunm에 관심이 있다! => BWT(Text)

​

 

BWT 전 후에 문자열의 길이는 변함이 없으나, 중복되는 문자열이 많을 수록

single character가 반복되는 경우가 생기기 때문에 압축하기가 용이해짐

.

.

 

 

우리는 첫번째 column은 마지막 column의 뒤에 있었던 문자임을 알고(rotation),

첫번째 column의 순서가 정해지면 마지막 column에 동일하게 그 순서가 등장한다는

특징을 아니까 2가지 특성을 활용하면 모든 글자를 찾을 수 있음

​

 

# Idea 1

위의 사진을 보면 $을 기점으로 원래 text에서 가지고 있던 suffix가 포함된 것을 알 수 있는데,

이러한 아이디어는 matrix를 사실상 매칭할 때 저장할 수 가 없다

우리의 목표는 메모리 사이즈를 줄이는 것이니 이 아이디어는 적합X

​

​

#Idea 2

 

알파벳의 순서가 보존되고, 시작과 끝점의 index를 찾아서 그 안에서 몇개의 매칭이 일어나는지 확인하는 것

(BWT의 LastFirst mapping 법칙을 이용해 문자열 index를 만든 방법)

​

​

 

"ana"를 찾고자 하면

-> last column의 a1과 a6에서 시작

-> first column의 a1, a6의 last colum n1, n3로 이동

-> last column의 n1, n3에서 fisrt column의 n1,n3로 이동

-> firstt column의 n1,n3의 마지막 colunm의 a3, a5로 이동

(너무 주저리 주저리인가?.. 사진을 통해 이해하면 된다!)

​

아무튼.. 두개의 포인터를 이용하면 몇개의 매칭이 일어나는지 알 수 있는데,

Total number of matches = bottom - top + 1

​

위의 그림을 공식에 대입해보면 결국 5-3+1 = 3 이니까

3개의 매칭이 일어난 것을 알 수 있음

​

 

그렇다면 BWT는 얼마나 빠른가?

​

1975년도 당시의 최신 알고리즘이었던 Aho-Corasick 알고리즘 같은 경우 24개의 단어를 찾으려면 15분을 소요해야 했는데,

BWT는 15분에 1000만개의 단어를 매핑 가능하다고 한다

 

 

 

+) ...

 

만약 어떠한 패턴을 찾으려 하는데, text에 single mismatch가 있다면 어떻게 해야할까?

우리는 패턴을 one mismatch substring + exact matches substring 으로 나누면 된다

만약 두 string이 n개의 match, d개의 mismatch를 포함한다면, 아마 두 string은 k의 길이만큼 공유해야 함

예를 들어,

패턴의 길이 = 20, mismatch = 3개 라고 한다면

결국 2개의 stirng에서 최소한 5개의 길이만큼 공유해야하므로 이 패턴을 4개의 부분으로 나눌 수있다.

 

(사실 이 부분은 무엇을 말하고자 하는지 잘 모르겠어서 다시 공부해보고 수정해야겠다..)

​