{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,9,5]],"date-time":"2023-09-05T05:06:41Z","timestamp":1693890401178},"reference-count":24,"publisher":"Springer Science and Business Media LLC","issue":"S17","content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["BMC Bioinformatics"],"published-print":{"date-parts":[[2012,12]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:sec>\n            <jats:title>Background<\/jats:title>\n            <jats:p>When studying genetic diseases in which genetic variations are passed on to offspring, the ability to distinguish between paternal and maternal alleles is essential. Determining haplotypes from genotype data is called haplotype inference. Most existing computational algorithms for haplotype inference have been designed to use genotype data collected from individuals in the form of a pedigree. A haplotype is regarded as a hereditary unit and therefore input pedigrees are preferred that are free of mutational events and have a minimum number of genetic recombinational events. These ideas motivated the zero-recombinant haplotype configuration (ZRHC) problem, which strictly follows the Mendelian law of inheritance, namely that one haplotype of each child is inherited from the father and the other haplotype is inherited from the mother, both without any mutation. So far no linear-time algorithm for ZRHC has been proposed for general pedigrees, even though the number of mating loops in a human pedigree is usually very small and can be regarded as constant.<\/jats:p>\n          <\/jats:sec>\n          <jats:sec>\n            <jats:title>Results<\/jats:title>\n            <jats:p>Given a pedigree with <jats:italic>n<\/jats:italic> individuals, <jats:italic>m<\/jats:italic> marker loci, and <jats:italic>k<\/jats:italic> mating loops, we proposed an algorithm that can provide a general solution to the zero-recombinant haplotype configuration problem in <jats:italic>O<\/jats:italic>(<jats:italic>kmn<\/jats:italic> + <jats:italic>k<\/jats:italic>\n              <jats:sup>2<\/jats:sup>\n              <jats:italic>m<\/jats:italic>) time. In addition, this algorithm can be modified to detect inconsistencies within the genotype data without loss of efficiency. The proposed algorithm was subject to 12000 experiments to verify its performance using different (<jats:italic>n, m<\/jats:italic>) combinations. The value of <jats:italic>k<\/jats:italic> was uniformly distributed between zero and six throughout all experiments. The experimental results show a great linearity in terms of execution time in relation to input size when both <jats:italic>n<\/jats:italic> and <jats:italic>m<\/jats:italic> are larger than 100. For those experiments where <jats:italic>n<\/jats:italic> or <jats:italic>m<\/jats:italic> are less than 100, the proposed algorithm runs very fast, in thousandth to hundredth of a second, on a personal desktop computer.<\/jats:p>\n          <\/jats:sec>\n          <jats:sec>\n            <jats:title>Conclusions<\/jats:title>\n            <jats:p>We have developed the first deterministic linear-time algorithm for the zero-recombinant haplotype configuration problem. Our experimental results demonstrated the linearity of its execution time in relation to the input size. The proposed algorithm can be modified to detect inconsistency within the genotype data without loss of efficiency and is expected to be able to handle recombinant and missing data with further extension.<\/jats:p>\n          <\/jats:sec>","DOI":"10.1186\/1471-2105-13-s17-s19","type":"journal-article","created":{"date-parts":[[2012,12,13]],"date-time":"2012-12-13T11:15:52Z","timestamp":1355397352000},"update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["A linear-time algorithm for reconstructing zero-recombinant haplotype configuration on a pedigree"],"prefix":"10.1186","volume":"13","author":[{"given":"En-Yu","family":"Lai","sequence":"first","affiliation":[]},{"given":"Wei-Bung","family":"Wang","sequence":"additional","affiliation":[]},{"given":"Tao","family":"Jiang","sequence":"additional","affiliation":[]},{"given":"Kun-Pin","family":"Wu","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2012,12,13]]},"reference":[{"issue":"6","key":"5483_CR1","doi-asserted-by":"publisher","first-page":"1434","DOI":"10.1086\/340610","volume":"70","author":"D Qian","year":"2002","unstructured":"Qian D, Beckmann L: Minimum-recombinant haplotyping in pedigrees. The American Journal of Human Genetics. 2002, 70 (6): 1434-1445. 10.1086\/340610.","journal-title":"The American Journal of Human Genetics"},{"issue":"2","key":"5483_CR2","doi-asserted-by":"publisher","first-page":"1101","DOI":"10.1534\/genetics.107.074047","volume":"177","author":"CA Albers","year":"2007","unstructured":"Albers CA, Heskes T, Kappen HJ: Haplotype inference in general pedigrees using the cluster variation method. Genetics. 2007, 177 (2): 1101-1116. 10.1534\/genetics.107.074047.","journal-title":"Genetics"},{"key":"5483_CR3","first-page":"985","volume-title":"Proceedings of the International Conference on Computational Science (ICCS)","author":"FYL Chin","year":"2005","unstructured":"Chin FYL, Zhang Q, Shen H: k-recombination haplotype inference in pedigrees. Proceedings of the International Conference on Computational Science (ICCS). 2005, Springer-Verlag, Berlin, 985-993."},{"key":"5483_CR4","first-page":"197","volume-title":"Proceedings of the 7th Annual Conference on Research in Computational Molecular Biology (RECOMB)","author":"J Li","year":"2003","unstructured":"Li J, Jiang T: Efficient rule-based haplotyping algorithms for pedigree data. Proceedings of the 7th Annual Conference on Research in Computational Molecular Biology (RECOMB). 2003, ACM, New York, 197-206."},{"key":"5483_CR5","first-page":"20","volume-title":"Proceedings of the 8th Annual Conference on Research in Computational Molecular Biology (RECOMB)","author":"J Li","year":"2004","unstructured":"Li J, Jiang T: An exact solution for finding minimum recombinant haplotype configurations on pedigrees with missing data by integer linear programming. Proceedings of the 8th Annual Conference on Research in Computational Molecular Biology (RECOMB). 2004, ACM, New York, 20-29."},{"issue":"6","key":"5483_CR6","doi-asserted-by":"publisher","first-page":"719","DOI":"10.1089\/cmb.2005.12.719","volume":"12","author":"J Li","year":"2005","unstructured":"Li J, Jiang T: Computing the minimum recombinant haplotype configuration from incomplete genotype data on a pedigree by integer linear programming. Journal of Computational Biology. 2005, 12 (6): 719-739. 10.1089\/cmb.2005.12.719.","journal-title":"Journal of Computational Biology"},{"key":"5483_CR7","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1007\/978-1-4612-0751-1_6","volume-title":"Genetic Mapping and DNA Sequencing, Volume 81 of IMA Volumes in Mathematics and its Applications","author":"E Sobel","year":"1996","unstructured":"Sobel E, Lange K, O'Connell JR, Weeks DE: Haplotyping algorithms. Genetic Mapping and DNA Sequencing, Volume 81 of IMA Volumes in Mathematics and its Applications. Edited by: Speed T, Waterman MS. 1996, Springer-Verlag, 89-110."},{"key":"5483_CR8","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1159\/000022890","volume":"50","author":"P Tapadar","year":"2000","unstructured":"Tapadar P, Ghosh S, Majumder PP: Haplotyping in pedigrees via a genetic algorithm. Human Heredity. 2000, 50: 43-56. 10.1159\/000022890.","journal-title":"Human Heredity"},{"key":"5483_CR9","doi-asserted-by":"publisher","first-page":"64","DOI":"10.1002\/1098-2272(2000)19:1+<::AID-GEPI10>3.0.CO;2-G","volume":"19","author":"JR O'Connell","year":"2000","unstructured":"O'Connell JR: Zero-recombinant haplotyping: Applications to fine mapping using SNPs. Genetic Epidemiology. 2000, 19: 64-70. 10.1002\/1098-2272(200007)19:1<64::AID-GEPI5>3.0.CO;2-E.","journal-title":"Genetic Epidemiology"},{"issue":"6","key":"5483_CR10","doi-asserted-by":"publisher","first-page":"2179","DOI":"10.1137\/080680990","volume":"38","author":"MY Chan","year":"2009","unstructured":"Chan MY, Chan WT, Chin FYL, Fung SPY, Kao MY: Linear-time haplotype inference on pedigrees without recombinations and mating loops. SIAM J Comput. 2009, 38 (6): 2179-2197. 10.1137\/080680990.","journal-title":"SIAM J Comput"},{"key":"5483_CR11","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1142\/9781848162648_0026","volume-title":"7th Annual International conference on Computational Systems Bioinformatics","author":"X Li","year":"2008","unstructured":"Li X, Li J: Efficient haplotype inference from pedigrees with missing data using linear systems with disjoint-set data structure. 7th Annual International conference on Computational Systems Bioinformatics. 2008, 297-308."},{"key":"5483_CR12","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1007\/s10878-008-9180-y","volume":"19","author":"L Liu","year":"2008","unstructured":"Liu L, Jiang T: A linear-time algorithm for reconstructing zero-recombinant haplotype configuration on pedigrees without mating loops. Journal of Combinatorial Optimization. 2008, 19: 217-240.","journal-title":"Journal of Combinatorial Optimization"},{"issue":"3","key":"5483_CR13","doi-asserted-by":"publisher","first-page":"1757","DOI":"10.1534\/genetics.105.047134","volume":"172","author":"E Baruch","year":"2006","unstructured":"Baruch E, Weller JI, Cohen-Zinder M, Ron M, Seroussi E: Efficient inference of haplotypes from genotypes on a large animal pedigree. Genetics. 2006, 172 (3): 1757-1765.","journal-title":"Genetics"},{"issue":"10","key":"5483_CR14","doi-asserted-by":"publisher","first-page":"1451","DOI":"10.1089\/cmb.2009.0133","volume":"17","author":"DD Doan","year":"2010","unstructured":"Doan DD, Evans PA, Horton JD: A near-linear time algorithm for haplotype determination on general pedigrees. J Comput Biol. 2010, 17 (10): 1451-65. 10.1089\/cmb.2009.0133. [http:\/\/www.biomedsearch.com\/nih\/near-linear-time-algorithm-haplotype\/20937017.html]","journal-title":"J Comput Biol"},{"key":"5483_CR15","first-page":"353","volume-title":"CPM 2009, LNCS 5577","author":"WB Wang","year":"2009","unstructured":"Wang WB, Jiang T: Efficient inference of haplotypes from genotypes on a pedigree with mutations and missing alleles. CPM 2009, LNCS 5577. Edited by: Kucherov G, Ukkonen E. 2009, Springer-Verlag Berlin Heidelberg, 353-367."},{"key":"5483_CR16","doi-asserted-by":"publisher","first-page":"2198","DOI":"10.1137\/070687591","volume":"38","author":"J Xiao","year":"2009","unstructured":"Xiao J, Liu L, Xia L, Jiang T: Efficient algorithms for reconstructing zero-recombinant haplotypes on a pedigree based on fast elimination of redundant linear equations. SIAM J Comput. 2009, 38: 2198-2219. 10.1137\/070687591.","journal-title":"SIAM J Comput"},{"key":"5483_CR17","doi-asserted-by":"publisher","first-page":"90","DOI":"10.1093\/bioinformatics\/bth388","volume":"21","author":"K Zhang","year":"2005","unstructured":"Zhang K, Sun F, Zhao H: HAPLORE: a program for haplotype reconstruction in general pedigrees without recombination. Bioinformatics. 2005, 21: 90-103. 10.1093\/bioinformatics\/bth388.","journal-title":"Bioinformatics"},{"issue":"3","key":"5483_CR18","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1089\/10665270152530863","volume":"8","author":"D Gusfield","year":"2001","unstructured":"Gusfield D: Inference of haplotypes from samples of diploid populations: complexity and algorithms. Journal of Computational Biology. 2001, 8 (3): 305-323. 10.1089\/10665270152530863.","journal-title":"Journal of Computational Biology"},{"key":"5483_CR19","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1086\/338446","volume":"70","author":"T Niu","year":"2002","unstructured":"Niu T, Qin ZS, Xu X, Liu JS: Bayesian haplotype inference for multiple linked single-nucleotide polymorphisms. The American Journal of Human Genetics. 2002, 70: 157-169. 10.1086\/338446.","journal-title":"The American Journal of Human Genetics"},{"issue":"4","key":"5483_CR20","doi-asserted-by":"publisher","first-page":"978","DOI":"10.1086\/319501","volume":"68","author":"M Stephens","year":"2001","unstructured":"Stephens M, Smith NJ, Donnelly P: A new statistical method for haplotype reconstruction from population data. The American Journal of Human Genetics. 2001, 68 (4): 978-989. 10.1086\/319501.","journal-title":"The American Journal of Human Genetics"},{"key":"5483_CR21","doi-asserted-by":"publisher","first-page":"74","DOI":"10.1002\/gepi.10195","volume":"24","author":"S Wang","year":"2003","unstructured":"Wang S, Kidd KK, Zhao H: On the use of DNA pooling to estimate haplotype frequencies. Genetic Epidemiology. 2003, 24: 74-82. 10.1002\/gepi.10195.","journal-title":"Genetic Epidemiology"},{"key":"5483_CR22","doi-asserted-by":"publisher","first-page":"7225","DOI":"10.1073\/pnas.1237858100","volume":"100","author":"Y Yang","year":"2002","unstructured":"Yang Y, Zhang J, Hoh J, Matsuda F, Xu P, Lathrop M, Ott J: Efficiency of single-nucleotide polymorphism haplotype estimation from pooled DNA. Proceedings of the National Academy of Science of the United States of America. 2002, 100: 7225-7230.","journal-title":"Proceedings of the National Academy of Science of the United States of America"},{"key":"5483_CR23","doi-asserted-by":"publisher","first-page":"703","DOI":"10.1038\/nrg3054","volume":"12","author":"SR Browning","year":"2011","unstructured":"Browning SR, Browning BL: Haplotype phasing: existing methods and new developments. Nature Reviews Genetics. 2011, 12: 703-714. [http:\/\/www.nature.com\/nrg\/journal\/v12\/n10\/full\/nrg3054.html]","journal-title":"Nature Reviews Genetics"},{"issue":"4","key":"5483_CR24","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1093\/imammb\/21.4.335","volume":"21","author":"A Thomas","year":"2004","unstructured":"Thomas A, Cannings C: Simulating realistic zero loop pedigrees using a bipartite Prufer code and graphical modelling. Math Med Biol. 2004, 21 (4): 335-45. 10.1093\/imammb\/21.4.335. [http:\/\/www.biomedsearch.com\/nih\/Simulating-realistic-zero-loop-pedigrees\/15567888.html]","journal-title":"Math Med Biol"}],"container-title":["BMC Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/1471-2105-13-S17-S19.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,9,1]],"date-time":"2021-09-01T21:06:57Z","timestamp":1630530417000},"score":1,"resource":{"primary":{"URL":"https:\/\/bmcbioinformatics.biomedcentral.com\/articles\/10.1186\/1471-2105-13-S17-S19"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,12]]},"references-count":24,"journal-issue":{"issue":"S17","published-print":{"date-parts":[[2012,12]]}},"alternative-id":["5483"],"URL":"https:\/\/doi.org\/10.1186\/1471-2105-13-s17-s19","relation":{},"ISSN":["1471-2105"],"issn-type":[{"value":"1471-2105","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,12]]},"assertion":[{"value":"13 December 2012","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"S19"}}