{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,12]],"date-time":"2026-03-12T00:35:34Z","timestamp":1773275734462,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":35,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540720300","type":"print"},{"value":"9783540720317","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-72031-7_4","type":"book-chapter","created":{"date-parts":[[2007,8,5]],"date-time":"2007-08-05T14:16:24Z","timestamp":1186323384000},"page":"37-48","source":"Crossref","is-referenced-by-count":14,"title":["Efficiently Finding the Most Parsimonious Phylogenetic Tree Via Linear Programming"],"prefix":"10.1007","author":[{"given":"Srinath","family":"Sridhar","sequence":"first","affiliation":[]},{"given":"Fumei","family":"Lam","sequence":"additional","affiliation":[]},{"given":"Guy E.","family":"Blelloch","sequence":"additional","affiliation":[]},{"given":"R.","family":"Ravi","sequence":"additional","affiliation":[]},{"given":"Russell","family":"Schwartz","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"4_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 on Computing\u00a023, 1216\u20131224 (1994)","journal-title":"SIAM Journal on Computing"},{"key":"4_CR2","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1089\/10665270360688048","volume":"10","author":"V. Bafna","year":"2003","unstructured":"Bafna, V., et al.: Haplotyping as perfect phylogeny: A direct approach. Journal of Computational Biology\u00a010, 323\u2013340 (2003)","journal-title":"Journal of Computational Biology"},{"key":"4_CR3","doi-asserted-by":"crossref","first-page":"743","DOI":"10.1093\/genetics\/141.2.743","volume":"141","author":"H.J. Bandelt","year":"1989","unstructured":"Bandelt, H.J., et al.: Mitochondrial portraits of human populations using median networks. Genetics\u00a0141, 743\u2013753 (1989)","journal-title":"Genetics"},{"key":"4_CR4","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1016\/0012-365X(89)90283-5","volume":"76","author":"J. Barth\u00e9lemy","year":"1989","unstructured":"Barth\u00e9lemy, J.: From copair hypergraphs to median graphs with latent vertices. Discrete Math.\u00a076, 9\u201328 (1989)","journal-title":"Discrete Math."},{"key":"4_CR5","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1002\/net.3230140112","volume":"14","author":"J.E. Beasley","year":"1984","unstructured":"Beasley, J.E.: An algorithm for the Steiner problem in graphs. Networks\u00a014, 147\u2013159 (1984)","journal-title":"Networks"},{"key":"4_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"667","DOI":"10.1007\/11786986_16","volume-title":"Automata, Languages and Programming","author":"R. Ravi","year":"2006","unstructured":"Ravi, R., et al.: Fixed Parameter Tractability of Binary Near-Perfect Phylogenetic Tree Reconstruction. In: Bugliesi, M., et al. (eds.) ICALP 2006. LNCS, vol.\u00a04051, pp. 667\u2013678. Springer, Heidelberg (2006)"},{"key":"4_CR7","unstructured":"Buneman, P.: The recovery of trees from measures of dissimilarity. In: Hodson, F., et al. (eds.) Mathematics in the Archeological and Historical Sciences, pp. 387\u2013395 (1971)"},{"key":"4_CR8","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4613-0255-1","volume-title":"Steiner Trees in Industry","author":"X. Cheng","year":"2002","unstructured":"Cheng, X., Du, D.Z.: Steiner Trees in Industry. Springer, Heidelberg (2002)"},{"issue":"5696","key":"4_CR9","doi-asserted-by":"publisher","first-page":"636","DOI":"10.1126\/science.1105136","volume":"306","author":"The ENCODE Project Consortium","year":"2004","unstructured":"The ENCODE Project Consortium: The ENCODE (ENCyclopedia Of DNA Elements) Project. Science\u00a0306(5696), 636\u2013640 (2004), doi:10.1126\/science.1105136","journal-title":"Science"},{"issue":"7069","key":"4_CR10","doi-asserted-by":"publisher","first-page":"803","DOI":"10.1038\/nature04338","volume":"438","author":"K. Lindblad-Toh","year":"2005","unstructured":"Lindblad-Toh, K., et al.: Genome sequence, comparative analysis and haplotype structure of the domestic dog. Nature\u00a0438(7069), 803\u2013819 (2005)","journal-title":"Nature"},{"key":"4_CR11","doi-asserted-by":"publisher","first-page":"381","DOI":"10.1038\/74215","volume":"24","author":"K. Lindblad-Toh","year":"2000","unstructured":"Lindblad-Toh, K., et al.: Large-scale discovery and genotyping of single-nucleotide polymorphisms in the mouse. Nature Genetics\u00a024, 381\u2013386 (2000)","journal-title":"Nature Genetics"},{"key":"4_CR12","unstructured":"Felsenstein, J.: PHYLIP (Phylogeny Inference Package) version 3.6. Distributed by the author, Department of Genome Sciences, University of Washington, Seattle (2005)"},{"key":"4_CR13","doi-asserted-by":"publisher","first-page":"1115","DOI":"10.1137\/S0097539799350839","volume":"32","author":"D. Fernandez-Baca","year":"2003","unstructured":"Fernandez-Baca, D., Lagergren, J.: A polynomial-time algorithm for near-perfect phylogeny. SIAM Journal on Computing\u00a032, 1115\u20131127 (2003)","journal-title":"SIAM Journal on Computing"},{"key":"4_CR14","doi-asserted-by":"crossref","unstructured":"Foulds, L.R., Graham, R.L.: The Steiner problem in phylogeny is NP-complete. Advances in Applied Mathematics\u00a03 (1982)","DOI":"10.1016\/S0196-8858(82)80004-3"},{"key":"4_CR15","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman, New York (1979)"},{"key":"4_CR16","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 trees. Networks\u00a021, 19\u201328 (1991)","journal-title":"Networks"},{"key":"4_CR17","doi-asserted-by":"crossref","unstructured":"Gusfield, D.: Haplotyping by pure parsimony. Combinatorial Pattern Matching (2003)","DOI":"10.1007\/3-540-44888-8_11"},{"key":"4_CR18","doi-asserted-by":"crossref","unstructured":"Gusfield, D., Bansal, V.: A fundamental decomposition theory for phylogenetic networks and incompatible characters. Research in Computational Molecular Biology (2005)","DOI":"10.1007\/11415770_17"},{"key":"4_CR19","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1002\/ajpa.20313","volume":"130","author":"A. Helgason","year":"2006","unstructured":"Helgason, A., et al.: mtDNA variation in Inuit populations of Greenland and Canada: migration history and population structure. American Journal of Physical Anthropology\u00a0130, 123\u2013134 (2006)","journal-title":"American Journal of Physical Anthropology"},{"key":"4_CR20","unstructured":"Hwang, F.K., Richards, D.S., Winter, P.: The Steiner Tree Problem. Annals of Discrete Mathematics, vol.\u00a053 (1992)"},{"key":"4_CR21","doi-asserted-by":"crossref","first-page":"789","DOI":"10.1038\/nature02168","volume":"426","author":"The International HapMap Consortium","year":"2005","unstructured":"The International HapMap Consortium: The International HapMap Project. Nature\u00a0426, 789\u2013796 (2005), www.hapmap.org","journal-title":"Nature"},{"key":"4_CR22","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. SIAM Journal on Computing\u00a026, 1749\u20131763 (1997)","journal-title":"SIAM Journal on Computing"},{"key":"4_CR23","doi-asserted-by":"publisher","first-page":"351","DOI":"10.1002\/ajpa.20102","volume":"127","author":"C.M.J.. Lewis","year":"2005","unstructured":"Lewis, C.M.J., et al.: Land, language, and loci: mtDNA in Native Americans and the genetic history of Peru. American Journal of Physical Anthropology\u00a0127, 351\u2013360 (2005)","journal-title":"American Journal of Physical Anthropology"},{"key":"4_CR24","first-page":"185","volume":"31","author":"N. Maculan","year":"1987","unstructured":"Maculan, N.: The Steiner problem in graphs. Annals of Discrete Mathematics\u00a031, 185\u2013212 (1987)","journal-title":"Annals of Discrete Mathematics"},{"key":"4_CR25","doi-asserted-by":"crossref","unstructured":"Merimaa, M., et al.: Functional co-adaption of phenol hydroxylase and catechol 2,3-dioxygenase genes in bacteria possessing different phenol and p-cresol degradation pathways. In: Eighth Symposium on Bacterial Genetics and Ecology 31, pp. 185\u2013212 (2005)","DOI":"10.1007\/s00203-006-0143-3"},{"key":"4_CR26","doi-asserted-by":"publisher","first-page":"497","DOI":"10.1007\/s10038-005-0284-2","volume":"50","author":"S. S","year":"2005","unstructured":"S, S., et al.: Human mtDNA hypervariable regions, HVR I and II, hint at deep common maternal founder and subsequent maternal gene flow in Indian population groups. American Journal of Human Genetics\u00a050, 497\u2013506 (2005)","journal-title":"American Journal of Human Genetics"},{"issue":"4","key":"4_CR27","first-page":"406","volume":"4","author":"N. Saitou","year":"1987","unstructured":"Saitou, N., Nei, M.: The neighbor-joining method: a new method for reconstructing phylogenetic trees. Molecular Biology and Evolution\u00a04(4), 406\u2013425 (1987)","journal-title":"Molecular Biology and Evolution"},{"key":"4_CR28","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)"},{"issue":"7055","key":"4_CR29","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1038\/nature04072","volume":"437","author":"The Chimpanzee Sequencing and Analysis Consortium","year":"2005","unstructured":"The Chimpanzee Sequencing and Analysis Consortium: Initial sequence of the chimpanzee genome and comparison with the human genome. Nature\u00a0437(7055), 69\u201387 (2005), http:\/\/dx.doi.org\/10.1038\/nature04072 , doi:10.1038\/nature04072","journal-title":"Nature"},{"issue":"1","key":"4_CR30","doi-asserted-by":"publisher","first-page":"352","DOI":"10.1093\/nar\/28.1.352","volume":"28","author":"E.M. Smigielski","year":"2000","unstructured":"Smigielski, E.M., et al.: dbSNP: a database of single nucleotide polymorphisms. Nucleic Acids Research\u00a028(1), 352\u2013355 (2000)","journal-title":"Nucleic Acids Research"},{"key":"4_CR31","doi-asserted-by":"crossref","unstructured":"Sridhar, S., et al.: Optimal imperfect phylogeny reconstruction and haplotyping. Computational Systems Bioinformatics (2006)","DOI":"10.1142\/9781860947575_0026"},{"key":"4_CR32","doi-asserted-by":"crossref","unstructured":"Sridhar, S., et al.: Simple reconstruction of binary near-perfect phylogenetic trees. In: International Workshop on Bioinformatics Research and Applications (2006)","DOI":"10.1007\/11758525_107"},{"key":"4_CR33","doi-asserted-by":"crossref","unstructured":"Stone, A.C., et al.: High levels of Y-chromosome nucleotide diversity in the genus Pan. Proceedings of the National Academy of Sciences USA, 43\u201348 (2002)","DOI":"10.1073\/pnas.012364999"},{"issue":"14","key":"4_CR34","doi-asserted-by":"publisher","first-page":"4746","DOI":"10.1073\/pnas.0306629101","volume":"101","author":"T. Wirth","year":"2004","unstructured":"Wirth, T., et al.: Distinguishing human ethnic groups by means of sequences from Helicobacter pylori: Lessons from Ladakh. Proceedings of the National Academy of Sciences USA\u00a0101(14), 4746\u20134751 (2004), doi:10.1073\/pnas.0306629101","journal-title":"Proceedings of the National Academy of Sciences USA"},{"key":"4_CR35","doi-asserted-by":"publisher","first-page":"271","DOI":"10.1007\/BF02612335","volume":"28","author":"R.T. Wong","year":"1984","unstructured":"Wong, R.T.: A dual ascent approach for Steiner tree problems on a directed graph. Mathematical Programming\u00a028, 271\u2013287 (1984)","journal-title":"Mathematical Programming"}],"container-title":["Lecture Notes in Computer Science","Bioinformatics Research and Applications"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-72031-7_4.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,2,17]],"date-time":"2024-02-17T07:58:53Z","timestamp":1708156733000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-72031-7_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540720300","9783540720317"],"references-count":35,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-72031-7_4","relation":{},"subject":[]}}