{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,10]],"date-time":"2026-04-10T03:23:29Z","timestamp":1775791409119,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":31,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642401923","type":"print"},{"value":"9783642401930","type":"electronic"}],"license":[{"start":{"date-parts":[[2013,10,10]],"date-time":"2013-10-10T00:00:00Z","timestamp":1381363200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2013,10,10]],"date-time":"2013-10-10T00:00:00Z","timestamp":1381363200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-642-40193-0_4","type":"book-chapter","created":{"date-parts":[[2013,12,23]],"date-time":"2013-12-23T13:11:16Z","timestamp":1387804276000},"page":"67-83","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["When and How the Perfect Phylogeny Model Explains Evolution"],"prefix":"10.1007","author":[{"given":"Paola","family":"Bonizzoni","sequence":"first","affiliation":[]},{"given":"Anna Paola","family":"Carrieri","sequence":"additional","affiliation":[]},{"given":"Gianluca Della","family":"Vedova","sequence":"additional","affiliation":[]},{"given":"Riccardo","family":"Dondi","sequence":"additional","affiliation":[]},{"given":"Teresa M.","family":"Przytycka","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2013,10,10]]},"reference":[{"issue":"6","key":"4_CR1","doi-asserted-by":"publisher","first-page":"1216","DOI":"10.1137\/S0097539793244587","volume":"23","author":"R. Agarwala","year":"1994","unstructured":"R.\u00a0Agarwala, D.\u00a0Fernandez-Baca, A polynomial-time algorithm for the perfect phylogeny problem when the number of character states is fixed. SIAM J. Comput. 23(6), 1216\u20131224 (1994)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"4_CR2","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1007\/s00453-007-0094-3","volume":"48","author":"P. Bonizzoni","year":"2007","unstructured":"P.\u00a0Bonizzoni, A linear time algorithm for the Perfect Phylogeny Haplotype problem. Algorithmica 48(3), 267\u2013285 (2007)","journal-title":"Algorithmica"},{"issue":"6","key":"4_CR3","doi-asserted-by":"publisher","first-page":"675","DOI":"10.1007\/BF02945456","volume":"18","author":"P. Bonizzoni","year":"2003","unstructured":"P.\u00a0Bonizzoni, G.\u00a0Della\u00a0Vedova, R.\u00a0Dondi, J.\u00a0Li, The haplotyping problem: an overview of computational models and solutions. J. Comput. Sci. Technol. 18(6), 675\u2013688 (2003)","journal-title":"J. Comput. Sci. Technol."},{"key":"4_CR4","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1016\/j.tcs.2012.05.035","volume":"454","author":"P. Bonizzoni","year":"2012","unstructured":"P.\u00a0Bonizzoni, C.\u00a0Braghin, R.\u00a0Dondi, G.\u00a0Trucco, The binary persistent perfect phylogeny. Theor. Comput. Sci. 454, 51\u201363 (2012)","journal-title":"Theor. Comput. Sci."},{"key":"4_CR5","doi-asserted-by":"publisher","first-page":"311","DOI":"10.2307\/2406441","volume":"19","author":"J. Camin","year":"1965","unstructured":"J.\u00a0Camin, R.\u00a0Sokal, A method for deducting branching sequences in phylogeny. Evolution 19, 311\u2013326 (1965)","journal-title":"Evolution"},{"issue":"3 Pt 1","key":"4_CR6","first-page":"233","volume":"19","author":"L.L. Cavalli-Sforza","year":"1967","unstructured":"L.L. Cavalli-Sforza, A.W.F. Edwards, Phylogenetic analysis. Models and estimation procedures. Am. J. Hum. Genet. 19(3 Pt 1), 233 (1967)","journal-title":"Phylogenetic analysis. Models and estimation procedures. Am. J. Hum. Genet."},{"issue":"2","key":"4_CR7","doi-asserted-by":"publisher","first-page":"522","DOI":"10.1089\/cmb.2006.13.522","volume":"13","author":"Z. Ding","year":"2006","unstructured":"Z.\u00a0Ding, V.\u00a0Filkov, D.\u00a0Gusfield, A linear time algorithm for Perfect Phylogeny Haplotyping (pph) problem. J. Comput. Biol. 13(2), 522\u2013553 (2006)","journal-title":"J. Comput. Biol."},{"issue":"3","key":"4_CR8","doi-asserted-by":"publisher","first-page":"125","DOI":"10.2307\/4444260","volume":"35","author":"T. Dobzhansky","year":"1973","unstructured":"T.\u00a0Dobzhansky, Nothing in biology makes sense except in the light of evolution. Am. Biol. Teach. 35(3), 125\u2013129 (1973)","journal-title":"Am. Biol. Teach."},{"key":"4_CR9","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity","author":"R.G. Downey","year":"1999","unstructured":"R.G. Downey, M.R. Fellows, Parameterized Complexity, Monographs in Computer Science, (Springer-Verlag, New York, 1999). ISBN 978-0-387-94883-6","ISBN":"https:\/\/id.crossref.org\/isbn\/9780387948836"},{"key":"4_CR10","first-page":"553","volume":"18","author":"A.W.F. Edwards","year":"1963","unstructured":"A.W.F. Edwards, L.L. Cavalli-Sforza, The reconstruction of evolution. Heredity 18, 553 (1963)","journal-title":"Heredity"},{"key":"4_CR11","volume-title":"Inferring Phylogenies","author":"J. Felsenstein","year":"2004","unstructured":"J.\u00a0Felsenstein, Inferring Phylogenies (Sinauer Associates, Sunderland, 2004)"},{"key":"4_CR12","doi-asserted-by":"publisher","first-page":"351","DOI":"10.1023\/B:ORDE.0000034609.99940.fb","volume":"20","author":"S. Felsner","year":"2003","unstructured":"S.\u00a0Felsner, V.\u00a0Raghavan, J.\u00a0Spinrad, Recognition algorithms for orders of small width and graphs of small Dilworth number. Order 20, 351\u2013364 (2003)","journal-title":"Order"},{"issue":"5","key":"4_CR13","doi-asserted-by":"publisher","first-page":"1115","DOI":"10.1137\/S0097539799350839","volume":"32","author":"D. Fernandez-Baca","year":"2003","unstructured":"D.\u00a0Fernandez-Baca, J.\u00a0Lagergren, A polynomial-time algorithm for near-perfect phylogeny. SIAM J. Comput. 32(5), 1115\u20131127 (2003)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"4_CR14","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1016\/S0196-8858(82)80004-3","volume":"3","author":"L. Foulds","year":"1982","unstructured":"L.\u00a0Foulds, R.\u00a0Graham, The Steiner problem in phylogeny is NP-complete. Adv. Appl. Math. 3(1), 43\u201349 (1982)","journal-title":"Adv. Appl. Math."},{"key":"4_CR15","volume-title":"Computer and Intractability: A Guide to the Theory of NP-Completeness","author":"M. Garey","year":"1979","unstructured":"M.\u00a0Garey, D.\u00a0Johnson, Computer and Intractability: A Guide to the Theory of NP-Completeness (W.H. Freeman, San Francisco, 1979)"},{"key":"4_CR16","volume-title":"Algorithmic Graph Theory and Perfect Graphs","author":"M. Golumbic","year":"1980","unstructured":"M.\u00a0Golumbic, Algorithmic Graph Theory and Perfect Graphs (Academic, New York, 1980)"},{"key":"4_CR17","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":"D.\u00a0Gusfield, Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology (Cambridge University Press, Cambridge, 1997)"},{"key":"4_CR18","first-page":"166","volume-title":"Haplotyping as perfect phylogeny: conceptual framework and efficient solutions, in Proceedings of the 6th Annual Conference on Research in Computational Molecular Biology (RECOMB)","author":"D. Gusfield","year":"2002","unstructured":"D.\u00a0Gusfield, Haplotyping as perfect phylogeny: conceptual framework and efficient solutions, in Proceedings of the 6th Annual Conference on Research in Computational Molecular Biology (RECOMB), Washington, DC, 2002, pp.\u00a0166\u2013175"},{"key":"4_CR19","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1007\/BF02392825","volume":"182","author":"J. H\u00e5stad","year":"1999","unstructured":"J.\u00a0H\u00e5stad, Clique is hard to approximate within n\n                  1\u2212\u03b5\n                  . Acta Math. 182, 105\u2013142 (1999). doi:10.1007\/BF02392825","journal-title":"Acta Math."},{"issue":"6","key":"4_CR20","doi-asserted-by":"publisher","first-page":"1749","DOI":"10.1137\/S0097539794279067","volume":"26","author":"S. Kannan","year":"1997","unstructured":"S.\u00a0Kannan, T.\u00a0Warnow, A fast algorithm for the computation and enumeration of perfect phylogenies. SIAM J. Comput. 26(6), 1749\u20131763 (1997)","journal-title":"SIAM J. Comput."},{"key":"4_CR21","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Complexity of Computer Computations","author":"R.M. Karp","year":"1972","unstructured":"R.M. Karp, Reducibility among combinatorial problems, in Complexity of Computer Computations, ed. by R.E. Miller, J.W. Thatcher. The IBM Research Symposia Series (Plenum Press, New York, 1972), pp.\u00a085\u2013103"},{"issue":"3","key":"4_CR22","doi-asserted-by":"publisher","first-page":"590","DOI":"10.1137\/S0097539702406510","volume":"33","author":"I. Peer","year":"2004","unstructured":"I.\u00a0Peer, T.\u00a0Pupko, R.\u00a0Shamir, R.\u00a0Sharan, Incomplete directed perfect phylogeny. SIAM J. Comput. 33(3), 590\u2013607 (2004)","journal-title":"SIAM J. Comput."},{"key":"4_CR23","doi-asserted-by":"crossref","unstructured":"T.M. Przytycka, An important connection between network motifs and parsimony models, in Proceedings of the 10th Annual Conference on Research in Computational Molecular Biology (RECOMB), Venice, 2006, pp.\u00a0321\u2013335","DOI":"10.1007\/11732990_27"},{"issue":"2","key":"4_CR24","doi-asserted-by":"publisher","first-page":"351","DOI":"10.1089\/cmb.2006.13.351","volume":"13","author":"T. Przytycka","year":"2006","unstructured":"T.\u00a0Przytycka, G.\u00a0Davis, N.\u00a0Song, D.\u00a0Durand, Graph theoretical insights into Dollo parsimony and evolution of multidomain proteins. J. Comput. Biol. 13(2), 351\u2013363 (2006)","journal-title":"J. Comput. Biol."},{"key":"4_CR25","doi-asserted-by":"crossref","unstructured":"R.V. Satya, A.\u00a0Mukherjee, G.\u00a0Alexe, L.\u00a0Parida, G.\u00a0Bhanot, Constructing near-perfect phylogenies with multiple homoplasy events, in ISMB (Supplement of Bioinformatics), Fortaleza, 2006, pp.\u00a0514\u2013522","DOI":"10.1093\/bioinformatics\/btl262"},{"key":"4_CR26","unstructured":"C.\u00a0Semple, M.\u00a0Steel, Phylogenetics. Oxford Lecture Series in Mathematics and Its Applications (Oxford University Press, Oxford, 2003)"},{"issue":"4","key":"4_CR27","doi-asserted-by":"publisher","first-page":"561","DOI":"10.1109\/TCBB.2007.1070","volume":"4","author":"S. Sridhar","year":"2007","unstructured":"S.\u00a0Sridhar, K.\u00a0Dhamdhere, G.\u00a0Blelloch, E.\u00a0Halperin, R.\u00a0Ravi, R.\u00a0Schwartz, Algorithms for efficient near-perfect phylogenetic tree reconstruction in theory and practice. IEEE\/ACM Trans. Comput. Biol. Bioinf. 4(4), 561\u2013571 (2007)","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinf."},{"key":"4_CR28","first-page":"1","volume":"2012","author":"A. Subramanian","year":"2012","unstructured":"A.\u00a0Subramanian, S.\u00a0Shackney, R.\u00a0Schwartz, Inference of tumor phylogenies from genomic assays on heterogeneous samples. J. Biomed. Biotechnol. 2012, 1\u201316 (2012)","journal-title":"J. Biomed. Biotechnol."},{"issue":"6","key":"4_CR29","first-page":"905","volume":"11","author":"W.T. Tutte","year":"1960","unstructured":"W.T. Tutte, An algorithm for determining whether a given binary matroid is graphic. Proc. Am. Math. Soc. 11(6), 905\u2013917 (1960)","journal-title":"Proc. Am. Math. Soc."},{"issue":"11","key":"4_CR30","doi-asserted-by":"publisher","first-page":"2583","DOI":"10.1093\/molbev\/msm207","volume":"24","author":"J. Zheng","year":"2007","unstructured":"J.\u00a0Zheng, I.B. Rogozin, E.V. Koonin, T.M. Przytycka, Support for the Coelomata clade of animals from a rigorous analysis of the pattern of intron conservation. Mol. Biol. Evol. 24(11), 2583\u20132592 (2007)","journal-title":"Mol. Biol. Evol."},{"issue":"1","key":"4_CR31","first-page":"1","volume":"7","author":"E. Zotenko","year":"2006","unstructured":"E.\u00a0Zotenko, K.S. Guimar\u00e3es, R.\u00a0Jothi, T.M. Przytycka, Decomposition of overlapping protein complexes: a graph theoretical method for analyzing static and dynamic protein associations. Algorithms Mol. Biol. 7(1), 1\u201311 (2006)","journal-title":"Algorithms Mol. Biol."}],"container-title":["Natural Computing Series","Discrete and Topological Models in Molecular Biology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-40193-0_4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,14]],"date-time":"2023-02-14T09:51:44Z","timestamp":1676368304000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-642-40193-0_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,10,10]]},"ISBN":["9783642401923","9783642401930"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-40193-0_4","relation":{},"ISSN":["1619-7127"],"issn-type":[{"value":"1619-7127","type":"print"}],"subject":[],"published":{"date-parts":[[2013,10,10]]},"assertion":[{"value":"10 October 2013","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}