{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,19]],"date-time":"2025-03-19T14:27:32Z","timestamp":1742394452076},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540359043"},{"type":"electronic","value":"9783540359050"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11786986_58","type":"book-chapter","created":{"date-parts":[[2006,6,28]],"date-time":"2006-06-28T06:46:45Z","timestamp":1151477205000},"page":"667-678","source":"Crossref","is-referenced-by-count":13,"title":["Fixed Parameter Tractability of Binary Near-Perfect Phylogenetic Tree Reconstruction"],"prefix":"10.1007","author":[{"given":"Guy E.","family":"Blelloch","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kedar","family":"Dhamdhere","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Eran","family":"Halperin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"R.","family":"Ravi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Russell","family":"Schwartz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Srinath","family":"Sridhar","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"58_CR1","doi-asserted-by":"crossref","unstructured":"Agarwala, R., Fernandez-Baca, D.: A Polynomial-Time Algorithm for the Perfect Phylogeny Problem when the Number of Character States is Fixed. SIAM Journal on Computing\u00a023 (1994)","DOI":"10.1137\/S0097539793244587"},{"key":"58_CR2","doi-asserted-by":"crossref","unstructured":"Bodlaender, H., Fellows, M., Warnow, T.: Two Strikes Against Perfect Phylogeny. In: proc. International Colloquium on Automata, Languages and Programming (1992)","DOI":"10.1007\/3-540-55719-9_80"},{"key":"58_CR3","doi-asserted-by":"crossref","unstructured":"Bodlaender, H., Fellows, M., Hallett, M., Wareham, H., Warnow, T.: The Hardness of Perfect Phylogeny, Feasible Register Assignment and Other Problems on Thin Colored Graphs. In: Theoretical Computer Science (2000)","DOI":"10.1016\/S0304-3975(98)00342-9"},{"key":"58_CR4","doi-asserted-by":"crossref","unstructured":"Bonet, M., Steel, M., Warnow, T., Yooseph, S.: Better Methods for Solving Parsimony and Compatibility. Journal of Computational Biology\u00a05(3) (1992)","DOI":"10.1089\/cmb.1998.5.391"},{"key":"58_CR5","doi-asserted-by":"crossref","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Monographs in Computer Science (1999)","DOI":"10.1007\/978-1-4612-0515-9"},{"key":"58_CR6","doi-asserted-by":"crossref","unstructured":"Day, W.H., Sankoff, D.: Computational Complexity of Inferring Phylogenies by Compatibility. Systematic Zoology (1986)","DOI":"10.2307\/2413432"},{"key":"58_CR7","doi-asserted-by":"crossref","unstructured":"Damaschke, P.: Parameterized Enumeration, Transversals, and Imperfect Phylogeny Reconstruction. In: proc. International Workshop on Parameterized and Exact Computation (2004)","DOI":"10.1007\/978-3-540-28639-4_1"},{"key":"58_CR8","doi-asserted-by":"crossref","unstructured":"Eskin, E., Halperin, E., Karp, R.M.: Efficient Reconstruction of Haplotype Structure via Perfect Phylogeny. Journal of Bioinformatics and Computational Biology (2003)","DOI":"10.1142\/S0219720003000174"},{"key":"58_CR9","doi-asserted-by":"crossref","unstructured":"Fernandez-Baca, D., Lagergren, J.: A Polynomial-Time Algorithm for Near-Perfect Phylogeny. SIAM Journal on Computing\u00a032 (2003)","DOI":"10.1137\/S0097539799350839"},{"key":"58_CR10","doi-asserted-by":"crossref","unstructured":"Foulds, L.R., Graham, R.L.: The Steiner problem in Phylogeny is NP-complete. Advances in Applied Mathematics\u00a0(3) (1982)","DOI":"10.1016\/S0196-8858(82)80004-3"},{"key":"58_CR11","doi-asserted-by":"crossref","unstructured":"Ganapathy, G., Ramachandran, V., Warnow, T.: Better Hill-Climbing Searches for Parsimony. In: Workshop on Algorithms in Bioinformatics (2003)","DOI":"10.1007\/978-3-540-39763-2_19"},{"key":"58_CR12","doi-asserted-by":"crossref","unstructured":"Gusfield, D.: Efficient Algorithms for Inferring Evolutionary Trees. Networks\u00a021 (1991)","DOI":"10.1002\/net.3230210104"},{"key":"58_CR13","volume-title":"Algorithms on Strings, Trees and Sequences","author":"D. Gusfield","year":"1999","unstructured":"Gusfield, D.: Algorithms on Strings, Trees and Sequences. Cambridge University Press, Cambridge (1999)"},{"key":"58_CR14","doi-asserted-by":"crossref","unstructured":"Gusfield, D., Bansal, V.: A Fundamental Decomposition Theory for Phylogenetic Networks and Incompatible Characters. In: proc. Research in Computational Molecular Biology (2005)","DOI":"10.1007\/11415770_17"},{"key":"58_CR15","doi-asserted-by":"crossref","unstructured":"Gusfield, D., Eddhu, S., Langley, C.: Efficient Reconstruction of Phylogenetic Networks with Constrained Recombination. In: Proc. IEEE Computer Society Bioinformatics Conference (2003)","DOI":"10.1109\/CSB.2003.1227337"},{"key":"58_CR16","doi-asserted-by":"crossref","unstructured":"Hinds, D.A., Stuve, L.L., Nilsen, G.B., Halperin, E., Eskin, E., Ballinger, D.G., Frazer, K.A., Cox, D.R.: Whole Genome Patterns of Common DNA Variation in Three Human Populations. In: Science (2005), http:\/\/www.perlegen.com","DOI":"10.1126\/science.1105436"},{"key":"58_CR17","doi-asserted-by":"crossref","unstructured":"The International HapMap Consortium. The International HapMap Project. Nature 426 (2003)","DOI":"10.1038\/nature02168"},{"key":"58_CR18","doi-asserted-by":"crossref","unstructured":"Kannan, S., Warnow, T.: A Fast Algorithm for the Computation and Enumeration of Perfect Phylogenies. SIAM Journal on Computing\u00a026 (1997)","DOI":"10.1137\/S0097539794279067"},{"key":"58_CR19","doi-asserted-by":"crossref","unstructured":"Promel, H.J., Steger, A.: The Steiner Tree Problem: A Tour Through Graphs Algorithms and Complexity. Vieweg Verlag (2002)","DOI":"10.1007\/978-3-322-80291-0"},{"key":"58_CR20","doi-asserted-by":"crossref","unstructured":"Sridhar, S., Dhamdhere, K., Blelloch, G.E., Halperin, E., Ravi, R., Schwartz, R.: Simple Reconstruction of Binary Near-Perfect Phylogenetic Trees. In: proc. International Workshop on Bioinformatics Research and Applications (2006)","DOI":"10.1007\/11758525_107"},{"key":"58_CR21","volume-title":"Phylogenetics","author":"C. Semple","year":"2003","unstructured":"Semple, C., Steel, M.: Phylogenetics. Oxford University Press, Oxford (2003)"},{"key":"58_CR22","doi-asserted-by":"crossref","unstructured":"Steel, M.A.: The Complexity of Reconstructing Trees from Qualitative Characters and Subtrees. J. Classification\u00a09 (1992)","DOI":"10.1007\/BF02618470"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11786986_58.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T03:19:57Z","timestamp":1619493597000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11786986_58"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540359043","9783540359050"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/11786986_58","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2006]]}}}