Genomic signature is a function of which input is a genomic sequence with (A, C, G, T) and output is a vector of real numbers. It helps engineers to mathematically analyze genome sequence with various length and compare each different genome sequences. There are three reasons why we try to develop a good genomic signature which reflects biological information well. First is identification which decides the original group to which target genome belongs. Second, if a genomic signature reflects biological information well, it can be a sequence modeling itself. Third, it can give some intuitions to design of biological experiments. Description of our research is as follows.
We introduce two conventional genomic signatures, Chaos Game Representation and Ordered Vertex Isolation Frequency, which are the most famous genomic signature on which other genomic signatures are based. However, there have not been remarkable improvement of the performance of identification and of other metric. We analyze conventional genomic signatures based on steady state probability and state transition probability on de Bruijn graph. And, we define the limitation of conventional genomic signatures by showing that all conventional genomic signatures are all most the same in engineering point of view and cannot extract any information of words with various length.
From the limitation of conventional genomic signature, we propose a novel genomic signature which is also based on de Bruijn graph. Although we use de Bruijn graph in common with conventional genomic signatures, proposed genomic signature, Core Node Finer (CNF), extracts information of words with various length by defining a new characteristic, Start-Core-Last path. And, we develop an algorithm to realize proposed genomic signature with $O(n)$ complexity. And Theoretical analysis consists of expectation and variance of genomic signature under some assumptions.
Finally, we perform some experiments to evaluate the performance of proposed genomic signature. First experiment is to compare the identification performance of proposed genomic signature with that of conventional genomic signatures using two phylogeny matching algorithm like G2MPAM and G2APAM. In this experiment, we show that proposed algorithm has ~37\% better performance than conventional genomic signatures. Second experiment is to generate phylogenetic trees using proposed genomic signature and conventional genomic signatures for some dataset and to interpret the tree in view of phylogeny. And then, we verify the theoretical analysis by comparing numerical results with simulation results.
유전체 해독 기술이 발점함에 따라 다양한 생물체의 염기서열이 발표되고 염기서열을 데이터로 간주한 유전체 분석연구가 수행되고 있다. 지놈 시그너처는 유전체 염기서열을 입력으로하고 실수형 벡터를 출력으로 하는 함수로서, 염기서열을 특정한 기준에 따라서 정량화하는 기술이다. 이러한 지놈 시그너처는 다양한 길이의 다양한 종의 지놈을 표현하는 기술로서 지놈의 식별과 계통생물학 연구에 이용될 수 있으며, 시퀀스 모델링 기술을 검증하는 방법으로도 사용 될 수 있다.
기존 지놈 시그너처 연구로 드브루인 그래프에서의 정상 상태 확률 기반의 CGR(Chaos Game Representation)과 상태 전이 확률 이용한 OVIF(Ordered Vertex Isolation Frequency)가 있다. 이외에도 드브루인 그래프 기반의 연구들이 존재하나 그들이 다루고 있는 정보가 정상 상태 확률과 상태 전이 확률에 국한되어 두드러진 성능 향상을 보이지 못했다. 이는 $W$ 차원의 드브루인 그래프에서 상태 전이 확률이 $W+1$ 차원의 드브루인 그래프에서 정상 상태 확률과 같은 속성에 기인한다. 따라서 기존의 지놈 시그너처와 차별되는 개념의 접근이 필요하다.
본 논문에서 제안하는 지놈 시그너처 CNF(Core Node Finder)는 드브루인 그래프에서의 시-종 경로와 시-중-종 경로의 개념을 정의 함으로써, 세 DNA 단어 사이의 관계를 표현한다. 두 단어 사이에 존재하는 또 다른 단어의 비율을 시그너처 벡터의 요소로 사용한다. 따라서 드브루인 그래프의 정상 상태 확률과 상태 전이 확률에 국한된 기존 지놈 시그너처와 달리 다양한 길이의 부분염기서열에 대한 정보를 나타내며 염기서열 해석의 새로운 방법을 제안한다. 그리고 제안 지놈 시그너처에 대한 이론적 분석을 수행함으로서 드르부인 기반의 지놈 시그너처 연구에 공학적으로 기여한다.
제안한 지놈 시그너처의 성능 분석을 위해서 각각 10개의 지놈으로 이루어진 박테리아 20개의 그룹과 40개의 지놈으로 이루어진 미토콘드리아 5개 그룹에 대하여 식별기능을 실험한다. 본 실험은 기존 지놈 시그너처 대비 박테리아에 대하여 17~36\% 미토콘드리아에 대하여 3~17\% 의 성능향상을 보인다. 또한 기존 지놈 시그너처와 제안 지놈 시그너처를 이용하여 미생물과, 사람 과 쥐에 대하여 계통수를 만든다. 지놈 시그러너처의 계통생물학 관점의 유효성을 확인하기 위해서 설계된 미생물 계통수를 통하여 제안 지놈 시그너처가 종의 분류 및 계통생물학 연구에 적합함을 확인하였으며, 사람 과 쥐의 계통수를 통하여 사람의 16,17,19,20,22번 염색체가 다른 염색체와 다른 계통를 가질 수 있다는 추측을 할 수 있다.