대용량 DNA 프로파일 고속 근사 검색 방법 = Fast approximate searching method of massive DNA profiles

국문 초록 (Abstract)

유전적 다양성을 이용하여 개체간 차이를 식별하는 것을 DNA 프로파일링(DNA profiling)이라고 한다. DNA 프로파일에는 염색체상의 STR (Short Tandem Repeat), SNP (Single Nucleotide Polymorphism), 미토콘드리아 SNP 데이터가 사용되며, 그 가운데 특히 Multiplex STR 실험으로 획득한 A-STR (Autosomal STR) 데이터는 다중 좌위를 동시에 확인함으로써 높은 식별력을 갖추고, 범죄현장 증거물, 실종아동 확인 등에 널리 사용되고 있다. A-STR 데이터는 약 17여개의 유전좌위에 대한 STR 반복횟수 쌍으로 이루어져 있으며, 이들의 일치여부로 개체를 식별하거나, 공유여부로 부모자식관계를 확인할 수 있다. 데이터베이스에 A-STR 데이터를 저장하고 있다면, 특정 개체의 A-STR 데이터와 일치하거나 부모자식관계에 있는 데이터를 검색할 수 있는데, 돌연변이 혹은 실험상 오차로 인해 정확한 일치 대신 유사하게 일치하는 데이터를 검색하는 일은 실무적으로 매우 중요하다. 따라서 DNA 프로파일 검색 시, 일정 오차범위내로 특정 개수만큼 불일치를 허용하도록 불일치수, 오차범위, 부분검색여부를 선택하게 하면 실무적 효용성을 크게 향상 시킬 수 있다. 본 연구는 대용량 DNA 프로파일을 고속 근사 검색할 수 있는 알고리즘을 제안하며 이를 관계대수로 정리하고 실제 구현하여 상기 고속 검색 방법과 일반적인 일대다 비교 검사와 실행 속도를 비교하였다. 비교 결과 일반적인 일대다 비교 검사는 데이터양이 증가함에 따라 실행속도가 선형적으로 증가하여 10,000건 데이터에서 검색 시 1,000초 정도가 소요되지만, 제안한 고속 검색 방법은 동일성 검색, 부모자식관계 검색 모두 1초이내에 검색결과를 제공한다.

다국어 초록 (Multilingual Abstract)

DNA profiling is a technique to assist in the identification of individual by their genetic variances. DNA profile is composed with STR (Short Tandem Repeat), SNP (Single Nucleotide Polymorphism), mitochondrial SNP. Especially A-STR data generated from multiplex STR is widely used in criminal investigation or parental testing due to their high identification power. Approximate search of identical or parental related STR data is practically important because there can be some mutations or experimental errors. This research proposes fast approximate search algorithm and describes it using relational algebra. Implementation of this algorithm is absolutely fast than conventional one-to-many comparisons. Conventional method takes a lot of search time according to increase data size (1,200 sec when 10,000 dataset) but proposed method takes less than 1 sec.

목차 (Table of Contents)

• 제 1 장 서론 1
• 1.1 DNA 프로파일링 1
• 1.1.1 상염색체 STR (A-STR; Autosomal STR) 2
• 1.1.2 Y염색체 STR (Y-STR; Y chromosomal STR) 4
• 1.1.3 미토콘드리아 SNP 5
• 1.1.4 상염색체 SNP 6
• 1.1.5 인구집단별 대립유전자 빈도 7
• 1.1.6 알려진 데이터베이스 10
• 1.2 DNA 프로파일 검사와 검색 11
• 1.2.1 동일성 검사와 검색 11
• 1.2.2 부모자식관계 검사와 검색 14
• 1.3 확장된 DNA 프로파일 검색방법의 필요성 17
• 1.3.1 불일치수와 오차범위 18
• 1.3.2 부분검색 19
• 1.3.3 고속 검색의 필요성 19
• 제 2 장 대용량 DNA 프로파일 고속 검색 방법 21
• 2.1 데이터모델 21
• 2.1.1 데이터 예제 22
• 2.2 관계대수를 이용한 검색 알고리즘 설명 25
• 2.2.1 관계대수 25
• 2.2.2 기본 검색 알고리즘 26
• 2.2.3 불일치수와 오차범위를 확장한 동일성 검색 28
• 2.2.4 불일치수와 오차범위를 확장한 부모자식관계 검색 29
• 2.2.5 부분검색 30
• 2.3 개선된 방법을 이용한 구현과 검색속도 측정 32
• 2.3.1 개선된 방법 구현 33
• 2.3.1 검색시간 측정 34
• 제 3 장 결과 및 고찰 35
• 3.1 데이터양의 증가에 따른 근사 검색 속도 비교 35
• 3.1.1 근사 검색 질의를 적용한 동일성 검색 속도 37
• 3.1.2 근사 검색 질의를 적용한 부모자식관계 검색 속도 37
• 3.2 불일치수 증가에 따른 근사 검색 속도 비교 38
• 3.3 오차범위 증가에 따른 근사 검색 속도 비교 40
• 3.4 고찰 42
• 참고문헌 38
• 부 록 39