{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T06:13:16Z","timestamp":1725516796820},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540697329"},{"type":"electronic","value":"9783540697336"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-69733-6_29","type":"book-chapter","created":{"date-parts":[[2008,8,12]],"date-time":"2008-08-12T12:07:43Z","timestamp":1218542863000},"page":"287-298","source":"Crossref","is-referenced-by-count":3,"title":["Haplotype Inferring Via Galled-Tree Networks Is NP-Complete"],"prefix":"10.1007","author":[{"given":"Arvind","family":"Gupta","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"J\u00e1n","family":"Ma\u0148uch","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ladislav","family":"Stacho","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xiaohong","family":"Zhao","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"29_CR1","doi-asserted-by":"publisher","first-page":"409","DOI":"10.1007\/s00026-004-0229-z","volume":"8","author":"M. Bordewich","year":"2004","unstructured":"Bordewich, M., Semple, C.: On the Computational Complexity of the Rooted Subtree Prune and Regraft Distance. Annals of Combinatorics\u00a08, 409\u2013423 (2004)","journal-title":"Annals of Combinatorics"},{"key":"29_CR2","first-page":"111","volume":"7","author":"A. Clark","year":"1990","unstructured":"Clark, A.: Inference of Haplotypes from PCR-Amplified Samples of Dipoid Populations. Molecular Biology and Evolution\u00a07, 111\u2013122 (1990)","journal-title":"Molecular Biology and Evolution"},{"key":"29_CR3","doi-asserted-by":"publisher","first-page":"1299","DOI":"10.1038\/nature04226","volume":"437","author":"I.H. Consortium","year":"2005","unstructured":"Consortium, I.H.: A Haplotype Map of the Human Genome. Nature\u00a0437, 1299\u20131320 (2005)","journal-title":"Nature"},{"issue":"2","key":"29_CR4","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., Lander, E.: High-Resolution Haplotype Structure in the Human Genome. Nature Genetics\u00a029(2), 229\u2013232 (2001)","journal-title":"Nature Genetics"},{"key":"29_CR5","doi-asserted-by":"crossref","unstructured":"Gabriel, S., Schaffner, S., Nguyen, H., Moore, J., Roy, J., Blumenstiel, B., Higgins, J., DeFelice, M., Lochner, A., Faggart, M., Liu-Cordero, S., Rotimi, C., Adeyemo, A., Cooper, R., Ward, R., Lander, E., Daly, M., Altshuler, D.: The Structure of Haplotype Blocks in the Human Genome. Science\u00a0296 (2002)","DOI":"10.1126\/science.1069424"},{"key":"29_CR6","doi-asserted-by":"crossref","unstructured":"Gupta, A., Manuch, J., Stacho, L., Zhao, X.: Haplotype Inferring via Galled-Tree Networks Using a Hypergraph Covering Problem for Special Genotype Matrices. Discr. Appl. Math. (to appear)","DOI":"10.1016\/j.dam.2008.06.051"},{"issue":"6","key":"29_CR7","doi-asserted-by":"publisher","first-page":"1309","DOI":"10.1142\/S0219720006002478","volume":"4","author":"A. Gupta","year":"2006","unstructured":"Gupta, A., Manuch, J., Stacho, L., Zhao, X.: Characterization of the Existence of Galled-Tree Networks. J. of Bioinform. and Comp. Biol.\u00a04(6), 1309\u20131328 (2006)","journal-title":"J. of Bioinform. and Comp. Biol."},{"key":"29_CR8","series-title":"Lecture Notes in Bioinformatics","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1007\/978-3-540-72031-7_11","volume-title":"Bioinformatics Research and Applications","author":"A. Gupta","year":"2007","unstructured":"Gupta, A., Manuch, J., Stacho, L., Zhao, X.: Algorithm for Haplotype Inferring via Galled-Tree Networks with Simple Galls (extended abstract). In: Istrail, S., Pevzner, P., Waterman, M. (eds.) ISBRA 2007. LNCS (LNBI), vol.\u00a04463, pp. 121\u2013132. Springer, Heidelberg (2007)"},{"issue":"3","key":"29_CR9","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. Comp. Biology\u00a08(3), 305\u2013323 (2001)","journal-title":"J. Comp. Biology"},{"key":"29_CR10","doi-asserted-by":"crossref","unstructured":"Gusfield, D.: Haplotyping as Perfect Phylogeny: Conceptual Framework and Efficient Solutions. In: Proceedings of the Sixth Annual International Conference on Computational Biology (RECOMB 2002), pp. 166\u2013175 (2002)","DOI":"10.1145\/565196.565218"},{"key":"29_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"144","DOI":"10.1007\/3-540-44888-8_11","volume-title":"Combinatorial Pattern Matching","author":"D. Gusfield","year":"2003","unstructured":"Gusfield, D.: Haplotype Inference by Pure Parsimony. In: Baeza-Yates, R., Ch\u00e1vez, E., Crochemore, M. (eds.) CPM 2003. LNCS, vol.\u00a02676, pp. 144\u2013155. Springer, Heidelberg (2003)"},{"issue":"3","key":"29_CR12","doi-asserted-by":"publisher","first-page":"381","DOI":"10.1016\/j.jcss.2004.12.009","volume":"70","author":"D. Gusfield","year":"2005","unstructured":"Gusfield, D.: Optimal, Efficient Reconstruction of Root-Unknown Phylogenetic Networks with Constrained and Structured Recombination. J. Comput. Syst. Sci.\u00a070(3), 381\u2013398 (2005)","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"29_CR13","doi-asserted-by":"publisher","first-page":"459","DOI":"10.1287\/ijoc.1040.0099","volume":"16","author":"D. Gusfield","year":"2004","unstructured":"Gusfield, D., Eddhu, S., Langley, C.: The Fine Structure of Galls in Phylogenetic Networks. INFORMS Journal on Computing\u00a016(4), 459\u2013469 (2004)","journal-title":"INFORMS Journal on Computing"},{"issue":"1","key":"29_CR14","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1142\/S0219720004000521","volume":"2","author":"D. Gusfield","year":"2004","unstructured":"Gusfield, D., Eddhu, S., Langley, C.: Optimal, Efficient Reconstruction of Phylogenetic Networks with Constrained Recombination. Journal of Bioinformatics and Computational Biology\u00a02(1), 173\u2013213 (2004)","journal-title":"Journal of Bioinformatics and Computational Biology"},{"key":"29_CR15","series-title":"CRC Computer and Information Science Series","first-page":"18","volume-title":"Handbook of Computational Molecular Biology, Chapter Haplotype Inference","author":"D. Gusfield","year":"2005","unstructured":"Gusfield, D., Orzack, S.H.: Handbook of Computational Molecular Biology, Chapter Haplotype Inference. CRC Computer and Information Science Series, p. 18C1C18C28. Chapman & Hall, Boca Raton (2005)"},{"issue":"5530","key":"29_CR16","doi-asserted-by":"publisher","first-page":"583","DOI":"10.1126\/science.293.5530.583b","volume":"293","author":"L. Helmuth","year":"2001","unstructured":"Helmuth, L.: Genome Research: Map of the Human Genome 3.0. Science\u00a0293(5530), 583\u2013585 (2001)","journal-title":"Science"},{"key":"29_CR17","unstructured":"Lancia, G., Pinotti, C., Rizzi, R.: Haplotyping Populations: Complexity and Aproximations. Dit-02-082, University of Trento (2002)"},{"key":"29_CR18","doi-asserted-by":"publisher","first-page":"5926","DOI":"10.1073\/pnas.0936399100","volume":"100","author":"R.D. Mitra","year":"2003","unstructured":"Mitra, R.D., Butty, V.L., Shendure, J., Williams, B.R., Housman, D.E., Church, G.M.: Digital Genotyping and Haplotyping with Polymerase Colonies. Proceedings of the Nationlal Academy of Sciences of the United States of America\u00a0100, 5926\u20135931 (2003)","journal-title":"Proceedings of the Nationlal Academy of Sciences of the United States of America"},{"key":"29_CR19","unstructured":"Papadimitriou, C.H.: Computational Complexity. Addison-Wiesley Publishing Company, Inc. (1994)"},{"issue":"5547","key":"29_CR20","doi-asserted-by":"publisher","first-page":"1719","DOI":"10.1126\/science.1065573","volume":"294","author":"N. Patil","year":"2001","unstructured":"Patil, N., Berno, A., Hinds, D., Barrett, W., Doshi, J., Hacker, C., Kautzer, C., Lee, D., Marjoribanks, C., McDonough, D., Nguyen, B., Norris, M., Sheehan, J., Shen, N., Stern, D., Stokowski, R., Thomas, D., Trulson, M., Vyas, K., Frazer, K., Fodor, S., Cox, D.: Blocks of Limited Haplotype Diversity Revealed by High-Resolution Scanning of Human Chromosome 21. Science\u00a0294(5547), 1719\u20131723 (2001)","journal-title":"Science"},{"issue":"5858","key":"29_CR21","doi-asserted-by":"publisher","first-page":"1842","DOI":"10.1126\/science.318.5858.1842","volume":"318","author":"E. Pennisi","year":"2007","unstructured":"Pennisi, E.: BREAKTHROUGH OF THE YEAR: Human Genetic Variation. Science\u00a0318(5858), 1842\u20131843 (2007)","journal-title":"Science"},{"issue":"2","key":"29_CR22","doi-asserted-by":"publisher","first-page":"186","DOI":"10.1109\/TCBB.2006.15","volume":"3","author":"Y.S. Song","year":"2006","unstructured":"Song, Y.S.: A Concise Necessary and Sufficient Condition for the Existence of a Galled-Tree. IEEE\/ACM Transaction on Computational Biology and Bioinformatics\u00a03(2), 186\u2013191 (2006)","journal-title":"IEEE\/ACM Transaction on Computational Biology and Bioinformatics"},{"key":"29_CR23","series-title":"Lecture Notes in Bioinformatics","doi-asserted-by":"publisher","first-page":"152","DOI":"10.1007\/11557067_13","volume-title":"Algorithms in Bioinformatics","author":"Y.S. Song","year":"2005","unstructured":"Song, Y.S., Wu, Y., Gusfield, D.: Algorithms for Imperfect Phylogeny Haplotyping (IPPH) with a Single Homoplasy or Recombination Event. In: Casadio, R., Myers, G. (eds.) WABI 2005. LNCS (LNBI), vol.\u00a03692, pp. 152\u2013164. Springer, Heidelberg (2005)"},{"key":"29_CR24","doi-asserted-by":"publisher","first-page":"1591","DOI":"10.1101\/gr.4413105","volume":"15","author":"G. Thorisson","year":"2005","unstructured":"Thorisson, G., Smith, A., Krishnan, L., Stein, L.: The International HapMap Project Web Site. Genome Research\u00a015, 1591\u20131593 (2005)","journal-title":"Genome Research"},{"issue":"1","key":"29_CR25","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1089\/106652701300099119","volume":"8","author":"L. Wang","year":"2001","unstructured":"Wang, L., Zhang, K., Zhang, L.: Perfect Phylogenetic Networks with Recombination. Journal of Computational Biology\u00a08(1), 69\u201378 (2001)","journal-title":"Journal of Computational Biology"}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-69733-6_29.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,3]],"date-time":"2021-05-03T00:44:49Z","timestamp":1620002689000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-69733-6_29"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540697329","9783540697336"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-69733-6_29","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[]}}