<h1>재료 및 방법</h1><h2>기본 전략</h2><p>본 논문에서 주장하는 방법의 기본적인 생각은 두 유전체 간의 유사성에서 출발한다. 참조 유전체에 다른 주어진 \( n-1 \) 개의 유전체들을 연속적으로 비교하여 \( n-1 \) 개의 비교 결과를 조합하여 중복되는 영역을 계산한다. 이와 같이 비교 되었던 다른 유전체들을 차례로 참조유전체로 하여 각각에 대한 중복 영역을 계산한다. Fig. 1은 그 개념을 보여준다. 각 유전체의 어떤 부분이 다른 유전체의 특정 부분과 얼마만큼 중복되는 지를 직관적으로 알 수 기본 전략을 표현한 것이다. 중복된 영역이 주어진 임계값 보다 큰 영역, 누계영역을 블록 혹은 블록노드라 한다. Fig. 2는 유전체 E. coli K12 (NC_000913)을 참조 유전체로 했을때 다른 9개의 다른 유전체와 BLAST 점수 3,000 이상의 영역이 누계로 표현되는 영역이 발생되는 것을 볼 수 있다. 이 블럭은 다중 관계 그래프의 정점으로 설정된다. 이 블럭을 중심으로 다른 유전체와 관련된 블럭들을 계산하고 이들 관계를 시각적으로 보여준다. 연관된 관계를 그래프로 표현하고 이 블록들이 보존되는 영역들을 그래프를 이용해 추이적(transitive)으로 보여준다.</p><h2>전처리 과정과 다중 관계 그래프 생성</h2><p>본 논문에서 제시하는 관계 그래프를 구성하기 위해 전처리 과정을 거쳐야 한다. 기본적으로 두 개의 유전체를 먼저 BLAST를 이용하여 유사성을 검사한다. 이에 대해 \( n-1 \) 쌍의 유전체 유사성 검사를 한다. 결국 주어진 \( n \) 개의 유전체에 대하여 \( C(n, 2) \) 의 비교를 한다. 이 같은 방법은 시간이 많이 걸리는 문제는 있지만 두 유전체간 보존영역을 가장 잘 알 수 있는 방법이다. 이 영역들을 처리하는데 유전체 크기 때문에 실시간 처리는 거의 불가능하며 관계 그래프를 생성하기 위해 전처리 과정을 거친다. 다중 관계 그래프를 생성하기 위한 전처리 과정은 Fig. 3 에서 보이고 있다 그 과정은 정리하면 다음과 같다.</p><li>단계 1. BLAST와 같은 잘 알려진 정렬 프로그램을 이용하여 정렬한다.</li><li>단계 2. 한 참조 유전체를 기준으로 정렬을 \( \mathrm{n} \) 개의 유전체로 확대한다.</li><li>단계 3. 다른 \( n-1 \) 개 참조 유전체에 대하여 단계2를 이용하여 정렬한다.</li><li>단계 4. 일정 점수 이상의 영역을 발췌하여 서로 중복되는 영역을 누계하여 각 영역의 빈도수를 구한다.(Fig. 2에서 특정 영역에 중복되는 영역이 많이 나타나고 있는 것을 알 수 있다.)</li><li>단계5. 구해진 영역의 빈도수가 일정 임계값을 넘으면 그 지역을 블럭노드로 지정한다. 연관된 블럭노드는 간선을 연결하여 다중 그래프를 생성한다</li></ul><p>다중 관계 그래프를 위한 정보는 전처리 단계에서 모두 생성된다. Fig. 4는 생성된 다중 관계 그래프의 블록노드와 다중으로 연결된 것을 개념적으로 보여준다. 같은 색깔은 보존된 영역이고 생성된 관계 그래프 정보는 특정 블록이 지정되면 그 블록노드에 연결된 모든 다른 유전체의 블록노드, 즉 클러스터링된 블록노드를 보여준다. 각 블럭노드는 각각에 대응되는 유전체나 유전자의 정보를 이용하여 GenoVA가 실행될 때 관계 그래프를 생성한다. 생성된 그래프를 모두 보이는 것은 너무 많은 간선을 가지고 있으므로 효율적이지 못하다. 따라서 GenoVA에서는 특정 블록노드와 연관된 정보, 그 블록노드의 클러스터링된 정보만을 보인다.</p>
전처리 과정시 기본적으로 두 개의 유전체를 무엇을 이용하여 유사성 검사를 하는가?
BLAST