{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,4]],"date-time":"2026-06-04T21:23:38Z","timestamp":1780608218513,"version":"3.54.1"},"reference-count":23,"publisher":"Oxford University Press (OUP)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2007,1,15]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Motivation: Phylogenies\u2014the evolutionary histories of groups of organisms\u2014play a major role in representing relationships among biological entities. Although many biological processes can be effectively modeled as tree-like relationships, others, such as hybrid speciation and horizontal gene transfer (HGT), result in networks, rather than trees, of relationships. Hybrid speciation is a significant evolutionary mechanism in plants, fish and other groups of species. HGT plays a major role in bacterial genome diversification and is a significant mechanism by which bacteria develop resistance to antibiotics. Maximum parsimony is one of the most commonly used criteria for phylogenetic tree inference. Roughly speaking, inference based on this criterion seeks the tree that minimizes the amount of evolution. In 1990, Jotun Hein proposed using this criterion for inferring the evolution of sequences subject to recombination. Preliminary results on small synthetic datasets. Nakhleh et al. (2005) demonstrated the criterion\u2019s application to phylogenetic network reconstruction in general and HGT detection in particular. However, the naive algorithms used by the authors are inapplicable to large datasets due to their demanding computational requirements. Further, no rigorous theoretical analysis of computing the criterion was given, nor was it tested on biological data.<\/jats:p><jats:p>Results: In the present work we prove that the problem of scoring the parsimony of a phylogenetic network is NP-hard and provide an improved fixed parameter tractable algorithm for it. Further, we devise efficient heuristics for parsimony-based reconstruction of phylogenetic networks. We test our methods on both synthetic and biological data (rbcL gene in bacteria) and obtain very promising results.<\/jats:p><jats:p>Contact: \u00a0ssagi@math.berkeley.edu<\/jats:p>","DOI":"10.1093\/bioinformatics\/btl313","type":"journal-article","created":{"date-parts":[[2007,1,19]],"date-time":"2007-01-19T18:51:12Z","timestamp":1169232672000},"page":"e123-e128","source":"Crossref","is-referenced-by-count":41,"title":["Efficient parsimony-based methods for phylogenetic network reconstruction"],"prefix":"10.1093","volume":"23","author":[{"given":"Guohua","family":"Jin","sequence":"first","affiliation":[{"name":"Department of Computer Science, Rice University 1 \u00a0 1 \u00a0 \u00a0 Houston, TX, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Luay","family":"Nakhleh","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Rice University 1 \u00a0 1 \u00a0 \u00a0 Houston, TX, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sagi","family":"Snir","sequence":"additional","affiliation":[{"name":"Department of Mathematics, University of California 2 \u00a0 2 \u00a0 \u00a0 Berkeley, CA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tamir","family":"Tuller","sequence":"additional","affiliation":[{"name":"School of Computer Science, Tel Aviv University 3 \u00a0 3 \u00a0 \u00a0 Tel Aviv, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"286","published-online":{"date-parts":[[2007,1,15]]},"reference":[{"key":"2023041107145373500_","doi-asserted-by":"crossref","first-page":"17747","DOI":"10.1073\/pnas.0408336102","article-title":"Massive horizontal transfer of mitochondrial genes from diverse land plant donors to the basal angiosperm Amborella","volume":"101","author":"Bergthorsson","year":"2004","journal-title":"Proc. Natl Acad. Sci. USA"},{"key":"2023041107145373500_","doi-asserted-by":"crossref","first-page":"873","DOI":"10.1093\/oxfordjournals.molbev.a025647","article-title":"Rampant horizontal transfer and duplicaion of rubisco genes in eubacteria and plastids","volume":"13","author":"Delwiche","year":"1996","journal-title":"Mol. Biol. Evol."},{"key":"2023041107145373500_","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1098\/rstb.2002.1185","article-title":"How big is the iceberg of which organellar genes in nuclear genomes are but the tip?","volume":"358","author":"Doolittle","year":"2003","journal-title":"Phil. Trans. R. Soc. Lond. B. Biol. Sci."},{"key":"2023041107145373500_","doi-asserted-by":"crossref","first-page":"873","DOI":"10.1137\/S0097539792228228","article-title":"Fixed parameter tractability and completeness I: basic theory","volume":"24","author":"Downey","year":"1995","journal-title":"SIAM J. Comput."},{"key":"2023041107145373500_","doi-asserted-by":"crossref","first-page":"475","DOI":"10.1016\/S1369-5274(00)00125-9","article-title":"Assessing evolutionary relationships among microbes from whole-genome analysis","volume":"3","author":"Eisen","year":"2000","journal-title":"Curr. Opin. Microbiol."},{"key":"2023041107145373500_","doi-asserted-by":"crossref","first-page":"406","DOI":"10.2307\/2412116","article-title":"Toward defining the course of evolution: minimum change for a specified tree topology","volume":"20","author":"Fitch","year":"1971","journal-title":"Syst. Zool."},{"key":"2023041107145373500_","author":"Garey","year":"1979","journal-title":"Computer and Intractability"},{"key":"2023041107145373500_","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1002\/net.3230210104","article-title":"Efficient algorithms for inferring evolutionary history","volume":"21","author":"Gusfield","year":"1991","journal-title":"Networks"},{"key":"2023041107145373500_","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1016\/0025-5564(90)90123-G","article-title":"Reconstructing evolution of sequences subject to recombination using parsimony","volume":"98","author":"Hein","year":"1990","journal-title":"Math. Biosci."},{"key":"2023041107145373500_","doi-asserted-by":"crossref","first-page":"396","DOI":"10.1007\/BF00182187","article-title":"A heuristic method to reconstruct the history of sequences subject to recombination","volume":"36","author":"Hein","year":"1993","journal-title":"J. Mol. Evol."},{"key":"2023041107145373500_","volume-title":"Approximation Algorithms for NP-Hard Problems","author":"Hochbaum","year":"1997"},{"key":"2023041107145373500_","doi-asserted-by":"crossref","first-page":"254","DOI":"10.1093\/molbev\/msj030","article-title":"Application of phylogenetic networks in evolutionary studies","volume":"23","author":"Huson","year":"2006","journal-title":"Mol. Biol. Evol."},{"key":"2023041107145373500_","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1007\/BF01731581","article-title":"A simple method for estimating evolutionary rates of base substitutions through comparative studies of nucleotide sequences","volume":"16","author":"Kimura","year":"1980","journal-title":"J. Mol. Evol."},{"key":"2023041107145373500_","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1371\/journal.pbio.0000019","article-title":"From gene trees to organismal phylogeny in prokaryotes: the case of the \u03b3-proteobacteria","volume":"1","author":"Lerat","year":"2003","journal-title":"PLoS Biol."},{"key":"2023041107145373500_","doi-asserted-by":"crossref","first-page":"1700","DOI":"10.3732\/ajb.91.10.1700","article-title":"Reconstructing patterns of reticulate evolution in plants","volume":"91","author":"Linder","year":"2004","journal-title":"Am. J. Bot."},{"key":"2023041107145373500_","article-title":"Network (reticulate) evolution: biology, models, and algorithms","volume-title":"In The Ninth Pacific Symposium on Biocomputing (PSB)","author":"Linder","year":"2004"},{"key":"2023041107145373500_","doi-asserted-by":"crossref","DOI":"10.1016\/S1874-5334(06)80006-7","article-title":"Phylogenetic network reconstruction approaches","volume":"6","author":"Makarenkov","year":"2006","journal-title":"Applied Mycology and Biotechnology (Genes, Genomics and Bioinformatics)"},{"key":"2023041107145373500_","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1109\/TCBB.2004.10","article-title":"Phylogenetic networks: modeling, reconstructibility, and accuracy","volume":"1","author":"Moret","year":"2004","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinform."},{"key":"2023041107145373500_","first-page":"440","article-title":"Reconstructing phylogenetic networks using maximum parsimony","volume":"393","author":"Nakhleh","year":"2005","journal-title":"Proc. IEEE Comput. Syst. Bioinform. Conf."},{"key":"2023041107145373500_","doi-asserted-by":"crossref","first-page":"2071","DOI":"10.1126\/science.1080613","article-title":"Role of mobile DNA in the evolution of Vacomycin-resistant Enterococcus faecalis","volume":"299","author":"Paulsen","year":"2003","journal-title":"Science"},{"key":"2023041107145373500_","first-page":"235","article-title":"Seq-Gen: an application for the Monte Carlo simulation of DNA sequence evolution along phylogenetic trees","volume":"13","author":"Rambaut","year":"1997","journal-title":"Comput. Appl. Biosci."},{"key":"2023041107145373500_","article-title":"r8s software package","author":"Sanderson"},{"key":"2023041107145373500_","first-page":"35","article-title":"Minimal mutation trees of sequences","volume-title":"SIAM J. Appl. Math.","author":"Sankoff","year":"1975"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/23\/2\/e123\/49820615\/bioinformatics_23_2_e123.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/23\/2\/e123\/49820615\/bioinformatics_23_2_e123.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,2,10]],"date-time":"2024-02-10T09:38:47Z","timestamp":1707557927000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/23\/2\/e123\/203275"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,1,15]]},"references-count":23,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2007,1,15]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btl313","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2007,1,15]]},"published":{"date-parts":[[2007,1,15]]}}}