{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,19]],"date-time":"2025-03-19T11:45:56Z","timestamp":1742384756631},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540395836"},{"type":"electronic","value":"9783540395843"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11851561_8","type":"book-chapter","created":{"date-parts":[[2006,9,22]],"date-time":"2006-09-22T08:49:41Z","timestamp":1158914981000},"page":"80-91","source":"Crossref","is-referenced-by-count":3,"title":["Beaches of Islands of Tractability: Algorithms for Parsimony and Minimum Perfect Phylogeny Haplotyping Problems"],"prefix":"10.1007","author":[{"given":"Leo","family":"van Iersel","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Judith","family":"Keijsper","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Steven","family":"Kelk","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Leen","family":"Stougie","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"8_CR1","doi-asserted-by":"crossref","unstructured":"Alimonti, P., Kann, V.: Hardness of approximating problems on cubic graphs. In: Proc. of the 3rd Italian Conf. on Algorithms and Complexity, pp. 288\u2013298 (1997)","DOI":"10.1007\/3-540-62592-5_80"},{"issue":"5","key":"8_CR2","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. of Computational Biology\u00a011(5), 858\u2013866 (2004)","journal-title":"J. of Computational Biology"},{"key":"8_CR3","first-page":"1","volume-title":"Graph theory and sparse matrix computation","author":"J.R.S. Blair","year":"1993","unstructured":"Blair, J.R.S., Peyton, B.: An introduction to chordal graphs and clique trees. In: Graph theory and sparse matrix computation, pp. 1\u201329. Springer, Heidelberg (1993)"},{"issue":"6","key":"8_CR4","doi-asserted-by":"publisher","first-page":"675","DOI":"10.1007\/BF02945456","volume":"18","author":"P. Bonizzoni","year":"2003","unstructured":"Bonizzoni, P., Vedova, G.D., Dondi, R., Li, J.: The haplotyping problem: an overview of computational models and solutions. J. of Computer Science and Technology\u00a018(6), 675\u2013688 (2003)","journal-title":"J. of Computer Science and Technology"},{"key":"8_CR5","doi-asserted-by":"crossref","unstructured":"Brown, D., Harrower, I.: Integer programming approaches to haplotype inference by pure parsimony. IEEE\/ACM Transactions on Computational Biology and Informatics\u00a03(2) (2006)","DOI":"10.1109\/TCBB.2006.24"},{"key":"8_CR6","series-title":"Lecture Notes in Bioinformatics","doi-asserted-by":"publisher","first-page":"128","DOI":"10.1007\/11557067_11","volume-title":"Algorithms in Bioinformatics","author":"R. Cilibrasi","year":"2005","unstructured":"Cilibrasi, R., Iersel, L.J.J., van Kelk, S.M., Tromp, J.: 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":"8_CR7","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. of Computational Biology\u00a013(2), 522\u2013533 (2006)","journal-title":"J. of Computational Biology"},{"key":"8_CR8","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511574931","volume-title":"Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology","author":"D. Gusfield","year":"1997","unstructured":"Gusfield, D.: Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology. Cambridge University Press, Cambridge (1997)"},{"key":"8_CR9","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1002\/net.3230210104","volume":"21","author":"D. Gusfield","year":"1991","unstructured":"Gusfield, D.: Efficient algorithms for inferring evolutionary history. Networks\u00a021, 19\u201328 (1991)","journal-title":"Networks"},{"key":"8_CR10","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)"},{"key":"8_CR11","doi-asserted-by":"crossref","unstructured":"Halld\u00f3rsson, B.V., Bafna, V., Edwards, N., Lippert, R., Yooseph, S., Istrail, S.: A survey of computational methods for determining haplotypes. In: Proc. DIMACS\/RECOMB Satellite Workshop: Computational Methods for SNPs and Haplotype Inference, pp. 26\u201347 (2004)","DOI":"10.1007\/978-3-540-24719-7_3"},{"key":"8_CR12","unstructured":"Iersel, L.J.J., van Keijsper, J.C.M., Kelk, S.M., Stougie, L.: Beaches of islands of tractability: Algorithms for parsimony and minimum perfect phylogeny haplotyping problems, technical report (2006), http:\/\/www.win.tue.nl\/bs\/spor\/2006-09.pdf"},{"issue":"4","key":"8_CR13","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., Rizzi, R.: Haplotyping populations by pure parsimony: complexity of exact and approximation algorithms. INFORMS J. on Computing\u00a016(4), 348\u2013359 (2004)","journal-title":"INFORMS J. on Computing"},{"issue":"3","key":"8_CR14","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. Operations Research Letters\u00a034(3), 289\u2013295 (2006)","journal-title":"Operations Research Letters"},{"key":"8_CR15","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","volume":"43","author":"C.H. Papadimitriou","year":"1991","unstructured":"Papadimitriou, C.H., Yannakakis, M.: Optimization, approximation, and complexity classes. J. Comput. System Sci.\u00a043, 425\u2013440 (1991)","journal-title":"J. Comput. System Sci."},{"key":"8_CR16","doi-asserted-by":"publisher","first-page":"266","DOI":"10.1137\/0205021","volume":"5","author":"D.J. Rose","year":"1976","unstructured":"Rose, D.J., Tarjan, R.E., Lueker, G.S.: Algorithmic aspects of vertex elimination on graphs. SIAM J. Comput.\u00a05, 266\u2013283 (1976)","journal-title":"SIAM J. Comput."},{"key":"8_CR17","unstructured":"Sharan, R., Halld\u00f3rsson, B.V., Istrail, S.: Islands of tractability for parsimony haplotyping. IEEE\/ACM Transactions on Computational Biology and Bioinformatics (to appear)"},{"key":"8_CR18","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 single haploplasy or recombination event. In: Casadio, R., Myers, G. (eds.) WABI 2005. LNCS (LNBI), vol.\u00a03692, pp. 152\u2013164. Springer, Heidelberg (2005)"},{"key":"8_CR19","unstructured":"VijayaSatya, R., Mukherjee, A.: An optimal algorithm for perfect phylogeny haplotyping. J. of Computational Biology (to appear)"},{"key":"8_CR20","doi-asserted-by":"publisher","first-page":"105","DOI":"10.2174\/157489306775330570","volume":"1","author":"X.-S. Zhang","year":"2006","unstructured":"Zhang, X.-S., Wang, R.-S., Wu, L.-Y., Chen, L.: Models and Algorithms for Haplotyping Problem. Current Bioinformatics\u00a01, 105\u2013114 (2006)","journal-title":"Current Bioinformatics"}],"container-title":["Lecture Notes in Computer Science","Algorithms in Bioinformatics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11851561_8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,21]],"date-time":"2019-04-21T04:38:07Z","timestamp":1555821487000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11851561_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540395836","9783540395843"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/11851561_8","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2006]]}}}