Pigeonhole Principle for Approximate Sequence Matching

비둘기집원리는 예전부터 지겹도록 듣던 원리중 하나이다. 매우 직관적이고 쓰이는곳도 많지만 approximate sequence matching을 위해서 사용될 수도 있다.

 

Approximate matching은 exact matching과 반대된다고도 할 수 있다. Exact matching은 정확하게 sequence가 같아야 하지만 approximate matching은 어느정도의 edit distance를 허용한다.

 

Edit distance는 수정거리를 뜻한다. 두개의 seq가 있을때 한 seq를 다른 seq로 변형할때 최소한의 편집으로 횟수를 뜻한다. 수정이란 삽입, 삭제, 변형을 뜻한다. 예를들어

AAGTTAC
AACTTAGC

두개의 seq가 주어졌을때 edit distance는 2이다.

AAGTTA-C
|| ||| |
AACTTAGC

대표적인 알고리즘으론 Levenshtein distance algorithm이 있다.

 

Exact matching을 위해선 빠르고 많은 방법들이 있다. k-mer index, suffix tree나 Burrows-Wheeler transform를 이용한 FM index가 그것들이다. 하지만 Approximate matching은 매우 까다로우며 어렵다. 하지만 pigeonhole principle를 이용하면 기존의 exact matching 알고리즘을 사용할 수 있다.

 

만약 길이가 l인 subsequence를 n까지의 edit distace를 허용하는 approximate matching을 하고싶다면 l을 n+1개의 조각으로 나누면 된다. Pigeonhole principle에 따라서 무조건 n+1개의 segment중에서 1개 이상의 segment에는 수정이 없게되며 이것을 이용해 exact matching을 수행할 수 있게된다. Exact matching결과를 가지고 나머지 segment들을 검증하면 된다.

 

길이가 100bp이고 3까지의 edit distance를 허용한다고 하면 25bp를 가지는 4개의 segment를 생성하면 된다. 이때 pigeonhole principal에 따라 최대 3개의 segment에는 수정이 존재하지만 최소 1개의 segment는 수정이 존재하지 않는다. 각 segment를 exact matching을 한 후 그 결과를 이용해 전체 seq가 3이하의 edit distance를 가지는지 확인하면 된다.

DNA의 base는 A, T, G, C 4가지가 존재하므로 random sequence에서 25bp의 exact match sequence가 존재할 확률은 1/(4^25) ≈ 0.000000000000000888이므로 만약 25bp가 exact match한 sequence만 필터링한다면 상당히 많은 경우를 걸러낼 수 있다.

 

추가로 FM index를 이용한 approximate matching도 가능한데 이는 추후에 포스팅 하겠다.