{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T04:58:27Z","timestamp":1725512307136},"publisher-location":"Berlin, Heidelberg","reference-count":36,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540720300"},{"type":"electronic","value":"9783540720317"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-72031-7_6","type":"book-chapter","created":{"date-parts":[[2007,8,5]],"date-time":"2007-08-05T10:16:24Z","timestamp":1186308984000},"page":"61-72","source":"Crossref","is-referenced-by-count":7,"title":["A New Linear-Time Heuristic Algorithm for Computing the Parsimony Score of Phylogenetic Networks: Theoretical Bounds and Empirical Performance"],"prefix":"10.1007","author":[{"given":"Guohua","family":"Jin","sequence":"first","affiliation":[]},{"given":"Luay","family":"Nakhleh","sequence":"additional","affiliation":[]},{"given":"Sagi","family":"Snir","sequence":"additional","affiliation":[]},{"given":"Tamir","family":"Tuller","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"6_CR1","series-title":"Lecture Notes in Bioinformatics","doi-asserted-by":"crossref","first-page":"569","DOI":"10.1007\/11415770_43","volume-title":"Research in Computational Molecular Biology","author":"V. Bafna","year":"2005","unstructured":"Bafna, V., Bansal, V.: Improved Recombination Lower Bounds for Haplotype Data. In: Miyano, S., et al. (eds.) RECOMB 2005. LNCS (LNBI), vol.\u00a03500, pp. 569\u2013584. Springer, Heidelberg (2005)"},{"key":"6_CR2","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1137\/S0895480196305124","volume":"12","author":"V. Bafna","year":"1999","unstructured":"Bafna, V., Berman, P., Fujito, T.: A 2-approximation algorithm for the undirected feedback vertex set problem. SIAM J. on Discrete Mathematics\u00a012, 289\u2013297 (1999)","journal-title":"SIAM J. on Discrete Mathematics"},{"key":"6_CR3","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1007\/s004530010009","volume":"27","author":"R. Bar-Yehuda","year":"2000","unstructured":"Bar-Yehuda, R.: One for the price of two: A unified approach for approximating covering problems. Algorithmica\u00a027, 131\u2013144 (2000)","journal-title":"Algorithmica"},{"key":"6_CR4","first-page":"27","volume":"25","author":"R. Bar-Yehuda","year":"1985","unstructured":"Bar-Yehuda, R., Even, S.: A local-ratio theorem for approximating the weighted vertex cover problem. Annals of Discrete Mathematics\u00a025, 27\u201346 (1985)","journal-title":"Annals of Discrete Mathematics"},{"key":"6_CR5","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1038\/nature01743","volume":"424","author":"U. Bergthorsson","year":"2003","unstructured":"Bergthorsson, U., et al.: Widespread horizontal transfer of mitochondrial genes in flowering plants. Nature\u00a0424, 197\u2013201 (2003)","journal-title":"Nature"},{"key":"6_CR6","doi-asserted-by":"crossref","unstructured":"Delwiche, C.F., Palmer, J.D.: Rampant horizontal transfer and duplication of rubisco genes in eubacteria and plastids. Mol. Biol. Evol.\u00a013(6) (1996)","DOI":"10.1093\/oxfordjournals.molbev.a025647"},{"key":"6_CR7","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1098\/rstb.2002.1185","volume":"358","author":"W.F. Doolittle","year":"2003","unstructured":"Doolittle, W.F., et al.: How big is the iceberg of which organellar genes in nuclear genomes are but the tip? Phil. Trans. R. Soc. Lond. B. Biol. Sci.\u00a0358, 39\u201357 (2003)","journal-title":"Phil. Trans. R. Soc. Lond. B. Biol. Sci."},{"key":"6_CR8","doi-asserted-by":"publisher","first-page":"475","DOI":"10.1016\/S1369-5274(00)00125-9","volume":"3","author":"J.A. Eisen","year":"2000","unstructured":"Eisen, J.A.: Assessing evolutionary relationships among microbes from whole-genome analysis. Curr. Opin. Microbiol.\u00a03, 475\u2013480 (2000)","journal-title":"Curr. Opin. Microbiol."},{"issue":"5615","key":"6_CR9","doi-asserted-by":"publisher","first-page":"2071","DOI":"10.1126\/science.1080613","volume":"299","author":"I.T. Paulsen","year":"2003","unstructured":"Paulsen, I.T., et al.: Role of mobile DNA in the evolution of Vacomycin-resistant Enterococcus faecalis. Science\u00a0299(5615), 2071\u20132074 (2003)","journal-title":"Science"},{"key":"6_CR10","doi-asserted-by":"publisher","first-page":"406","DOI":"10.2307\/2412116","volume":"20","author":"W. Fitch","year":"1971","unstructured":"Fitch, W.: Toward defining the course of evolution: minimum change for a specified tree topology. Syst. Zool.\u00a020, 406\u2013416 (1971)","journal-title":"Syst. Zool."},{"key":"6_CR11","series-title":"Lecture Notes in Bioinformatics","doi-asserted-by":"crossref","first-page":"217","DOI":"10.1007\/11415770_17","volume-title":"Research in Computational Molecular Biology","author":"D. Gusfield","year":"2005","unstructured":"Gusfield, D., Bansal, V.: A Fundamental Decomposition Theory for Phylogenetic Networks and Incompatible Characters. In: Miyano, S., et al. (eds.) RECOMB 2005. LNCS (LNBI), vol.\u00a03500, pp. 217\u2013232. Springer, Heidelberg (2005)"},{"key":"6_CR12","doi-asserted-by":"crossref","unstructured":"Hallett, M., Lagergren, J., Tofigh, A.: Simultaneous identification of duplications and lateral transfers. In: Proceedings of the Eighth Annual International Conference on Computational Molecular Biology, pp. 347\u2013356 (2004)","DOI":"10.1145\/974614.974660"},{"key":"6_CR13","doi-asserted-by":"crossref","unstructured":"Hastad, J.: Some optimal inapproximability results. In: STOC97, pp. 1\u201310 (1997)","DOI":"10.1145\/258533.258536"},{"key":"6_CR14","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1016\/0025-5564(90)90123-G","volume":"98","author":"J. Hein","year":"1990","unstructured":"Hein, J.: Reconstructing evolution of sequences subject to recombination using parsimony. Mathematical Biosciences\u00a098, 185\u2013200 (1990)","journal-title":"Mathematical Biosciences"},{"key":"6_CR15","doi-asserted-by":"publisher","first-page":"396","DOI":"10.1007\/BF00182187","volume":"36","author":"J. Hein","year":"1993","unstructured":"Hein, J.: A heuristic method to reconstruct the history of sequences subject to recombination. Journal of Molecular Evolution\u00a036, 396\u2013405 (1993)","journal-title":"Journal of Molecular Evolution"},{"key":"6_CR16","volume-title":"Approximation Algorithms for NP-Hard Problems","author":"D.S. Hochbaum","year":"1997","unstructured":"Hochbaum, D.S.: Approximation Algorithms for NP-Hard Problems. PWS Publishing Company, Boston (1997)"},{"key":"6_CR17","series-title":"Lecture Notes in Bioinformatics","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1007\/11415770_18","volume-title":"Research in Computational Molecular Biology","author":"D.H. Huson","year":"2005","unstructured":"Huson, D.H., et al.: Reconstruction of Reticulate Networks from Gene Trees. In: Miyano, S., et al. (eds.) RECOMB 2005. LNCS (LNBI), vol.\u00a03500, pp. 233\u2013249. Springer, Heidelberg (2005)"},{"key":"6_CR18","series-title":"Lecture Notes in Bioinformatics","first-page":"265","volume-title":"Research in Computational Molecular Biology","author":"W.-K. Sung","year":"2005","unstructured":"Sung, W.-K., et al.: Constructing a Smallest Refining Galled Phylogenetic Network. In: Miyano, S., et al. (eds.) RECOMB 2005. LNCS (LNBI), vol.\u00a03500, pp. 265\u2013280. Springer, Heidelberg (2005)"},{"issue":"4","key":"6_CR19","doi-asserted-by":"publisher","first-page":"489","DOI":"10.1006\/tpbi.2002.1596","volume":"61","author":"R. Jain","year":"2002","unstructured":"Jain, R., et al.: Horizontal gene transfer in microbial genome evolution. Theoretical Population Biology\u00a061(4), 489\u2013495 (2002)","journal-title":"Theoretical Population Biology"},{"issue":"10","key":"6_CR20","doi-asserted-by":"publisher","first-page":"1598","DOI":"10.1093\/molbev\/msg154","volume":"20","author":"R. Jain","year":"2003","unstructured":"Jain, R., et al.: Horizontal gene transfer accelerates genome innovation and evolution. Molecular Biology and Evolution\u00a020(10), 1598\u20131602 (2003)","journal-title":"Molecular Biology and Evolution"},{"key":"6_CR21","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1093\/bioinformatics\/btl313","volume":"23","author":"G. Jin","year":"2006","unstructured":"Jin, G., et al.: Efficient parsimony-based methods for phylogenetic network reconstruction. Bioinformatics\u00a023, e123\u2013e128 (2006)","journal-title":"Bioinformatics"},{"issue":"1","key":"6_CR22","doi-asserted-by":"publisher","first-page":"324","DOI":"10.1093\/molbev\/msl163","volume":"24","author":"G. Jin","year":"2007","unstructured":"Jin, G., et al.: Inferring phylogenetic networks by the maximum parsimony criterion: A case study. Molecular Biology and Evolution\u00a024(1), 324\u2013337 (2007)","journal-title":"Molecular Biology and Evolution"},{"key":"6_CR23","unstructured":"Jin, G., et al.: On approximating the parsimony score of phylogenetic networks. Under review (2007)"},{"key":"6_CR24","doi-asserted-by":"publisher","first-page":"1627","DOI":"10.3732\/ajb.91.10.1627","volume":"91","author":"W.S. Judd","year":"2004","unstructured":"Judd, W.S., Olmstead, R.G.: A survey of tricolpate (eudicot) phylogenetic relationships. American Journal of Botany\u00a091, 1627\u20131644 (2004)","journal-title":"American Journal of Botany"},{"key":"6_CR25","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1007\/BF01731581","volume":"16","author":"M. Kimura","year":"1980","unstructured":"Kimura, M.: A simple method for estimating evolutionary rates of base substitutions through comparative studies of nucleotide sequences. Journal of Molecular Evolution\u00a016, 111\u2013120 (1980)","journal-title":"Journal of Molecular Evolution"},{"key":"6_CR26","unstructured":"Linder, C.R., et al.: Network (reticulate) evolution: biology, models, and algorithms. In: The Ninth Pacific Symposium on Biocomputing (PSB), A tutorial (2004)"},{"key":"6_CR27","doi-asserted-by":"crossref","unstructured":"Makarenkov, V., Kevorkov, D., Legendre, P.: Phylogenetic network reconstruction approaches. Applied Mycology and Biotechnology (Genes, Genomics and Bioinformatics) 6, To appear (2005)","DOI":"10.1016\/S1874-5334(06)80006-7"},{"issue":"5","key":"6_CR28","doi-asserted-by":"crossref","first-page":"631","DOI":"10.1093\/oxfordjournals.molbev.a004122","volume":"19","author":"O. Matte-Tailliez","year":"2002","unstructured":"Matte-Tailliez, O., et al.: Archaeal phylogeny based on ribosomal proteins. Molecular Biology and Evolution\u00a019(5), 631\u2013639 (2002)","journal-title":"Molecular Biology and Evolution"},{"key":"6_CR29","doi-asserted-by":"publisher","first-page":"93","DOI":"10.3732\/ajb.90.1.93","volume":"90","author":"F.A. Michelangeli","year":"2003","unstructured":"Michelangeli, F.A., Davis, J.I., Stevenson, D.W.: Phylogenetic relationships among Poaceae and related families as inferred from morphology, inversions in the plastid genome, and sequence data from mitochondrial and plastid genomes. American Journal of Botany\u00a090, 93\u2013106 (2003)","journal-title":"American Journal of Botany"},{"issue":"1","key":"6_CR30","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1109\/TCBB.2004.10","volume":"1","author":"B.M.E. Moret","year":"2004","unstructured":"Moret, B.M.E., et al.: Phylogenetic networks: modeling, reconstructibility, and accuracy. IEEE\/ACM Transactions on Computational Biology and Bioinformatics\u00a01(1), 13\u201323 (2004)","journal-title":"IEEE\/ACM Transactions on Computational Biology and Bioinformatics"},{"key":"6_CR31","doi-asserted-by":"crossref","unstructured":"Nakhleh, L., et al.: Reconstructing phylogenetic networks using maximum parsimony. In: Proceedings of the 2005 IEEE Computational Systems Bioinformatics Conference (CSB2005), August 2005, pp. 93\u2013102 (2005)","DOI":"10.1109\/CSB.2005.47"},{"key":"6_CR32","doi-asserted-by":"crossref","unstructured":"Nakhleh, L., Warnow, T., Linder, C.R.: Reconstructing reticulate evolution in species: theory and practice. In: Proceedings of the Eighth Annual International Conference on Computational Molecular Biology, pp. 337\u2013346 (2004)","DOI":"10.1145\/974614.974659"},{"key":"6_CR33","doi-asserted-by":"crossref","unstructured":"Nguyen, C.T., et al.: Reconstructing recombination network from sequence data: The small parsimony problem. IEEE\/ACM Transactions on Computational Biology and Bioinformatics (TCBB) (2006)","DOI":"10.1109\/tcbb.2007.1018"},{"key":"6_CR34","first-page":"235","volume":"13","author":"A. Rambaut","year":"1997","unstructured":"Rambaut, A., Grassly, N.C.: Seq-gen: An application for the Monte Carlo simulation of DNA sequence evolution along phylogenetic trees. Comp. Appl. Biosci.\u00a013, 235\u2013238 (1997)","journal-title":"Comp. Appl. Biosci."},{"key":"6_CR35","unstructured":"Sanderson, M.: r8s software package. Available from http:\/\/loco.ucdavis.edu\/r8s\/r8s.html"},{"key":"6_CR36","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1137\/0128004","volume":"28","author":"D. Sankoff","year":"1975","unstructured":"Sankoff, D.: Minimal mutation trees of sequences. SIAM Journal on Applied Mathematics\u00a028, 35\u201342 (1975)","journal-title":"SIAM Journal on Applied Mathematics"}],"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_6.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,13]],"date-time":"2023-05-13T13:58:40Z","timestamp":1683986320000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-72031-7_6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540720300","9783540720317"],"references-count":36,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-72031-7_6","relation":{},"subject":[]}}