Solving the Haplotype Assembly Problem for Human Using the Improved Branch and Bound Algorithm


KIPS Transactions on Software and Data Engineering, Vol. 2, No. 10, pp. 697-704, Oct. 2013
10.3745/KTSDE.2013.2.10.697,   PDF Download:

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.


Statistics
Show / Hide Statistics

Statistics (Cumulative Counts from September 1st, 2017)
Multiple requests among the same browser session are counted as one view.
If you mouse over a chart, the values of data points will be shown.


Cite this article
[IEEE Style]
M. H. Choi, S. H. Kang, H. S. Lim, "Solving the Haplotype Assembly Problem for Human Using the Improved Branch and Bound Algorithm," KIPS Transactions on Software and Data Engineering, vol. 2, no. 10, pp. 697-704, 2013. DOI: 10.3745/KTSDE.2013.2.10.697.

[ACM Style]
Mun Ho Choi, Seung Ho Kang, and Hyeong Seok Lim. 2013. Solving the Haplotype Assembly Problem for Human Using the Improved Branch and Bound Algorithm. KIPS Transactions on Software and Data Engineering, 2, 10, (2013), 697-704. DOI: 10.3745/KTSDE.2013.2.10.697.