[Sequence assembly] Overlap Consensus Graph

Sequence assembly?

Sequence assembly는 염기서열을 조립하여 하나의 긴 서열을 만드는 방법이다.

 

Next Generation Sequencing(NGS) 시대가 도래하여, 많은 종들에 대한 염기서열을 빠른 시간안에 시퀀싱 할 수 있게 됐다.

 

NGS의 기본적인 원리는 긴 서열을 수백만개의 fragment로 쪼개서 시퀀싱를 진행하는 방법이다.

 

왜? 짧게 쪼개는 이유? 간단하다.

 

한번에 긴 염기서열을 읽을 수 있는 시퀀서가 개발되지 않았었기 때문이다.

 

요즘은 초기에 비해서 긴 길이의 fragment를 읽을 수 있는 long read sequencer 등이 개발되고 있고, short read sequencer와의 비교도 진행되고 있다. 

 

출처: https://bioinformaticsandme.tistory.com/60

 

중요한 부분은 짧게 쪼갠 fragmens를 나중에 어떻게 복원하는지이다. 짧게 쪼갰으니 다시 이어붙여서 우리가 원하는 분석을 진행하여야한다.

 

여기서 연구의 목적에 따라서 다양하게 분류될 수 있다.

 

이번 글 주제는 sequence assembly이므로

예를들면, reference genome이 존재하지 않는 생물종에 대한 reference genome을 만들거나,

혹은 RNA-Seq 데이터 분석을 위한 맵핑 과정에서 reference genome이 없을 경우에 사용하는 transcript assembly 방식 등을 예로 들어서 설명하겠다.

 

만약, 우리에게 reference genome이 없고 단순히 수 많은 read(fragments)가 존재한다면, 우리는 이로부터 하나의 genome을 만들어야한다. 

 

그렇다면, fragments들을 가지고 어떻게 긴 genome을 만들 수 있을까?

가장 먼저 떠오르는 방법은 역시 겹치는 부분을 이용하여 만드는 방법이다.

 

이 글의 주제인 Overlap Consensus Graph 방법도 리드들의 겹치는 부분을 이용하여 그래프를 만든다.

 

Commins, Jennifer, Christina Toft, and Mario A. Fares. "Computational biology methods and their application to the comparative genomics of endocellular symbiotic bacteria of insects."  Biological procedures online  11.1 (2009): 52-78.

 

위 그림처럼 Overlap consensus graph는 리드들의 겹치는 부분을 찾아서, 그래프를 만든 이후 해밀턴 경로를 찾아서 그 경로를 순회하게 되면, 연속적인 서열을 만들 수 있다. 여기서 핵심인 부분은 겹치는 각 리드들이 그래프의 node가 된다는 것이다. 이 부분이 overlap consensus graph 방법의 문제점이 된다.

 

염기서열은 A, C, G, T 4개의 염기서열로 구성되어있다. 인간의 경우 reference genome의 길이는 대략 30억 bp가 되는데, 쉽게 말하면 A, C, G, T 문자가 30억개로 이루어져있다는 것이다. 그렇다면 분명히 반복되는 서열들이 무수히 많이 존재하게 될것이다.

만약 엄청난 수의 중복된 서열들이 그래프의 노드가 되고, 이 그래프에서 해밀턴 경로를 찾는다면 어떻게 될까?

분명히 엄청난 시간이 걸릴 것이다.

이를 NP-Complete 문제라고 정의한다.

쉽게 말하면, 다항 시간안에 문제의 해결방법을 찾을 수도 있고, 찾을 수도 없는 방법이다. 이러한 문제 때문에, 다음 글에서 소개할 de bruijn graph 이론이 현재 assembly 방법에서 가장 유용하게 쓰이고 있다.