{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,19]],"date-time":"2025-03-19T16:05:04Z","timestamp":1742400304922},"reference-count":33,"publisher":"Oxford University Press (OUP)","issue":"6","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2008,3,15]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Motivation: The evolution of viruses is very rapid and in addition to local point mutations (insertion, deletion, substitution) it also includes frequent recombinations, genome rearrangements and horizontal transfer of genetic materials (HGTS). Evolutionary analysis of viral sequences is therefore a complicated matter for two main reasons: First, due to HGTs and recombinations, the right model of evolution is a network and not a tree. Second, due to genome rearrangements, an alignment of the input sequences is not guaranteed. These facts encourage developing methods for inferring phylogenetic networks that do not require aligned sequences as input.<\/jats:p>\n               <jats:p>Results: In this work, we present the first computational approach which deals with both genome rearrangements and horizontal gene transfers and does not require a multiple alignment as input. We formalize a new set of computational problems which involve analyzing such complex models of evolution. We investigate their computational complexity, and devise algorithms for solving them. Moreover, we demonstrate the viability of our methods on several synthetic datasets as well as four biological datasets.<\/jats:p>\n               <jats:p>Availability: The code is available from the authors upon request.<\/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\/btn024","type":"journal-article","created":{"date-parts":[[2008,1,19]],"date-time":"2008-01-19T01:34:46Z","timestamp":1200706486000},"page":"826-832","source":"Crossref","is-referenced-by-count":9,"title":["Inferring horizontal transfers in the presence of rearrangements by the minimum evolution criterion"],"prefix":"10.1093","volume":"24","author":[{"given":"Hadas","family":"Birin","sequence":"first","affiliation":[{"name":"1 School of Computer Science, Tel Aviv University, Tel Aviv, Israel and 2School of Computer Science and Communication, Royal Institute of Technology, Sweden"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zohar","family":"Gal-Or","sequence":"additional","affiliation":[{"name":"1 School of Computer Science, Tel Aviv University, Tel Aviv, Israel and 2School of Computer Science and Communication, Royal Institute of Technology, Sweden"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Isaac","family":"Elias","sequence":"additional","affiliation":[{"name":"1 School of Computer Science, Tel Aviv University, Tel Aviv, Israel and 2School of Computer Science and Communication, Royal Institute of Technology, Sweden"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tamir","family":"Tuller","sequence":"additional","affiliation":[{"name":"1 School of Computer Science, Tel Aviv University, Tel Aviv, Israel and 2School of Computer Science and Communication, Royal Institute of Technology, Sweden"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2008,1,18]]},"reference":[{"key":"2023020209512345600_B1","first-page":"279","article-title":"Towards identifying lateral gene transfer events","volume-title":"PSB03.","author":"Addario-Berry","year":"2003"},{"key":"2023020209512345600_B2","author":"Arvestad","year":"2006","journal-title":"Beep software package"},{"key":"2023020209512345600_B3","doi-asserted-by":"crossref","first-page":"197","DOI":"10.1038\/nature01743","article-title":"Widespread horizontal transfer of mitochondrial genes in flowering plants","volume":"424","author":"Bergthorsson","year":"2003","journal-title":"Nature"},{"key":"2023020209512345600_B4","first-page":"190","article-title":"New efficient algorithm for detection of horizontal gene transfer events","volume-title":"WABI.","author":"Boc","year":"2003"},{"key":"2023020209512345600_B5","first-page":"55","article-title":"Fast lightweight suffix array construction and checking","author":"Burkhardt","year":"2003"},{"key":"2023020209512345600_B6","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":"2023020209512345600_B7","doi-asserted-by":"crossref","first-page":"687","DOI":"10.1089\/106652702761034136","article-title":"Fast and accurate phylogeny reconstruction algorithms based on the minimum-evolution principle","volume":"9","author":"Desper","year":"2002","journal-title":"J. Comp. Biol"},{"key":"2023020209512345600_B8","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":"2023020209512345600_B9","first-page":"352","article-title":"Settling the intractability of multiple alignment","volume-title":"ISAAC.","author":"Elias","year":"2003"},{"key":"2023020209512345600_B10","doi-asserted-by":"crossref","first-page":"27","DOI":"10.2307\/2412810","article-title":"Cases in which parsimony and compatibility methods will be positively misleading","volume":"27","author":"Felsenstein","year":"1978","journal-title":"Syst. Zool"},{"key":"2023020209512345600_B11","article-title":"Phylip (phylogeny inference package) version 3.5c","author":"Felsenstein","year":"1993","journal-title":"Distributed by the author."},{"key":"2023020209512345600_B12","doi-asserted-by":"crossref","DOI":"10.1090\/dimacs\/037\/09","article-title":"Concerning the NJ algorithm and its unweighted version UNJ","volume-title":"Mathematical hierarchies and Biology.","author":"Gascuel","year":"1997"},{"key":"2023020209512345600_B13","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1006\/viro.1995.1228","article-title":"The DNA sequence of human herpesvirus-6: structure, coding content, and genome evolution","volume":"209","author":"Gompels","year":"1995","journal-title":"Virology"},{"key":"2023020209512345600_B14","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":"2023020209512345600_B15","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":"2023020209512345600_B16","doi-asserted-by":"crossref","first-page":"2604","DOI":"10.1093\/bioinformatics\/btl452","article-title":"Maximum likelihood of phylogenetic networks","volume":"22","author":"Guohua","year":"2006","journal-title":"Bioinformatics"},{"key":"2023020209512345600_B17","first-page":"324","article-title":"Inferring phylogenetic networks by the maximum parsimony criterion: A case study","volume":"24","author":"Guohua","year":"2007","journal-title":"Mol. Biol. Evol"},{"key":"2023020209512345600_B18","doi-asserted-by":"crossref","first-page":"1627","DOI":"10.3732\/ajb.91.10.1627","article-title":"A survey of tricolpate (eudicot) phylogenetic relationships","volume":"91","author":"Judd","year":"2004","journal-title":"Am. J. Bot"},{"key":"2023020209512345600_B19","doi-asserted-by":"crossref","first-page":"1853","DOI":"10.1099\/vir.0.79984-0","article-title":"Full-length open reading frame of a recombinant Hepatitis C virus strain from St Petersburg: proposed mechanism for its formation","volume":"85","author":"Kalinina","year":"2004","journal-title":"J. Gen. Virol"},{"key":"2023020209512345600_B20","first-page":"235","article-title":"Phylogenetic analysis: concepts and methods","volume":"23","author":"Kidd","year":"1971","journal-title":"Am. J. Hum. Genet"},{"key":"2023020209512345600_B21","article-title":"The ancient virus world and evolution of cells","volume":"1","author":"Koonin","year":"2006","journal-title":"Biol. Direct"},{"key":"2023020209512345600_B22","doi-asserted-by":"crossref","first-page":"379","DOI":"10.1093\/bioinformatics\/bth485","article-title":"The los alamos HCV sequence database","volume":"21","author":"Kuiken","year":"2005","journal-title":"Bioinformatics"},{"key":"2023020209512345600_B23","doi-asserted-by":"crossref","first-page":"93","DOI":"10.3732\/ajb.90.1.93","article-title":"Phylogenetic relationships among Poaceae and related families as inferred from morphology, inversions in the plastid genome, and sequence data from mitochondrial and plastid genomes","volume":"90","author":"Michelangeli","year":"2003","journal-title":"Am. J. Bot"},{"key":"2023020209512345600_B24","first-page":"1073","article-title":"Theoretical foundation of the minimum-evolution method of phylogenetic inference","volume":"10","author":"Rzhetsky","year":"1993","journal-title":"Mol. Biol. Evol"},{"key":"2023020209512345600_B25","first-page":"406","article-title":"The neighbor-joining method: a new method for reconstructing phylogenetic trees","volume":"4","author":"Saitou","year":"1987","journal-title":"Mol. Biol. Evol"},{"key":"2023020209512345600_B26","first-page":"349","article-title":"The origin and evolution of viruses (a review)","volume":"45","author":"Sinkovics","year":"1998","journal-title":"Acta Microbiol Immunol Hung"},{"key":"2023020209512345600_B27","doi-asserted-by":"crossref","first-page":"321","DOI":"10.1099\/0022-1317-78-2-321","article-title":"The origin of hepatitis C virus genotypes","volume":"78","author":"Smith","year":"1997","journal-title":"J. Gen. Virol"},{"key":"2023020209512345600_B28","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1093\/bioinformatics\/14.2.157","article-title":"Rose: generating sequence families","volume":"14","author":"Stoye","year":"1998","journal-title":"Bioinformatics"},{"key":"2023020209512345600_B29","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":"2023020209512345600_B30","doi-asserted-by":"crossref","first-page":"1629","DOI":"10.1093\/molbev\/msh159","article-title":"On inconsistency of the neighbor-joining, least squares, and minimum evolution estimation when substitution processes are incorrectly modeled","volume":"21","author":"Susko","year":"2004","journal-title":"Mol. Biol. Evol"},{"key":"2023020209512345600_B31","doi-asserted-by":"crossref","first-page":"336","DOI":"10.1089\/cmb.2006.13.336","article-title":"The average common substring approach to phylogenomic reconstruction","volume":"13","author":"Ulitsky","year":"2006","journal-title":"J. Comp. Biol"},{"key":"2023020209512345600_B32","doi-asserted-by":"crossref","first-page":"2535","DOI":"10.1099\/0022-1317-80-10-2535","article-title":"Evolutionary aspects of recombination in RNA viruses","volume":"80","author":"Worobey","year":"1999","journal-title":"J. Gen. Virol"},{"key":"2023020209512345600_B33","doi-asserted-by":"crossref","first-page":"1107","DOI":"10.1093\/molbev\/msk019","article-title":"Average gene length is highly conserved in prokaryotes and eukaryotes and diverges only between the two kingdoms","volume":"23","author":"Xu","year":"2006","journal-title":"Mol. Biol. Evol"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/24\/6\/826\/49046011\/bioinformatics_24_6_826.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/24\/6\/826\/49046011\/bioinformatics_24_6_826.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,2]],"date-time":"2023-02-02T10:46:20Z","timestamp":1675334780000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/24\/6\/826\/193548"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,1,18]]},"references-count":33,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2008,3,15]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btn024","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2008,3,15]]},"published":{"date-parts":[[2008,1,18]]}}}