개선된 분기한정 알고리즘을 이용한 인간 유전체의 일배체형 조합문제 해결 = Solving the Haplotype Assembly Problem for Human Using the Improved Branch and Bound Algorithm

다국어 초록 (Multilingual Abstract)

The identification of haplotypes, which encode SNPs in a single chromosome, makes it possible to perform haplotype-based association tests with diseases. Minimum Error Correction model, one of models to computationally assemble a pair of haplotypes for a given organism from Single Nucleotide Polymorphism fragments, has been known to be NP-hard even for gapless cases. In the previous work, an improved branch and bound algorithm was suggested and showed that it is more efficient than naive branch and bound algorithm by performing experiments for Apis mellifera (honeybee) data set. In this paper, to show the extensibility of the algorithm to other organisms we apply the improved branch and bound algorithm to the human data set and confirm the efficiency of the algorithm.

참고문헌 (Reference)

1 "Wikipedia"

2 R. Schwartz, "Theory and Algorithms for the Haplotype Assembly Problem" 10 (10): 23-38, 2010

3 R. Cilibrasi, "The Complexity of the Single Individual SNP Haplotyping Problem" 49 (49): 13-36, 2007

4 X. S. Zang, "Models and algorithms for haplotyping problem" 1 (1): 105-114, 2006

5 Hyeong-Seok Lim, "Individual haplotype assembly of Apis mellifera (honeybee) using a practical branch and bound algorithm" 한국응용곤충학회 15 (15): 375-381, 2012

6 M. J. Daly, "High-resolution haplotype structure in the human genome" 29 : 229-232, 2001

7 R. S. Wang, "Haplotype reconstruction from SNP fragments by minimum error correction" 21 : 2456-2462, 2005

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

9 A. Graça, "Haplotype inference by Pure Parsimony: a survey" 17 : 969-992, 2010

10 S. H. Kang, "HapAssembler: A web server for haplotype assembly from SNP fragments using genetic algorithm" 397 : 340-344, 2010

11 C. Burgtorf, "Clone-based systematic haplotyping (CSH): A procedure for physical haplotyping of whole genomes" 13 : 2717-2724, 2003

12 R. Lippert, "Algorithmic Strategies for the SNPs Haplotype Assembly Problem" 3 (3): 23-31, 2002

13 The International HapMap Consortium, "A second generation human haplotype map of over 3.1 million SNPs" 449 : 851-861, 2007

14 M, Xie, "A practical exact algorithm for the individual haplotyping problem MEC" 72-76, 2008

15 J. Wang, "A Practical Exact Algorithm for the Individual Haplotyping Problem MEC/GI" 56 : 283-296, 2010