{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T06:18:20Z","timestamp":1725603500940},"publisher-location":"Berlin, Heidelberg","reference-count":29,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642230370"},{"type":"electronic","value":"9783642230387"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"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":[[2011]]},"DOI":"10.1007\/978-3-642-23038-7_24","type":"book-chapter","created":{"date-parts":[[2011,8,30]],"date-time":"2011-08-30T13:06:43Z","timestamp":1314709603000},"page":"282-297","source":"Crossref","is-referenced-by-count":1,"title":["Efficiently Solvable Perfect Phylogeny Problems on Binary and k-State Data with Missing Values"],"prefix":"10.1007","author":[{"given":"Kristian","family":"Stevens","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bonnie","family":"Kirkpatrick","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"6","key":"24_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 Journal of Computing\u00a023(6), 1216\u20131224 (1994)","journal-title":"SIAM Journal of Computing"},{"key":"24_CR2","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-1-4613-8369-7_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: George, A., Gilbert, J.R., Liu, J.W.H. (eds.) Graph Theory and Sparse Matrix Computation, pp. 1\u201329. Springer, Heidelberg (1993)"},{"issue":"3","key":"24_CR3","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 characterisation of rigid circuit graphs. Discrete Mathematics\u00a09(3), 205\u2013212 (1974)","journal-title":"Discrete Mathematics"},{"issue":"19","key":"24_CR4","doi-asserted-by":"publisher","first-page":"2215","DOI":"10.1093\/bioinformatics\/btn406","volume":"24","author":"Z. Ding","year":"2008","unstructured":"Ding, Z., Mailund, T., Song, Y.S.: Efficient whole-genome association mapping using local phylogenies for unphased genotype data. Bioinformatics\u00a024(19), 2215\u20132221 (2008)","journal-title":"Bioinformatics"},{"key":"24_CR5","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1007\/BF02992776","volume":"25","author":"G.A. Dirac","year":"1961","unstructured":"Dirac, G.A.: On rigid circuit graphs. Abhandlungen aus dem Mathematischen Seminar der Universit\u00e4t Hamburg\u00a025, 71\u201376 (1961)","journal-title":"Abhandlungen aus dem Mathematischen Seminar der Universit\u00e4t Hamburg"},{"key":"24_CR6","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"},{"issue":"3","key":"24_CR7","doi-asserted-by":"publisher","first-page":"835","DOI":"10.2140\/pjm.1965.15.835","volume":"15","author":"D.R. Fulkerson","year":"1965","unstructured":"Fulkerson, D.R., Gross, O.A.: Incidence matrices and interval graphs. Pac. J. of Math.\u00a015(3), 835\u2013855 (1965)","journal-title":"Pac. J. of Math."},{"key":"24_CR8","volume-title":"Algorithmic graph theory and perfect graphs","author":"M.C. Golumbic","year":"2004","unstructured":"Golumbic, M.C.: Algorithmic graph theory and perfect graphs. North-Holland, Amsterdam (2004)"},{"key":"24_CR9","doi-asserted-by":"publisher","first-page":"236","DOI":"10.1007\/978-3-642-02008-7_18","volume-title":"Research in Computational Molecular Biology","author":"D. Gusfield","year":"2009","unstructured":"Gusfield, D.: The multi-state perfect phylogeny problem with missing and removable data: Solutions via integer-programming and chordal graph theory. In: Research in Computational Molecular Biology, pp. 236\u2013252. Springer, Heidelberg (2009)"},{"key":"24_CR10","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":"24_CR11","first-page":"10","volume-title":"RECOMB 2004: Proc.s of the 8th ann. Internat\u2019l. Conf. on Comp. Mol. Bio.","author":"E. Halperin","year":"2004","unstructured":"Halperin, E., Karp, R.M.: Perfect phylogeny and haplotype assignment. In: RECOMB 2004: Proc.s of the 8th ann. Internat\u2019l. Conf. on Comp. Mol. Bio., pp. 10\u201319. ACM Press, New York (2004)"},{"issue":"2","key":"24_CR12","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1093\/bioinformatics\/18.2.337","volume":"18","author":"R.R. Hudson","year":"2002","unstructured":"Hudson, R.R.: Generating samples under a Wright-Fisher neutral model of genetic variation. Bioinformatics\u00a018(2), 337\u2013338 (2002)","journal-title":"Bioinformatics"},{"key":"24_CR13","first-page":"595","volume-title":"Proc. of the 6th Ann. ACM-SIAM Symp. on Disc. Alg.","author":"S. Kannan","year":"1995","unstructured":"Kannan, S., Warnow, T.: A fast algorithm for the computation and enumeration of perfect phylogenies when the number of character states is fixed. In: Proc. of the 6th Ann. ACM-SIAM Symp. on Disc. Alg., pp. 595\u2013603. Society for Industrial and Applied Mathematics, Philadelphia (1995)"},{"key":"24_CR14","doi-asserted-by":"crossref","first-page":"45","DOI":"10.4064\/fm-51-1-45-64","volume":"51","author":"C.G. Lekkerkerker","year":"1962","unstructured":"Lekkerkerker, C.G., Boland, J.C.: Representation of a finite graph by a set of intervals on the real line. Fundamenta Mathematicae\u00a051, 45\u201364 (1962)","journal-title":"Fundamenta Mathematicae"},{"issue":"6","key":"24_CR15","doi-asserted-by":"publisher","first-page":"1146","DOI":"10.1137\/0910070","volume":"10","author":"J.G. Lewis","year":"1989","unstructured":"Lewis, J.G., Peyton, B.W., Pothen, A.: A fast algorithm for reordering sparse matrices for parallel factorization. SIAM J. on Sci. and Stat. Comp.\u00a010(6), 1146\u20131173 (1989)","journal-title":"SIAM J. on Sci. and Stat. Comp."},{"issue":"4","key":"24_CR16","doi-asserted-by":"crossref","first-page":"2213","DOI":"10.1093\/genetics\/165.4.2213","volume":"165","author":"N. Li","year":"2003","unstructured":"Li, N., Stephens, M.: Modeling linkage disequilibrium and identifying recombination hotspots using single-nucleotide polymorphism data. Genetics\u00a0165(4), 2213\u20132233 (2003)","journal-title":"Genetics"},{"key":"24_CR17","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":"24_CR18","first-page":"135","volume":"16B","author":"F.R. McMorris","year":"1983","unstructured":"McMorris, F.R., Meacham, C.A.: Partition intersection graphs. Ars Combinatoria\u00a016B, 135\u2013138 (1983)","journal-title":"Ars Combinatoria"},{"issue":"3","key":"24_CR19","doi-asserted-by":"publisher","first-page":"591","DOI":"10.2307\/1219940","volume":"30","author":"C.A. Meacham","year":"1981","unstructured":"Meacham, C.A.: A manual method for character compatibility analysis. Taxon\u00a030(3), 591\u2013600 (1981)","journal-title":"Taxon"},{"issue":"3","key":"24_CR20","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. Comput.\u00a033(3), 590\u2013607 (2004)","journal-title":"SIAM J. Comput."},{"issue":"2a","key":"24_CR21","doi-asserted-by":"publisher","first-page":"407","DOI":"10.1142\/S021972000700259X","volume":"5","author":"G. Pennington","year":"2007","unstructured":"Pennington, G., Smith, C.A., Shackney, S., Schwartz, R.: Reconstructing tumor phylogenies from heterogeneous single-cell data. J. Bioinfo. and Comp. Bio.\u00a05(2a), 407\u2013427 (2007)","journal-title":"J. Bioinfo. and Comp. Bio."},{"issue":"4","key":"24_CR22","doi-asserted-by":"publisher","first-page":"618","DOI":"10.1109\/TCBB.2007.70218","volume":"5","author":"R. Satya","year":"2008","unstructured":"Satya, R., Mukherjee, A.: The undirected incomplete perfect phylogeny problem. IEEE\/ACM Trans. on Comp. Bio. and Bioinfo.\u00a05(4), 618\u2013629 (2008)","journal-title":"IEEE\/ACM Trans. on Comp. Bio. and Bioinfo."},{"key":"24_CR23","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":"24_CR24","doi-asserted-by":"crossref","unstructured":"Steel, M.: The complexity of reconstructing trees from qualitative characters and subtrees. Journal of Classification, 91\u2013116 (1992)","DOI":"10.1007\/BF02618470"},{"key":"24_CR25","doi-asserted-by":"publisher","first-page":"978","DOI":"10.1086\/319501","volume":"68","author":"M. Stephens","year":"2001","unstructured":"Stephens, M., Smith, N., Donnelly, P.: A new statistical method for haplotype reconstruction from population data. American Journal of Human Genetics\u00a068, 978\u2013989 (2001)","journal-title":"American Journal of Human Genetics"},{"key":"24_CR26","doi-asserted-by":"crossref","unstructured":"Sze, S.H., Lu, S., Chen, J.: Integrating sample-driven and pattern-driven approaches in motif finding. Algorithms in Bioinformatics, 438\u2013449 (2004)","DOI":"10.1007\/978-3-540-30219-3_37"},{"key":"24_CR27","doi-asserted-by":"publisher","first-page":"566","DOI":"10.1137\/0213035","volume":"13","author":"R. Tarjan","year":"1984","unstructured":"Tarjan, R., Yannakakis, M.: Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs. SIAM Journal on Computing\u00a013, 566\u2013579 (1984)","journal-title":"SIAM Journal on Computing"},{"key":"24_CR28","first-page":"382","volume-title":"Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete algorithms, SODA 1993","author":"T.J. Warnow","year":"1993","unstructured":"Warnow, T.J.: Tree compatibility and inferring evolutionary history. In: Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete algorithms, SODA 1993, pp. 382\u2013391. Society for Industrial and Applied Mathematics, Philadelphia (1993)"},{"key":"24_CR29","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1007\/978-3-642-01551-9_21","volume-title":"Bioinformatics Research and Applications","author":"Y. Wu","year":"2009","unstructured":"Wu, Y.: Exact computation of coalescent likelihood under the infinite sites model. In: M\u0103ndoiu, I., Narasimhan, G., Zhang, Y. (eds.) ISBRA 2009. LNCS, vol.\u00a05542, pp. 209\u2013220. Springer, Heidelberg (2009)"}],"container-title":["Lecture Notes in Computer Science","Algorithms in Bioinformatics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-23038-7_24","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,4,10]],"date-time":"2024-04-10T18:29:25Z","timestamp":1712773765000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-23038-7_24"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642230370","9783642230387"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-23038-7_24","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}