{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T06:19:22Z","timestamp":1725517162507},"publisher-location":"Berlin, Heidelberg","reference-count":27,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540852377"},{"type":"electronic","value":"9783540852384"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-85238-4_24","type":"book-chapter","created":{"date-parts":[[2008,8,18]],"date-time":"2008-08-18T15:34:36Z","timestamp":1219073676000},"page":"299-310","source":"Crossref","is-referenced-by-count":2,"title":["Computational Complexity of Perfect-Phylogeny-Related Haplotyping Problems"],"prefix":"10.1007","author":[{"given":"Michael","family":"Elberfeld","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Till","family":"Tantau","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"5","key":"24_CR1","doi-asserted-by":"publisher","first-page":"858","DOI":"10.1089\/cmb.2004.11.858","volume":"11","author":"V. Bafna","year":"2004","unstructured":"Bafna, V., Gusfield, D., Hannenhalli, S., Yooseph, S.: A note on efficient computation of haplotypes via perfect phylogeny. J. Comput. Biol.\u00a011(5), 858\u2013866 (2004)","journal-title":"J. Comput. Biol."},{"issue":"3\u20134","key":"24_CR2","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1089\/10665270360688048","volume":"10","author":"V. Bafna","year":"2003","unstructured":"Bafna, V., Gusfield, D., Lancia, G., Yooseph, S.: Haplotyping as perfect phylogeny: A direct approach. J. Comput. Biol.\u00a010(3\u20134), 323\u2013340 (2003)","journal-title":"J. Comput. Biol."},{"issue":"3","key":"24_CR3","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1007\/BF01374526","volume":"25","author":"G. Buntrock","year":"1992","unstructured":"Buntrock, G., Damm, C., Hertrampf, U., Meinel, C.: Structure and importance of logspace-MOD-classes. Math. Syst. Theor.\u00a025(3), 223\u2013237 (1992)","journal-title":"Math. Syst. Theor."},{"key":"24_CR4","series-title":"Lecture Notes in Bioinformatics","first-page":"128","volume-title":"Algorithms in Bioinformatics","author":"J. Tromp","year":"2005","unstructured":"Tromp, J., Cilibrasi, R., van Iersel, L., Kelk, S.: On the Complexity of Several Haplotyping Problems. In: Casadio, R., Myers, G. (eds.) WABI 2005. LNCS (LNBI), vol.\u00a03692, pp. 128\u2013139. Springer, Heidelberg (2005)"},{"issue":"2","key":"24_CR5","first-page":"111","volume":"7","author":"A.G. Clark","year":"1990","unstructured":"Clark, A.G.: Inference of haplotypes from PCR-amplified samples of diploid populations. J. Mol. Biol. and Evol.\u00a07(2), 111\u2013122 (1990)","journal-title":"J. Mol. Biol. and Evol."},{"key":"24_CR6","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1038\/ng1001-229","volume":"29","author":"M. Daly","year":"2001","unstructured":"Daly, M., Rioux, J., Schaffner, S., Hudson, T., Ladner, E.: High-resolution haplotype structure in the human genome. Nat. Genet.\u00a029, 229\u2013232 (2001)","journal-title":"Nat. Genet."},{"issue":"1","key":"24_CR7","doi-asserted-by":"publisher","first-page":"161","DOI":"10.2307\/1969503","volume":"51","author":"R.P. Dilworth","year":"1950","unstructured":"Dilworth, R.P.: A decomposition theorem for partially ordered sets. Ann. Math.\u00a051(1), 161\u2013166 (1950)","journal-title":"Ann. Math."},{"issue":"2","key":"24_CR8","doi-asserted-by":"publisher","first-page":"522","DOI":"10.1089\/cmb.2006.13.522","volume":"13","author":"Z. Ding","year":"2006","unstructured":"Ding, Z., Filkov, V., Gusfield, D.: A linear-time algorithm for the perfect phylogeny haplotyping (PPH)problem. J. Comput. Biol.\u00a013(2), 522\u2013553 (2006)","journal-title":"J. Comput. Biol."},{"unstructured":"Elberfeld, M., Tantau, T.: Computational complexity of perfect-phylogeny-related haplotyping problems. Tech. Rep. SIIM-TR-A-08-02, Universitat zu Lubeck (2008)","key":"24_CR9"},{"issue":"1","key":"24_CR10","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1142\/S0219720003000174","volume":"1","author":"E. Eskin","year":"2003","unstructured":"Eskin, E., Halperin, E., Karp, R.M.: Efficient reconstruction of haplotype structure via perfect phylogeny. J. Bioinform. and Comput. Biol.\u00a01(1), 1\u201320 (2003)","journal-title":"J. Bioinform. and Comput. Biol."},{"issue":"5","key":"24_CR11","first-page":"921","volume":"12","author":"L. Excoffier","year":"1995","unstructured":"Excoffier, L., Slatkin, M.: Maximum-likelihood estimation of molecular haplotype frequencies in a diploid population. Mol. Biol. and Evol.\u00a012(5), 921\u2013927 (1995)","journal-title":"Mol. Biol. and Evol."},{"key":"24_CR12","doi-asserted-by":"publisher","first-page":"947","DOI":"10.1086\/303069","volume":"67","author":"D. Fallin","year":"2000","unstructured":"Fallin, D., Schork, N.: Accuracy of haplotype frequency estimation for biallelic loci via the expectation-maximation algorithm for unphased diploid genotype data. Am. J. Hum. Genet.\u00a067, 947\u2013959 (2000)","journal-title":"Am. J. Hum. Genet."},{"key":"24_CR13","doi-asserted-by":"publisher","first-page":"831","DOI":"10.1086\/323612","volume":"69","author":"L. Friss","year":"2001","unstructured":"Friss, L., Hudson, R., Bartoszewicz, A., Wall, J., Donfalk, T., Di Rienzo, A.: Gene conversion and differential population histories may explain the contrast between polymorphism and linkage disequilibrium levels. Am. J. Hum. Genet.\u00a069, 831\u2013843 (2001)","journal-title":"Am. J. Hum. Genet."},{"doi-asserted-by":"crossref","unstructured":"Gramm, J., Hartman, T., Nierhoff, T., Sharan, R., Tantau, T.: On the complexity of SNP block partitioning under the perfect phylogeny model. Discrete Math (2008)","key":"24_CR14","DOI":"10.1016\/j.disc.2008.04.002"},{"issue":"6\u20137","key":"24_CR15","doi-asserted-by":"publisher","first-page":"788","DOI":"10.1016\/j.dam.2005.09.020","volume":"155","author":"J. Gramm","year":"2007","unstructured":"Gramm, J., Nierhoff, T., Sharan, R., Tantau, T.: Haplotyping with missing data via perfect path phylogenies. Discrete and Appl. Math.\u00a0155(6\u20137), 788\u2013805 (2007)","journal-title":"Discrete and Appl. Math."},{"issue":"3","key":"24_CR16","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. J. Comput. Biol.\u00a08(3), 305\u2013323 (2001)","journal-title":"J. Comput. Biol."},{"key":"24_CR17","doi-asserted-by":"publisher","first-page":"166","DOI":"10.1145\/565196.565218","volume-title":"Proc. RECOMB 2002","author":"D. Gusfield","year":"2002","unstructured":"Gusfield, D.: Haplotyping as perfect phylogeny: Conceptual framework and efficient solutions. In: Proc. RECOMB 2002, pp. 166\u2013175. ACM Press, New York (2002)"},{"key":"24_CR18","doi-asserted-by":"crossref","first-page":"409","DOI":"10.1093\/oxfordjournals.jhered.a111613","volume":"86","author":"M. Hawley","year":"1995","unstructured":"Hawley, M., Kidd, K.: Haplo: A program using the EM algorithm to estimate the frequency of multi-site haplotypes. J. Hered.\u00a086, 409\u2013441 (1995)","journal-title":"J. Hered."},{"issue":"5530","key":"24_CR19","doi-asserted-by":"publisher","first-page":"582","DOI":"10.1126\/science.293.5530.583b","volume":"293","author":"L. Helmuth","year":"2001","unstructured":"Helmuth, L.: Map of the human genome 3.0. Science\u00a0293(5530), 582\u2013585 (2001)","journal-title":"Science"},{"key":"24_CR20","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0539-5","volume-title":"Descriptive Complexity","author":"N. Immerman","year":"1999","unstructured":"Immerman, N.: Descriptive Complexity. Springer, New York (1999)"},{"issue":"4","key":"24_CR21","doi-asserted-by":"publisher","first-page":"348","DOI":"10.1287\/ijoc.1040.0085","volume":"16","author":"G. Lancia","year":"2004","unstructured":"Lancia, G., Pinotti, M.C., Rizzi, R.: Haplotyping populations by pure parsimony: Complexity of exact and approximation algorithms. INFORMS J. Comput.\u00a016(4), 348\u2013359 (2004)","journal-title":"INFORMS J. Comput."},{"issue":"3","key":"24_CR22","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1016\/j.orl.2005.05.007","volume":"34","author":"G. Lancia","year":"2006","unstructured":"Lancia, G., Rizzi, R.: A polynomial case of the parsimony haplotyping problem. Oper. Res. Lett.\u00a034(3), 289\u2013295 (2006)","journal-title":"Oper. Res. Lett."},{"key":"24_CR23","first-page":"173","volume-title":"Proc. Int. Conf. Adv. in Bioinfor. and Appl.","author":"Y. Liu","year":"2005","unstructured":"Liu, Y., Zhang, C.-Q.: A linear solution for haplotype perfect phylogeny problem. In: Proc. Int. Conf. Adv. in Bioinfor. and Appl., pp. 173\u2013184. World Scientific, Singapore (2005)"},{"issue":"4","key":"24_CR24","doi-asserted-by":"publisher","first-page":"897","DOI":"10.1089\/cmb.2006.13.897","volume":"13","author":"R. Vijaya Satya","year":"2006","unstructured":"Vijaya Satya, R., Mukherjee, A.: An optimal algorithm for perfect phylogeny haplotyping. J. Comput. Biol.\u00a013(4), 897\u2013928 (2006)","journal-title":"J. Comput. Biol."},{"doi-asserted-by":"crossref","unstructured":"Vijaya Satya, R., Mukherjee, A.: The undirected incomplete perfect phylogeny problem. IEEE\/ACM T. Comput. Biol. and Bioinfor (to appear, 2008)","key":"24_CR25","DOI":"10.1109\/TCBB.2007.70218"},{"issue":"3","key":"24_CR26","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1109\/TCBB.2006.40","volume":"3","author":"R. Sharan","year":"2006","unstructured":"Sharan, R., Halld\u00f3rsson, B.V., Istrail, S.: Islands of tractability for parsimony haplotyping. IEEE\/ACM T. Comput. Biol. and Bioinfor.\u00a03(3), 303\u2013311 (2006)","journal-title":"IEEE\/ACM T. Comput. Biol. and Bioinfor."},{"issue":"2","key":"24_CR27","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1109\/TCBB.2007.70232","volume":"5","author":"L. Iersel van","year":"2008","unstructured":"van Iersel, L., Keijsper, J., Kelk, S., Stougie, L.: Shorelines of islands of tractability: Algorithms for parsimony and minimum perfect phylogeny haplotyping problems. IEEE\/ACM T. Comput. Biol. and Bioinfor.\u00a05(2), 301\u2013312 (2008)","journal-title":"IEEE\/ACM T. Comput. Biol. and Bioinfor."}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2008"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-85238-4_24.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,24]],"date-time":"2020-11-24T02:23:25Z","timestamp":1606184605000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-85238-4_24"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540852377","9783540852384"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-85238-4_24","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[]}}