효율적인 적합도 계산을 통한 PEATH의 수행 시간 개선
Improving the running time of PEATH by efficient fitness computations
0
조회
0
다운로드
1
인용
0
참고문헌
키워드
초록
하플로타입 페이징은 입력으로 주어진 SNP 매트릭스로부터 하플로타입을 결정하는 문제로, 본 논문에서 다루는 PEATH를 포함하여 최근까지도 다양한 하플로타입 페이징 방법들이 제시되고 있다. PEATH는 유전 알고리즘과 토글링(toggling)이라 불리는 휴리스틱을 이용한 하플로타입 페이징 알고리즘으로 많은 계산을 필요로 한다. 본 논문에서는 PEATH의 수행 시간을 단축시키기 위한 효율적인 구현 방법을 제시하고 실험을 통해 성능을 분석한다. PEATH의 토글링 단계에서는 많은 적합도 계산이 필요한데, 본 연구에서는 계산되는 적합도의 관계를 분석하여, 이전의 계산 결과를 이용하여 적합도를 효율적으로 계산하는 방법을 제안한다. 실험 결과, 제안하는 구현 방법은 PEATH의 수행 시간을 약 12배 개선시켰다.
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.
참고문헌 (16)
- The 1000 Genomes Project Consortium, "A map of human genome variation from populationscale sequencing", Nature, 467, pp.1061~1073 (2010)
- 이종근, "클라우드 컴퓨팅을 이용한 개인 유전체 정보 분석: 병렬 CNV 영역 검색 알고리즘", 한국차세대컴퓨팅학회 논문지, 6(3), pp.4~11 (2010), 한국차세대컴퓨팅학회
- 송명선, "유전체 데이터를 위한 효율적인 데이터 관리자의 구현 및 성능분석", 한국차세대컴퓨팅학회 논문지, 8(1), pp.24~33 (2012), 한국차세대컴퓨팅학회
- 이병욱, "발현 유전자 분석을 위한 고성능 클라우드 서비스 구축", 한국차세대컴퓨팅학회 논문지, 11(3), pp.43~55 (2015), 한국차세대컴퓨팅학회
- S. R. Browning, "Haplotype phasing : existing methods and new developments", Nature Reviews Genetics, 12(10), pp.703~714 (2011)
- 이제근, "개인 유전체 하플로타입 결정을 위한 계산학적 연구", 한국정보과학회지, 32(3), pp.33~40 (2014)
- J. Duitama, "Fosmid-based whole genome haplotyping of a HapMap trio child : evaluation of Single Individual Haplotyping techniques", Nucleic acids research, 40(5), pp.2041~2053 (2012)
- V. Bansal, "HapCUT : an efficient and accurate algorithm for the haplotype assembly problem", Bioinformatics, 24(16), pp.i153~i159 (2008)
- V. Kuleshov, "Probabilistic single-individual haplotyping", Bioinformatics, 30(17), pp.i379~i385 (2014)
- V. Kuleshov, "Whole-genome haplotyping using long reads and statistical methods", Nature biotechnology, 32(3), pp.261~266 (2014)
- H. Matsumoto, "MixSIH : a mixture model for single individual haplotyping", BMC Genomics, 14(S5) (2013)
- A. Tangherloni, "GenHap : a novel computational method based on genetic algorithms for haplotype assembly", BMC Bioinformatics, 20, pp.172~ (2019)
- 이제근, "Survey of computational haplotype determination methods for single individual", Genes & Genomics, 38(1), pp.1~12 (2016), 한국유전학회[DOI]
- J. C. Na, "PEATH : single-individual haplotyping by a probabilistic evolutionary algorithm with toggling", Bioinformatics, 34(11), pp.1801~1807 (2018)
- B. Ewing, "Base-calling of automated sequencer traces using Phred. I. Accuracy assessment", Genome research, 8(3), pp.175~185 (1998)
- B. Ewing, "Base-calling of automated sequencer traces using phred. II. Error probabilities", Genome research, 8(3), pp.186~194 (1998)