earticle

영어

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.

한국어

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