Lecture 6: Genome Assembly

de novo whole-genome shotgun assembly

(shotgun refers to the random fragmentation of the whole genome ; like it was fired from a shotgun)

 

De novo assembly

whole-genome "shotgun" sequencing starts by copying and fragmenting the DNA

 

전체 게놈 서열을 한번에 분석하는 기술은 현존하지 않으며,

수백개의 염기쌍으로 이루어진 DNA의 작은 조각 서열로 나누어서 읽어야한다.

Read 라고 불리는 겹치는 조각들을 마치 퍼즐 조각을 맞추듯 원래 서열 또는 게놈을 재구성하기 위해 합친다. 

 

All we have to do is line the reads up to recover the read sequence at the bottom-- the original genome sequence.

맨아래 있는 read sequence를 복구하기 위해서 read 를 정렬 하는 것이다.

 

하지만 2억개 이상, 수십억개의 리드로 구성되어 있기 때문에 이 과정의 복잡성은 엄청나고 각 read 들이

어디서 왔는지 알 수 없다. (sequencing 된 read 출처 확인불가능)

따라서, 별도의 reference 없이 assembly 하는 방식.

주로 서열이 밝혀지지 않은 genome 서열을 밝힐 때 사용한다.

(=> de novo assembly 를 하는 이유)

Coverage : the average number of reads covering a position in the genome.

 

read가 생성되면 해당 genmoe 에 대한 coverage 를 계산한다.

이는 생성된 sequenceing base 들이 얼마나 genmoe base 에 포함되어 있는지 파악한다. 

 

assembly size / target genome size

위 예제에서 177/35 = 7x

 

genome assembly 를 위한 두 가지 알고리즘

 

1. 오버랩(overlap) 그래프

read 들이 겹치는 구간을 찾아서 나열한 후, 가장 가능성이 높은 서열을 선택하는 방식.

sanger sequencing을 할때 사용되고

이 방식을 사용하는 asembly 프로그램으로는 Celera Assembler, CAP4, PCAP, Pharp, AMOS, Newbler 등이 있다.

2. 드부르인(de Bruijn) 그래프 

read 들을 k-mer로 자른 후, 겹치는 k-mer를 연결한다.

여러 갈래로 나누는 경우에는 해당 k-mer가 몇번 나타 났는지 카운팅하게 된다.

coverage가 낮은 경로는 제외하여 contig를 형성한다.

이 방식을 사용하는 asembly 프로그램으로는 soapDenovo, Velvet, ABySS, SOAPdenovo 등이 있다.

 

드부르인 그래프를 이해하기 전에,

k-mer : 문자열(string)에서 가능한 모든 부분문자열(substring) 의 길이를 의미

그림 요약:

Ayling , 2018

overlap 길이를 다르게 할 수 있기 때문에 반복에 덜 민감하게 작용하지만,

pairwise overlap 단계에서 de Bruijn 그래프 보다  많은 시간과 컴퓨팅 자원이 필요로 한다.  

 

해밀턴 경로 : 모든 노드를 정확히 한번 통과하는 경로.

오일러 경로 : 모든 예지를 정확히 한번 통과하는 경로. (한연필 그리기)

 

de novo assembly overall steps

https://bmcgenomics.biomedcentral.com/articles/10.1186/s12864-018-4567-3

1. overlap 이나 de Bruijn 방법으로 read 를 모아서 assembly 한다.

2. assembly 된 read 들은 contig 를 형성한다.

3. contig를 연결하여 scaffold 를 형성한다.

4. 만들어진 scaffold 들은 gap filling 과정을 통해서 draft genome 으로 완성된다.

 

reference

1.https://ar6com.tistory.com/94

De novo assembly 알고리즘 비교(De bruijn Vs Overlap layout consensus)

2.https://www.koreascience.or.kr/article/JAKO201432558387461.pdf