{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,28]],"date-time":"2026-04-28T23:00:44Z","timestamp":1777417244802,"version":"3.51.4"},"reference-count":21,"publisher":"Oxford University Press (OUP)","issue":"21","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006,11,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Motivation: Horizontal gene transfer (HGT) is believed to be ubiquitous among bacteria, and plays a major role in their genome diversification as well as their ability to develop resistance to antibiotics. In light of its evolutionary significance and implications for human health, developing accurate and efficient methods for detecting and reconstructing HGT is imperative.<\/jats:p>\n               <jats:p>Results: In this article we provide a new HGT-oriented likelihood framework for many problems that involve phylogeny-based HGT detection and reconstruction. Beside the formulation of various likelihood criteria, we show that most of these problems are NP-hard, and offer heuristics for efficient and accurate reconstruction of HGT under these criteria. We implemented our heuristics and used them to analyze biological as well as synthetic data. In both cases, our criteria and heuristics exhibited very good performance with respect to identifying the correct number of HGT events as well as inferring their correct location on the species tree.<\/jats:p>\n               <jats:p>Availability: Implementation of the criteria as well as heuristics and hardness proofs are available from the authors upon request. Hardness proofs can also be downloaded at<\/jats:p>\n               <jats:p>Contact: \u00a0tamirtul@post.tau.ac.il<\/jats:p>\n               <jats:p>Supplementary information: Supplementary data are available at Bioinformatics online.<\/jats:p>","DOI":"10.1093\/bioinformatics\/btl452","type":"journal-article","created":{"date-parts":[[2006,8,24]],"date-time":"2006-08-24T00:25:54Z","timestamp":1156379154000},"page":"2604-2611","source":"Crossref","is-referenced-by-count":107,"title":["Maximum likelihood of phylogenetic networks"],"prefix":"10.1093","volume":"22","author":[{"given":"Guohua","family":"Jin","sequence":"first","affiliation":[{"name":"Department of Computer Science, Rice University 1 \u00a0 1 \u00a0 \u00a0 Houston, TX, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Luay","family":"Nakhleh","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Rice University 1 \u00a0 1 \u00a0 \u00a0 Houston, TX, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sagi","family":"Snir","sequence":"additional","affiliation":[{"name":"Department of Mathematics, University of California 2 \u00a0 2 \u00a0 \u00a0 Berkeley, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tamir","family":"Tuller","sequence":"additional","affiliation":[{"name":"School of Computer Science, Tel-Aviv University 3 \u00a0 3 \u00a0 \u00a0 Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2006,8,23]]},"reference":[{"key":"2023012408424184900_b1","first-page":"190","article-title":"New efficient algorithm for detection of horizontal gene transfer events","volume-title":"Proceedings of the WABI03","author":"Boc","year":"2003"},{"key":"2023012408424184900_b2","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":"2023012408424184900_b3","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":"Philos. Trans. R. Soc. Lond. B. Biol. Sci."},{"key":"2023012408424184900_b4","doi-asserted-by":"crossref","first-page":"368","DOI":"10.1007\/BF01734359","article-title":"Evolutionary trees from DNA sequences: a maximum likelihood approach","volume":"17","author":"Felsenstein","year":"1981","journal-title":"J. Mol. Evol."},{"key":"2023012408424184900_b5","first-page":"217","article-title":"A fundamental decomposition theory for phylogenetic networks and incompatible characters","volume-title":"Proceedings of the RECOMB05","author":"Gusfield","year":"2005"},{"key":"2023012408424184900_b6","doi-asserted-by":"crossref","first-page":"345","DOI":"10.1093\/bioinformatics\/18.suppl_1.S345","article-title":"Detecting recombination with MCMC","volume":"18","author":"Husmeier","year":"2002","journal-title":"Bioinformatics"},{"key":"2023012408424184900_b7","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":"2023012408424184900_b8","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1016\/B978-1-4832-3211-9.50009-7","article-title":"Evolution of protein molecules","volume-title":"Mammalian-Protein Metabolism","author":"Jukes","year":"1969"},{"key":"2023012408424184900_b9","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":"2023012408424184900_b10","article-title":"Network (reticulate) evolution: biology, models, and algorithms","volume-title":"Proceedings of the PSB04","author":"Linder","year":"2004"},{"key":"2023012408424184900_b11","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. Boto."},{"key":"2023012408424184900_b12","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":"Trans. Comput. Biol. Bioinform."},{"key":"2023012408424184900_b13","article-title":"Towards the development of computational tools for evaluating phylogenetic network reconstruction methods","volume-title":"Proceedings of the PSB03","author":"Nakhleh","year":"2003"},{"key":"2023012408424184900_b14","article-title":"Gene trees, species trees, and species networks","volume-title":"Meta-analysis and Combining Information in Genetics","author":"Nakhleh","year":"2006"},{"key":"2023012408424184900_b15","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":"2023012408424184900_b16","doi-asserted-by":"crossref","first-page":"890","DOI":"10.1093\/oxfordjournals.molbev.a026369","article-title":"A fast algorithm for joint reconstruction of ancestral amino-acid sequences","volume":"17","author":"Pupko","year":"2000","journal-title":"Mol. Biol. Evol."},{"key":"2023012408424184900_b17","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":"2023012408424184900_b18","doi-asserted-by":"crossref","first-page":"839","DOI":"10.1093\/oxfordjournals.molbev.a026364","article-title":"Parsimony, likelihood and the role of models in molecular phylogenetics","volume":"17","author":"Steel","year":"2000","journal-title":"Mol. Biol. Evol."},{"key":"2023012408424184900_b19","doi-asserted-by":"crossref","first-page":"875","DOI":"10.1093\/oxfordjournals.molbev.a026367","article-title":"Likelihood analysis of phylogenetic networks using directed graphical models","volume":"17","author":"Strimmer","year":"2000","journal-title":"Mol. Biol. Evol."},{"key":"2023012408424184900_b20","doi-asserted-by":"crossref","first-page":"631","DOI":"10.1093\/oxfordjournals.molbev.a004122","article-title":"Archaeal phylogeny based on ribosomal proteins","volume":"19","author":"Tailliez","year":"2002","journal-title":"Mol. Biol. Evol."},{"key":"2023012408424184900_b21","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1007\/BF00170465","article-title":"Network models for sequence evolution","volume":"37","author":"von Haeseler","year":"1993","journal-title":"J. Mol. Evol."}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/22\/21\/2604\/48838630\/bioinformatics_22_21_2604.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/22\/21\/2604\/48838630\/bioinformatics_22_21_2604.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,24]],"date-time":"2023-01-24T09:03:36Z","timestamp":1674551016000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/22\/21\/2604\/251789"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,8,23]]},"references-count":21,"journal-issue":{"issue":"21","published-print":{"date-parts":[[2006,11,1]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btl452","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2006,11,1]]},"published":{"date-parts":[[2006,8,23]]}}}