Assembly에 사용한 프로그램

From Biospecies

 

Assembly Program

 

 

PHRAP

 

Overlap 단계에서 PHRAP은 read들 간의 local alignment를 찾는다. 먼저 read들 간에 정확하게 일치하는 부분들을 찾은 후 이 지점들을 기준으로 좌우로 미리 정해진 폭의 구간(band)에 대해서 Smith-Waterman 알고리즘을 수행한다. 일단 alignment를 찾은 후, 이 alignment 자체와 그 주변의 mismatch 부분들의 quality를 반영하여 LLR score라는 값을 계산한다. 이 LLR score는 quality가 높은 부분에서의 match / mismatch (high quality match / mismatch) 에는 높은 점수를, quality가 낮은 부분에서의 match / mismatch (low quality match / mis-match) 에는 낮은 점수를 주게 된다. 

 

Layout 단계에서는 PHRAP은 다음과 같은 일을 한다.

 

1.       먼저 모든 read들이 각각 하나의 contig가 된다.

 

2.       Overlap 단계에서 찾은 각각의 alignment들을 LLR score에 따라서 정렬한다.

 

3.       정렬된 순서에 따라서 다음 과정을 수행한다.

 

A.       합치려는 두 read가 같은 contig에 속하면 수행을 종료한다.

 

B.       서로 다른 contig에 속한다면, 한쪽 contig의 merge reject list에 다른 contig가 있는지 확인한다. 만약 있다면 이 contig를 merge reject list에서 삭제할 것인지 아닌지를 결정한다.

 

C.       최종적으로 두 contig를 합칠 지 여부에 대한 검사를 수행하고, 통과하면 이 둘을 합치고 수행을 종료한다.

 

D.       통과하지 못하면 merge reject list에 추가하고, repeat 여부를 확인한 후 수행을 종료한다.

 

Consensus 단계에서 PHRAP은 그래프를 이용하여 같은 위치에 놓은 여러 read들 중 quality가 좋은 부분들의 조각을 이어 붙이는 방식으로 consensus를 만든다.


TIGR
TIGR는 다른 fragment assembly 프로그램과는 약간 다른 구조를 가지고 있다.
먼저 BLAST의 초기 처리 과정과 비슷한 방식으로 모든 read들의 쌍에서 n 글자 길이의 유사한 문자열(n-mer)들을 찾는다. 다른 대부분의 fragment assembly 프로그램들이 read들 간의 overlap을 먼저 찾는데 비해, TIGR는 잠재적인 overlap들을 찾은 뒤 layout 단계의 중간에서 실제 overlap들을 찾는다는 특징을 갖고 있다. 현재까지 합쳐진 assembly와 read들간의 잠재적인 overlap을 평가하기 위해서는 변형된 Smith-Waterman 알고리즘을 사용한다. TIGR의 repeat를 찾는 방식은 다음과 같다. 어떤 read가 다른 read들과 지나치게 자주 겹칠 경우 이를 유전체의 repeat인 부분에서 온 것으로 간주하고, read들을 repeat와 non-repeat로 분류한다. Layout 단계에서는 먼저 non-repeat인 read들을 가지고 assemble을 진행한다. 이 과정은 assembly의 한쪽 끝이 repeat인 read들과 잠재적인 overlap을 가질 때까지 반복된다. 음, repeat인 read들 중에서 mate인 read가 assembly에 포함되어 있고, 이 둘 사이의 거리 및 방향 정보를 통해서 위치를 알 수 있는 read들을 assembly에 추가한 추가한다. 이와 같은 방식으로 TIGR는 repeat를 처리하며, 처리가 가능한 repeat의 길이는 mate 간의 거리와 같다. Consensus 단계에서 TIGR는 이미 consensus를 만든 부분에 새로운 read를 하나씩 추가해 나간다. 이미 만들어진 consensus에서 각각의 위치는 이전에 어떤 염기가 이 위치에 놓여졌는지에 대한 정보를 가진다.
Celera assembler
Overlap 전단계에서 Celera assembler는 각각의 read에서 이미 알려진 repeat에 해당하는 부분을 제거한다. 이는 다른 fragment assembly 프로그램에서는 쓰이지 않는 Celera assembler만의 특징이다. Overlap 단계에서 Celera assembler는 BLAST와 비슷한 방법을 사용하여, read들 간에 6% 이내의 차이를 가지면서 40bp 이상 겹치는 부분을 찾아낸다.
Layout 단계에서는 먼저 좋은 overlap을 갖는 read들을 assemble하여 Contig를 만든다. 이 Contig는 유전체에서 유일한 시퀀스이거나 repeat 시퀀스일 수 있다. 이들을 구별하는 방법은 A-static이라는 값을 통해서 발견할 수 있는데, 정상적으로 assemble 되었을 때 주어진 길이에 대한 read의 시작 위치의 분포와 두 repeat가 하나로 잘못 assemble되었을 때의 시작 위치의 분포의 log-odds ratio로 정해진다. 이는 (log e) F/G – (log 2) k 라는 수식으로 나타나며, F는 read의 개수, G는 유전체의 길이, k는 Contig 안의 read 개수, 는 Contig에서 시작 read의 위치와 마지막 read의 위치의 거리이다. 이 값이 10 이상인 Contig를 U-Contig로 정한다. Contig 사이에서 repeat로 인해 잘못 겹쳐지는 것을 막기 위해서 repeat 경계를 구한다. ContigA가 ContigB, C와 겹치면서 B와 C 사이에 겹치지 않는 부분이 있다면, 이 부분이 repeat 경계가 된다. 다음 단계에서는 mate 정보를 이용하여 가능한 모든 U-Contig들을 연결한 scaffold를 만든다. 둘 이상의 mate가 일관되게 두 U-Contig간의 관계를 나타내면 이들이 틀릴 가능성은 매우 낮다.  Mate 정보를 이용하여 U-Contig들 간의 평균 거리와 편차를 계산하고, 둘 이상의 mate로 연결된 U-Contig를 이어서 scaffold를 만든다. 둘 이상의 mate가 필요한 이유는 키메라로 인해서 잘못된 mate 정보가 생길 수 있기 때문이다. 다음에 많은 mate 정보에 의해서 검증될 수 있는 것을 우선으로 scaffold들을 assemble한다. 이 과정에서 만들어진 scaffold의 안과 밖에는 gap이 존재한다. Celera assembler는 rock, stone, pebble이라고 불리워지는 Contig들을 가지고 이 gap들을 채워나간다. Rock은 A-statics가 양수이고, 다른 contig들과 일관되게 연결되는 두 mate를 가지거나 혹은 넷 이상의 다른 contig와 mate로 연결되면서 일관성이 없는 mate가 많아야 하나인 Contig를 말한다. Stone은 다른 contig와 하나의 mate로만 연결되는 Contig이며, pebble은 rock과 stone이 아니면서 log-odd ratio가 좋은 Contig이다. Celera assembler는 rock, stone, pebble을 차례대로 이용하여 scaffold의 gap을 채워나간다.
Consensus 단계에서 Celera assembler는 다음에 설명하는 ARACHNE와 비슷한 방식으로, 한 base씩 오른쪽으로 이동해가면서 quality 정보를 이용하여 최종 consensus를 만든다.
ARACHNE
ARACHNE에서 overlap을 찾아내는 방법은 FASTA와 유사한데, 다음의 4단계로 이루어진다. 첫 번째 입력으로 주어진 read들과 그의 reverse complement에 나타나는 길이 k의 모든 부분 시퀀스(k-mer)의 테이블을 만든다. 두 번째 하나의 gap이 없는 alignment로 합쳐질 수 있는 k-mer들을 병합한다. 세 번째 두 번째에서 만들어진 alignment를 gap을 포함하여 확장시킨다. 네 번째 Dynamic programming을 통하여 만들어진 alignment를 다듬는다. 이렇게 찾아낸 alignment 안에 있는 mismatch에 대해 그 자신과 좌우에 있는 염기, 즉 총 6개의 염기에 대해서 가장 작은 quality를 기준으로 penalty를 계산한다. 이 penalty 값은 quality가 좋을수록 큰 값을 가지며, 이를 이용하여 전체 alignment의 penalty를 계산한다. 너무 좋지 않은 alignment는 버려진다.  ARACHNE는 contig를 만들기 전에 비슷한 길이의 mate 정보를 갖는 두 read들의 쌍이 양쪽 모두 겹치는 것들을 찾아내고, 이를 연결하여 하나의 큰 read로 간주한다. Layout 단계에서는 우선 다른 read에 완전히 포함되는 read(subread)는 일단 사용하지 않고, 남은 read(full read)에서 겹치는 부분이 있는 것들로 잠재적인 repeat 경계까지 최대한 assemble한다. Repeat 경계는 다음과 같이 찾을 수 있다.  Read A와 겹치는 여러 read들이 있고, 그 중 B가 A를 최소한으로 확장할 때 A와 겹치는 다른 read C와 B 사이에 겹치는 부분이 없고 B에서 C까지 다른 read를 통해서도 겹치는 부분을 찾을 수 없다면 A의 오른쪽으로는 더 이상 assemble을 진행하지 않는다. 이 후 repeat 경계를 보다 엄밀하게 적용하여 시퀀서의 오류로 인한 repeat 경계를 찾아낸다.  마지막으로는 앞에서 제외되었던 subread들을 병합한다. Subread A를 포함하는 모든 full read가 하나의 contig에 속하고, 그로 인한 A의 위치가 염기 셋 이내의 거리로 일치하면 A가 이 contig에 포함된다. Repeat는 다음 두 기준에 의해서 찾아낸다. 먼저 read들의 밀도를 이용하는데, 어떤 특정한 read가 지나치게 많이 나온다면 이는 유전체에서 repeat 부분을 읽은 것으로 간주하고 이 read는 이후 사용되지 않는다. Repeat인 contig를 찾는 기준은 Celera assembler와 비슷하게, log-odds ratio  F/G – (log 2) k가 1보다 작다면 repeat로 간주한다. Repeat인 contig를 찾는 또다른 기준은 mate 정보이다. 두 contig A, B가 둘 이상의 mate 정보에 의해서 이어진다면 이들이 link되었다고 하며, A, B간의 평균 거리 d(A,B)와 표준편차 ERR(A, B)를 구할 수 있다. 첫 번째 d(A,B) < -2000 – 4ERR(A,B) 이면 A, B는 repeat이다. 두 번째 Contig A가 contig B, C와 link되어 있다면 d(B, C)와 ERR(B, C)를 구할 수 있다. 이때 d(B,C) < -2000-4ERR(B,C) 이면 A가 repeat이다.