Research on parameterized algorithms of the individual haplotyping problem. TeX Export

@article{citeulike:1557158, abstract = {The individual haplotyping problem is a computing problem of reconstructing two haplotypes for an individual based on several optimal criteria from one's fragments sequencing data. This paper is based on the fact that the length of a fragment and the number of the fragments covering a SNP (single nucleotide polymorphism) site are both very small compared with the length of a sequenced region and the total number of the fragments and introduces the parameterized haplotyping problems. With m fragments whose maximum length is k(1), n SNP sites and the number of the fragments covering a SNP site no more than k(2), our algorithms can solve the gapless MSR (Minimum SNP Removal) and MFR (Minimum Fragment Removal) problems in the time complexity O(nk(1)k(2) + m log m + nk(2) + mk(1)) and \$O(mk\_{2};{2} + mk\_{1}k\_{2} + m \log m + nk\_{2} + mk\_{1})\$ respectively. Since, the value of k(1) and k(2) are both small (about 10) in practice, our algorithms are more efficient and applicable compared with the algorithms of V. Bafna et al. of time complexity O(mn(2)) and O(m(2)n + m(3)), respectively.}, address = {School of Information Science and Engineering, Central South University, Changsha, Hunan Province 410083, China. xieminzhu@hotmail.com.}, author = {Xie, M. and Chen, J. and Wang, J.}, citeulike-article-id = {1557158}, citeulike-linkout-0 = {http://view.ncbi.nlm.nih.gov/pubmed/17688317}, citeulike-linkout-1 = {http://www.hubmed.org/display.cgi?uids=17688317}, issn = {0219-7200}, journal = {J Bioinform Comput Biol}, keywords = {haplotype}, month = {June}, number = {3}, pages = {795--816}, posted-at = {2007-08-13 09:27:25}, priority = {2}, title = {Research on parameterized algorithms of the individual haplotyping problem.}, url = {http://view.ncbi.nlm.nih.gov/pubmed/17688317}, volume = {5}, year = {2007} }

TY - JOUR ID - citeulike:1557158 L3 - citeulike-article-id:1557158 N2 - The individual haplotyping problem is a computing problem of reconstructing two haplotypes for an individual based on several optimal criteria from one's fragments sequencing data. This paper is based on the fact that the length of a fragment and the number of the fragments covering a SNP (single nucleotide polymorphism) site are both very small compared with the length of a sequenced region and the total number of the fragments and introduces the parameterized haplotyping problems. With m fragments whose maximum length is k(1), n SNP sites and the number of the fragments covering a SNP site no more than k(2), our algorithms can solve the gapless MSR (Minimum SNP Removal) and MFR (Minimum Fragment Removal) problems in the time complexity O(nk(1)k(2) + m log m + nk(2) + mk(1)) and $O(mk_{2};{2} + mk_{1}k_{2} + m \log m + nk_{2} + mk_{1})$ respectively. Since, the value of k(1) and k(2) are both small (about 10) in practice, our algorithms are more efficient and applicable compared with the algorithms of V. Bafna et al. of time complexity O(mn(2)) and O(m(2)n + m(3)), respectively. IS - 3 JF - J Bioinform Comput Biol SN - 0219-7200 AD - School of Information Science and Engineering, Central South University, Changsha, Hunan Province 410083, China. xieminzhu@hotmail.com. EP - 816 TI - Research on parameterized algorithms of the individual haplotyping problem. VL - 5 SP - 795 KW - haplotype AU - Xie, M AU - Chen, J AU - Wang, J PY - 2007/06// UR - http://view.ncbi.nlm.nih.gov/pubmed/17688317 ER -