loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
2008 International Conference on BioMedical Engineering and Informatics
A Practical Exact Algorithm for the Individual Haplotyping Problem MEC
May 27-May 30
ISBN: 978-0-7695-3118-2
The individual haplotyping problem MEC is a computational problem that, given a set of DNA sequence fragment data of an individual, induces the corresponding haplotypes by changing the smallest number of SNPs. MEC problem is NP-hard and there has been no practical exact algorithm to solve the problem. In DNA sequencing experiments, due to technical limits, the maximum length of a fragment sequenced directly is about 1kb. In consequence, the maximum number k of SNP sites that a fragment covers is usually small. Based on the observation above, the current paper introduces a new parameterized algorithm of runningtime O(m k 3^{k}+mlogm+mk), where m is the number of fragments. The algorithm solves the MEC problem efficiently even if the number of fragments and SNPs are large, and is practical in real biological applications.
Index Terms:
SNP (single-nucleotide polymorphism), haplotype, MEC (Minimum Error Correction), NP-hardness
Citation:
Minzhu Xie, Jianxin Wang, Jianer Chen, "A Practical Exact Algorithm for the Individual Haplotyping Problem MEC," bmei, vol. 1, pp.72-76, 2008 International Conference on BioMedical Engineering and Informatics, 2008
Usage of this product signifies your acceptance of the Terms of Use.