Mapping #
Find similar titles

2016-04-29 00:42:16 (rev. 3)
ympaik-intern@insilicogen.com
Edit

Structured data

Category: Software

Genetic Mapping
Mapping Tool
1. Hash-based Mapping Tool
  1. Stampy
  2. MAQ
2. BWT-based Mapping Tool
  1. BWA
  2. SOAP2
Incoming Links
1. Related Bioinformaticses (Bioinformatics 0)
Suggested Pages

Genetic Mapping #

사람에 대한 어떠한 새로운 단편 유전자 시퀀스가 있을 경우 해당 유전자가 사람에게 어떠한 역할을 하는지 알기 위한 방법으로 먼저 잘 알려진 유전 정보를 가지고 해당 유전자가 어떤 위치에 있는 것인지 찾으므로써 어떠한 의미를 가지고 있는지 유추 할 수 있다. 이러한 참조서열로부터 임의의 시퀀스의 위치를 찾는 것을 매핑(Mapping)한다고 하며, 이 방법을 통해 특정 시퀀스의 기능이나, 발현된 RNA 시퀀스가 어떠한 기능을 갖는가를 확인 할 수 있다.

Mapping Tool #

위와 같은 매핑 과정을 사람의 손으로 일일히 찾는것은 매우 어렵고 시간과 인력의 비용이 많이 소모된다. 매핑 과정에 발생하는 시간과 인력의 비용을 줄이기 위한 프로그래밍 도구로 컴퓨터를 이용한 매핑 도구를 많이 활용하며, 각 시퀀스의 형태와 목적에 따라 다양한 매핑도구을 개발하기위한 연구가 이루어지고있다. 일반적으로 매핑도구는 알고리즘에 따라 해쉬(Hash) 기반의 매핑도구와 BWT 기반의 매핑도구가 있다.

Hash-based Mapping Tool #

해시 기반 알고리즘은 참조서열을 k-mer과 같이 분할한 후 해시테이블에 분할한 서열을 키값으로 하여 해당 서열의 위치를 저장한다. 이후 매핑과정을 수행할 때에 리드역시 k-mer로 나누어 해시테이블을 통해 비교한다. 해시 기반 도구의 경우 이론적으로는 한번 해시 테이블을 생성하고 나면 이후에는 \( O(1) \)의 수행시간만에 리드를 매핑하는 것이 가능하지만 실제 도구에서는 Collision과 리드의 에러율에 대해 고려해야 하므로 \( O(1) \)의 시간내에 수행하기는 것은 약간 어렵다. 그러므로 해시 기반 도구는 앞의 두가지 문제점을 해결하는 방법에 따라 알고리즘과 도구의 성능에서 차이가 발생한다

Stampy #

Stampy는 참조서열을 k-mer로 나누어 해시 태이블로 생성한다. 이렇게 해시 테이블을 만들게 될 경우 메모리 비용이 매우 커지게 될 수 있으므로 몇개의 bp씩만 겹치게하여 해시테이블의 크기를 줄이게 한다. 또한 과도하게 반복되는 k-mer의 경우 일정 수가 넘어갈 경우에는 반복 시퀀스로 간주하고 더이상 해시테이블에 저장하지 않는다. 해시 테이블이 생성되고 나면 리드에서 가능한 모든 k-mer을 생성하여 해시테이블과 비교한다. 이때 최대 한개의 불일치 까지 허용된다. Stampy는 리드로부터 최대한 많은 k-mer를 생성하여 비교하기 때문에 높은 정확도를 보이나, 계산량이 많아 속도가 느려지는 단점이 있다.

MAQ #

MAQ는 템플릿을 이용하여 리드서열로부터 여러개의 해시값(템플릿쌍)을 만들어 해시 테이블을 구축한 후, 참조서열에 비교하여 리드의 위치를 찾는다. 이후 하나의 탬플릿쌍을 선택하여 전체 참조서열을 확인하며 템플릿쌍에 매칭되는지 비교하고 다음 템플릿쌍으로 이를 반복한다. MAQ는 k개 이하의 모든 mismatch쌍을 비교 할 수 있으나 mismatch수가 증가할수록 템플릿 수가 증가하며 템플릿 수만큼 전체서열을 비교해야 한다. 또한 매번 리드를 수행 할 때마다 해시 테이블을 생성해야하는 단점이 있다.

BWT-based Mapping Tool #

BWT(Burrows-Wheeler Transform)알고리즘은 1994년 Burrows와 Wheeler가 처음 제안한 방법으로 BWT를 이용하여 BW Matrix을 생성성하고 BW Matrix를 SuffixArray, FM-index과 같이 응용하여 리드와 매칭이 되는지 확인한다. Bowtie, BWA, Bowtie2와 같은 가장 대표적인 분석도구 역시 이러한 BWT 알고리즘을 이용한 도구이다.

BWA #

BWA는 BWT와 접미사 배열을 이용하여 정렬을 수행하는 알고리즘이다. BWT변환에 의해 생성된 BW-Matrix의 접미사가 SA(Surffix Array)의 어느 구간에 해당하는지 알면, BW-Matrix의 매핑 결과로 SA구간을 찾음으로써 원본 서열에서의 위치를 알 수 있다. BWA는 subtitutioin 뿐만 아니라 indel에 대해서도 mismatch를 수행 한다. 백트래킹을 통해 mismatch를 수행하는데, 이론적으로는 BWA를 이용하여 모든 k-mismatch를 찾을수 있으나 비용이 매우 커지므로 제한된 범위 내에서 k-mismatch를 수행한다.

SOAP2 #

SOAP2 는 매핑속도에 중점을 둔 BWT기반 도구이다. 전체적인 진행과정은 BWA와 유사하지만, 속도를 올리기 위해 최대 2개의 mismath만 허용한다. 즉 탐색 도중 더이상 탐색이 불가능한 구간에 도달하면 그위치의 문자를 다른 문자로 subtitution하여 수행한다. SOPA2는 매우 빠른속도를 보이지만, mismatch수가 제한적이며 error가 많을경우 속도가 저하된다.