효율적인 적합도 계산을 통한 PEATH의 수행 시간 개선

국문 초록 (Abstract)

하플로타입 페이징은 입력으로 주어진 SNP 매트릭스로부터 하플로타입을 결정하는 문제로, 본 논문에서 다루는 PEATH를 포함하여 최근까지도 다양한 하플로타입 페이징 방법들이 제시되고 있다. PEATH는 유전 알고리즘과 토글링(toggling)이라 불리는 휴리스틱을 이용한 하플로타입 페이징 알고리즘으로 많은 계산을 필요로 한다. 본 논 문에서는 PEATH의 수행 시간을 단축시키기 위한 효율적인 구현 방법을 제시하고 실험을 통해 성능을 분석한다. PEATH의 토글링 단계에서는 많은 적합도 계산이 필요한데, 본 연구에서는 계산되는 적합도의 관계를 분석하여, 이전의 계산 결과를 이용하여 적합도를 효율적으로 계산하는 방법을 제안한다. 실험 결과, 제안하는 구현 방법은 PEATH의 수행 시간을 약 12배 개선시켰다.

다국어 초록 (Multilingual Abstract)

Haplotype phasing is a problem of, given an SNP matrix as an input, determining its haplotype. Diverse haplotype phasing methods have been proposed. The PEATH is a haplotype phasing algorithm using genetic algorithms and toggling heuristic which require a lot of computation. In this paper we propose an efficient implementation of the PEATH for improving the running time and analyze the performance experimentally. The toggling of the PEATH requires a lot of fitness computations. We analyze the relationship between these fitness computations and propose an efficient implementation of the fitness computations which make use of the previous computation results. The experimental results show that the proposed implementation enhances the running time of the PEATH by about 12 times.

목차 (Table of Contents)

• 요약
• Abstract
• 1. 서론
• 2. PEATH 알고리즘
• 3. 구현 방법
• 3.1 피연산 read 수 최적화
• 3.2 피연산 bit 수 최적화
• 4. 실험 및 결과
• 5. 결론
• Acknowledgement
• 참고문헌

참고문헌 (Reference)

1 이종근, "클라우드 컴퓨팅을 이용한 개인 유전체 정보 분석: 병렬 CNV 영역 검색 알고리즘" 한국차세대컴퓨팅학회 6 (6): 4-11, 2010

2 송명선, "유전체 데이터를 위한 효율적인 데이터 관리자의 구현 및 성능분석" 한국차세대컴퓨팅학회 8 (8): 24-33, 2012

3 이병욱, "발현 유전자 분석을 위한 고성능 클라우드 서비스 구축" 한국차세대컴퓨팅학회 11 (11): 43-55, 2015

4 이제근, "개인 유전체 하플로타입 결정을 위한 계산학적 연구" 32 (32): 33-40, 2014

5 V. Kuleshov, "Whole-genome haplotyping using long reads and statistical methods" 32 (32): 261-266, 2014

6 이제근, "Survey of computational haplotype determination methods for single individual" 한국유전학회 38 (38): 1-12, 2016

7 V. Kuleshov, "Probabilistic single-individual haplotyping" 30 (30): i379-i385, 2014

8 J. C. Na, "PEATH : single-individual haplotyping by a probabilistic evolutionary algorithm with toggling" 34 (34): 1801-1807, 2018

9 H. Matsumoto, "MixSIH : a mixture model for single individual haplotyping" 14 (14): 2013

10 S. R. Browning, "Haplotype phasing : existing methods and new developments" 12 (12): 703-714, 2011

11 V. Bansal, "HapCUT : an efficient and accurate algorithm for the haplotype assembly problem" 24 (24): i153-i159, 2008

12 A. Tangherloni, "GenHap : a novel computational method based on genetic algorithms for haplotype assembly" 20 : 172-, 2019

13 J. Duitama, "Fosmid-based whole genome haplotyping of a HapMap trio child : evaluation of Single Individual Haplotyping techniques" 40 (40): 2041-2053, 2012

14 B. Ewing, "Base-calling of automated sequencer traces using phred. II. Error probabilities" 8 (8): 186-194, 1998

15 B. Ewing, "Base-calling of automated sequencer traces using Phred. I. Accuracy assessment" 8 (8): 175-185, 1998

16 The 1000 Genomes Project Consortium, "A map of human genome variation from populationscale sequencing" 467 : 1061-1073, 2010