{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T21:52:58Z","timestamp":1742939578963,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642020070"},{"type":"electronic","value":"9783642020087"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009]]},"DOI":"10.1007\/978-3-642-02008-7_18","type":"book-chapter","created":{"date-parts":[[2009,5,13]],"date-time":"2009-05-13T17:28:14Z","timestamp":1242235694000},"page":"236-252","source":"Crossref","is-referenced-by-count":7,"title":["The Multi-State Perfect Phylogeny Problem with Missing and Removable Data: Solutions via Integer-Programming and Chordal Graph Theory"],"prefix":"10.1007","author":[{"given":"Dan","family":"Gusfield","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"18_CR1","doi-asserted-by":"publisher","first-page":"1216","DOI":"10.1137\/S0097539793244587","volume":"23","author":"R. Agarwala","year":"1994","unstructured":"Agarwala, R., Fernandez-Baca, D.: A polynomial-time algorithm for the perfect phylogeny problem when the number of character states is fixed. SIAM J. on Computing\u00a023, 1216\u20131224 (1994)","journal-title":"SIAM J. on Computing"},{"key":"18_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1007\/3-540-46784-X_17","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"A. Berry","year":"1999","unstructured":"Berry, A., Bordat, J.-P., Cogis, O.: Generating All the Minimal Separators of a Graph. In: Widmayer, P., Neyer, G., Eidenbenz, S. (eds.) WG 1999. LNCS, vol.\u00a01665, pp. 167\u2013172. Springer, Heidelberg (1999)"},{"key":"18_CR3","doi-asserted-by":"crossref","unstructured":"Bodlaender, H., Fellows, M., Warnow, T.: Two strikes against perfect phylogeny. In: Proc. of the 19\u2019th Inter. colloquium on Automata, Languages and Programming, pp. 273\u2013283 (1992)","DOI":"10.1007\/3-540-55719-9_80"},{"key":"18_CR4","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1016\/0012-365X(74)90002-8","volume":"9","author":"P. Buneman","year":"1974","unstructured":"Buneman, P.: A characterization of rigid circuit graphs. Discrete Math.\u00a09, 205\u2013212 (1974)","journal-title":"Discrete Math."},{"key":"18_CR5","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/0893-9659(92)90026-6","volume":"5","author":"A. Dress","year":"1993","unstructured":"Dress, A., Steel, M.: Convex tree realizations of partitions. Applied Math. Letters\u00a05, 3\u20136 (1993)","journal-title":"Applied Math. Letters"},{"key":"18_CR6","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1016\/0025-5564(75)90040-1","volume":"23","author":"G. Estabrook","year":"1975","unstructured":"Estabrook, G., Johnson, C., McMorris, F.: An idealized concept of the true cladistic character. Math. Bioscience\u00a023, 263\u2013272 (1975)","journal-title":"Math. Bioscience"},{"key":"18_CR7","volume-title":"Inferring Phylogenies","author":"J. Felsenstein","year":"2004","unstructured":"Felsenstein, J.: Inferring Phylogenies. Sinauer, Sunderland (2004)"},{"key":"18_CR8","volume-title":"Steiner Trees in Industries","author":"D. Fernandez-Baca","year":"2000","unstructured":"Fernandez-Baca, D.: The perfect phylogeny problem. In: Du, D.Z., Cheng, X. (eds.) Steiner Trees in Industries. Kluwer Academic Publishers, Dordrecht (2000)"},{"key":"18_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"670","DOI":"10.1007\/3-540-61440-0_168","volume-title":"Automata, Languages and Programming","author":"D. Fernandez-Baca","year":"1996","unstructured":"Fernandez-Baca, D., Lagergren, J.: A polynomial-time algorithm for near-perfect phylogeny. In: Meyer auf der Heide, F., Monien, B. (eds.) ICALP 1996. LNCS, vol.\u00a01099, pp. 670\u2013680. Springer, Heidelberg (1996)"},{"key":"18_CR10","first-page":"189","volume-title":"Proceedings of the eighth international conference on numerical taxonomy","author":"W. Fitch","year":"1975","unstructured":"Fitch, W.: Towards finding the tree of maximum parsimony. In: Estabrook, G.F. (ed.) Proceedings of the eighth international conference on numerical taxonomy, pp. 189\u2013230. W.H. Freeman, New York (1975)"},{"key":"18_CR11","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1016\/0095-8956(74)90094-X","volume":"16","author":"F. Gavril","year":"1974","unstructured":"Gavril, F.: The intersection graphs of subtrees in trees are exactly the chordal graphs. J. Combinatorial Theory, B\u00a016, 47\u201356 (1974)","journal-title":"J. Combinatorial Theory, B"},{"key":"18_CR12","volume-title":"Algorithmic Graph Theory and Perfect Graphs","author":"M.C. Golumbic","year":"1980","unstructured":"Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York (1980)"},{"key":"18_CR13","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":"18_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1007\/978-3-540-73545-8_8","volume-title":"Computing and Combinatorics","author":"D. Gusfield","year":"2007","unstructured":"Gusfield, D., Frid, Y., Brown, D.: Integer programming formulations and computations solving phylogenetic and population genetic problems with missing or genotypic data. In: Lin, G. (ed.) COCOON 2007. LNCS, vol.\u00a04598, pp. 51\u201364. Springer, Heidelberg (2007)"},{"key":"18_CR15","unstructured":"Gusfield, D., Wu, Y.: The three-state perfect phylogeny problem reduces to 2-SAT (to appear)"},{"key":"18_CR16","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1016\/j.disc.2005.12.003","volume":"306","author":"P. Heggernes","year":"2006","unstructured":"Heggernes, P.: Minimal triangulations of graphs: A survey. Discrete Mathematics\u00a0306, 297\u2013317 (2006)","journal-title":"Discrete Mathematics"},{"issue":"2","key":"18_CR17","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1093\/bioinformatics\/18.2.337","volume":"18","author":"R. Hudson","year":"2002","unstructured":"Hudson, R.: Generating samples under the Wright-Fisher neutral model of genetic variation. Bioinformatics\u00a018(2), 337\u2013338 (2002)","journal-title":"Bioinformatics"},{"key":"18_CR18","doi-asserted-by":"publisher","first-page":"713","DOI":"10.1137\/S0097539791222171","volume":"23","author":"S. Kannan","year":"1994","unstructured":"Kannan, S., Warnow, T.: Inferring evolutionary history from DNA sequences. SIAM J. on Computing\u00a023, 713\u2013737 (1994)","journal-title":"SIAM J. on Computing"},{"key":"18_CR19","doi-asserted-by":"publisher","first-page":"1749","DOI":"10.1137\/S0097539794279067","volume":"26","author":"S. Kannan","year":"1997","unstructured":"Kannan, S., Warnow, T.: A fast algorithm for the computation and enumeration of perfect phylogenies when the number of character states is fixed. SIAM J. on Computing\u00a026, 1749\u20131763 (1997)","journal-title":"SIAM J. on Computing"},{"key":"18_CR20","doi-asserted-by":"crossref","unstructured":"McKee, T.A., McMorris, F.R.: Topics in Intersection Graph Theory. Siam Monographs on Discrete Mathematics (1999)","DOI":"10.1137\/1.9780898719802"},{"key":"18_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1007\/3-540-60084-1_68","volume-title":"Automata, Languages and Programming","author":"A. Parra","year":"1995","unstructured":"Parra, A., Scheffler, P.: How to use the minimal separators of a graph for its chordal triangulation. In: F\u00fcl\u00f6p, Z., Gecseg, F. (eds.) ICALP 1995. LNCS, vol.\u00a0944, pp. 123\u2013134. Springer, Heidelberg (1995)"},{"key":"18_CR22","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1016\/S0166-218X(97)00041-3","volume":"79","author":"A. Parra","year":"1997","unstructured":"Parra, A., Scheffler, P.: Characterizations and algorithmic applications of chordal graph embeddings. Discrete Applied Mathematics\u00a079, 171\u2013188 (1997)","journal-title":"Discrete Applied Mathematics"},{"key":"18_CR23","doi-asserted-by":"publisher","first-page":"590","DOI":"10.1137\/S0097539702406510","volume":"33","author":"I. Pe\u2019er","year":"2004","unstructured":"Pe\u2019er, I., Pupko, T., Shamir, R., Sharan, R.: Incomplete directed perfect phylogeny. SIAM J. on Computing\u00a033, 590\u2013607 (2004)","journal-title":"SIAM J. on Computing"},{"key":"18_CR24","doi-asserted-by":"crossref","DOI":"10.1093\/oso\/9780198509424.001.0001","volume-title":"Phylogenetics","author":"C. Semple","year":"2003","unstructured":"Semple, C., Steel, M.: Phylogenetics. Oxford University Press, Oxford (2003)"},{"key":"18_CR25","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1007\/BF02618470","volume":"9","author":"M. Steel","year":"1992","unstructured":"Steel, M.: The complexity of reconstructing trees from qualitative characters and subtrees. J. of Classification\u00a09, 91\u2013116 (1992)","journal-title":"J. of Classification"}],"container-title":["Lecture Notes in Computer Science","Research in Computational Molecular Biology"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-02008-7_18","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,13]],"date-time":"2024-03-13T09:34:40Z","timestamp":1710322480000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-02008-7_18"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642020070","9783642020087"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-02008-7_18","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2009]]}}}