{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,25]],"date-time":"2025-09-25T16:33:39Z","timestamp":1758818019910,"version":"3.33.0"},"reference-count":41,"publisher":"Oxford University Press (OUP)","issue":"13","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2007,7,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Motivation: Reconstruction of gene-content evolutionary history is fundamental in studying the evolution of genomes and biological systems. To reconstruct plausible evolutionary history, rates of gene gain\/loss should be estimated by considering the high level of heterogeneity: e.g. genome duplication and parasitization, respectively, result in high rates of gene gain and loss. Gene-content evolution reconstruction methods that consider this heterogeneity and that are both effective in estimating the rates of gene gain and loss and sufficiently efficient to analyze abundant genomic data had not been developed.<\/jats:p><jats:p>Results: An effective and efficient method for reconstructing heterogeneous gene-content evolution was developed. This method comprises analytically integrable modeling of gene-content evolution, analytical formulation of expectation-maximization and efficient calculation of marginal likelihood using an inside-outside-like algorithm. Simulation tests on the scale of hundreds of genomes showed that both the gene gain\/loss rates and evolutionary history were effectively estimated within a few days of computational time. Subsequently, this algorithm was applied to an actual data set of nearly 200 genomes to reconstruct the heterogeneous gene-content evolution across the three domains of life. The reconstructed history, which contained several features consistent with biological observations, showed that the trends of gene-content evolution were not only drastically different between prokaryotes and eukaryotes, but were highly variable within each form of life. The results suggest that heterogeneity should be considered in studies of the evolution of gene content, genomes and biological systems.<\/jats:p><jats:p>Availability: An R script that implements the algorithm is available upon request.<\/jats:p><jats:p>Contact: iwasaki@cb.k.u-tokyo.ac.jp<\/jats:p>","DOI":"10.1093\/bioinformatics\/btm165","type":"journal-article","created":{"date-parts":[[2007,7,23]],"date-time":"2007-07-23T16:13:46Z","timestamp":1185207226000},"page":"i230-i239","source":"Crossref","is-referenced-by-count":29,"title":["Reconstruction of highly heterogeneous gene-content evolution across the three domains of life"],"prefix":"10.1093","volume":"23","author":[{"given":"Wataru","family":"Iwasaki","sequence":"first","affiliation":[{"name":"Department of Computational Biology, Graduate School of Frontier Sciences, University of Tokyo, 5-1-5 Kashiwanoha, Kashiwa, Chiba 277-8568, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Toshihisa","family":"Takagi","sequence":"additional","affiliation":[{"name":"Department of Computational Biology, Graduate School of Frontier Sciences, University of Tokyo, 5-1-5 Kashiwanoha, Kashiwa, Chiba 277-8568, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2007,7,1]]},"reference":[{"key":"2023062708515900800_B1","doi-asserted-by":"crossref","first-page":"489","DOI":"10.1038\/387489a0","article-title":"Evidence for a clade of nematodes, arthropods and other moulting animals","volume":"387","author":"Aguinaldo","year":"1997","journal-title":"Nature"},{"key":"2023062708515900800_B2","doi-asserted-by":"crossref","first-page":"509","DOI":"10.1126\/science.286.5439.509","article-title":"Emergence of scaling in random networks","volume":"286","author":"Barabasi","year":"1999","journal-title":"Science"},{"key":"2023062708515900800_B3","doi-asserted-by":"crossref","first-page":"14332","DOI":"10.1073\/pnas.0504068102","article-title":"Highways of gene sharing in prokaryotes","volume":"102","author":"Beiko","year":"2005","journal-title":"Proc. Natl. Acad. Sci. U. S. A"},{"issue":"A3(2)","key":"2023062708515900800_B4","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1038\/417141a","article-title":"Complete genome sequence of the model actinomycete Streptomyces coelicolor","volume":"417","author":"Bentley","year":"2002","journal-title":"Nature"},{"key":"2023062708515900800_B5","doi-asserted-by":"crossref","first-page":"7","DOI":"10.1186\/1471-2148-2-7","article-title":"The evolutionary position of nematodes","volume":"2","author":"Blair","year":"2002","journal-title":"BMC Evol. Biol"},{"key":"2023062708515900800_B6","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1101\/gr.751803","article-title":"A recent polyploidy superimposed on older large-scale duplications in the Arabidopsis genome","volume":"13","author":"Blanc","year":"2003","journal-title":"Genome Res"},{"key":"2023062708515900800_B7","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1007\/s00294-006-0078-x","article-title":"On the origin and functions of RNA-mediated silencing: from protists to man","volume":"50","author":"Cerutti","year":"2006","journal-title":"Curr. Genet"},{"key":"2023062708515900800_B8","doi-asserted-by":"crossref","first-page":"1283","DOI":"10.1126\/science.1123061","article-title":"Toward automatic reconstruction of a highly resolved tree of life","volume":"311","author":"Ciccarelli","year":"2006","journal-title":"Science"},{"key":"2023062708515900800_B9","first-page":"206","article-title":"A probabilistic model for gene content evolution with duplication, loss, and horizontal transfer","author":"Cs\u0171r\u00f6s","year":"2006","journal-title":"RECOMB 2006, LNBI 3909"},{"key":"2023062708515900800_B10","doi-asserted-by":"crossref","first-page":"e314","DOI":"10.1371\/journal.pbio.0030314","article-title":"Two rounds of whole genome duplication in the ancestral vertebrate","volume":"3","author":"Dehal","year":"2005","journal-title":"PLoS Biol"},{"key":"2023062708515900800_B11","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1111\/j.2517-6161.1977.tb01600.x","article-title":"Maximum likelihood from incomplete data via the EM algorithm","volume":"39","author":"Dempster","year":"1977","journal-title":"J. R. Stat. Soc. Ser. B-Stat. Methodol"},{"key":"2023062708515900800_B12","doi-asserted-by":"crossref","first-page":"15386","DOI":"10.1073\/pnas.0403984101","article-title":"The timing of eukaryotic evolution: does a relaxed molecular clock reconcile proteins and fossils?","volume":"101","author":"Douzery","year":"2004","journal-title":"Proc. Natl. Acad. Sci. U. S. A"},{"key":"2023062708515900800_B13","doi-asserted-by":"crossref","first-page":"527","DOI":"10.1007\/s00239-003-2575-6","article-title":"The consistent phylogenetic signal in genome trees revealed by reducing the impact of noise","volume":"58","author":"Dutilh","year":"2004","journal-title":"J. Mol. Evol"},{"key":"2023062708515900800_B14","doi-asserted-by":"crossref","first-page":"342","DOI":"10.1046\/j.1365-313X.2003.01810.x","article-title":"A gene encoding an RNase D exonuclease-like protein is required for post-transcriptional silencing in Arabidopsis","volume":"35","author":"Glazov","year":"2003","journal-title":"Plant J"},{"key":"2023062708515900800_B15","doi-asserted-by":"crossref","first-page":"1401","DOI":"10.1093\/molbev\/msh138","article-title":"Genome phylogenetic analysis based on extended gene contents","volume":"21","author":"Gu","year":"2004","journal-title":"Mol. Biol. Evol"},{"key":"2023062708515900800_B16","doi-asserted-by":"crossref","first-page":"1153","DOI":"10.1101\/gr.3567505","article-title":"Estimating the tempo and mode of gene family evolution from comparative genomic data","volume":"15","author":"Hahn","year":"2005","journal-title":"Genome Res"},{"key":"2023062708515900800_B17","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1146\/annurev.ecolsys.35.112202.130124","article-title":"The new view of animal phylogeny","volume":"35","author":"Halanych","year":"2004","journal-title":"Annu. Rev. Ecol. Evol. Syst"},{"key":"2023062708515900800_B18","doi-asserted-by":"crossref","first-page":"753","DOI":"10.1006\/jmbi.2002.5405","article-title":"An expectation maximization algorithm for training hidden substitution models","volume":"317","author":"Holmes","year":"2002","journal-title":"J. Mol. Biol"},{"key":"2023062708515900800_B19","doi-asserted-by":"crossref","first-page":"2044","DOI":"10.1093\/bioinformatics\/bth198","article-title":"Phylogenetic trees based on gene content","volume":"20","author":"Huson","year":"2004","journal-title":"Bioinformatics"},{"key":"2023062708515900800_B20","doi-asserted-by":"crossref","first-page":"526","DOI":"10.1038\/nbt820","article-title":"Complete genome sequence and comparative analysis of the industrial microorganism Streptomyces avermitilis","volume":"21","author":"Ikeda","year":"2003","journal-title":"Nat. Biotechnol"},{"key":"2023062708515900800_B21","doi-asserted-by":"crossref","first-page":"18","DOI":"10.1186\/1471-2148-2-18","article-title":"Birth and death of protein domains: a simple model of evolution explains power law behavior","volume":"2","author":"Karev","year":"2002","journal-title":"BMC Evol. Biol"},{"key":"2023062708515900800_B22","doi-asserted-by":"crossref","first-page":"1889","DOI":"10.1093\/bioinformatics\/btg351","article-title":"Simple stochastic birth and death models of genome evolution: was there enough time for us to evolve?","volume":"19","author":"Karev","year":"2003","journal-title":"Bioinformatics"},{"key":"2023062708515900800_B23","doi-asserted-by":"crossref","first-page":"32","DOI":"10.1186\/1471-2148-4-32","article-title":"Gene family evolution: an in-depth theoretical and simulation analysis of non-linear birth-death-innovation models","volume":"4","author":"Karev","year":"2004","journal-title":"BMC Evol. Biol"},{"key":"2023062708515900800_B24","doi-asserted-by":"crossref","first-page":"670","DOI":"10.1016\/j.tree.2005.09.005","article-title":"The tree of eukaryotes","volume":"20","author":"Keeling","year":"2005","journal-title":"Trends Ecol. Evol"},{"key":"2023062708515900800_B25","doi-asserted-by":"crossref","first-page":"1412","DOI":"10.1093\/bioinformatics\/btg174","article-title":"GeneTRACE-reconstruction of gene content of ancestral species","volume":"19","author":"Kunin","year":"2003","journal-title":"Bioinformatics"},{"key":"2023062708515900800_B26","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1016\/0885-2308(90)90022-X","article-title":"The estimation of stochastic context-free grammars using the inside-outside algorithm","volume":"4","author":"Lari","year":"1990","journal-title":"Comput. Speech Lang"},{"key":"2023062708515900800_B27","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1186\/1471-2148-3-2","article-title":"Algorithms for computing parsimonious evolutionary scenarios for genome evolution, the last universal common ancestor and dominance of horizontal gene transfer in the evolution of prokaryotes","volume":"3","author":"Mirkin","year":"2003","journal-title":"BMC Evol. Biol"},{"key":"2023062708515900800_B28","doi-asserted-by":"crossref","first-page":"267","DOI":"10.1126\/science.1134196","article-title":"The 160-kilobase genome of the bacterial endosymbiont Carsonella","volume":"314","author":"Nakabachi","year":"2006","journal-title":"Science"},{"key":"2023062708515900800_B29","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1007\/s00239-005-0257-2","article-title":"Evolution and diversification of RNA silencing proteins in fungi","volume":"63","author":"Nakayashiki","year":"2006","journal-title":"J. Mol. Evol"},{"key":"2023062708515900800_B30","doi-asserted-by":"crossref","first-page":"612","DOI":"10.1080\/106351599260184","article-title":"The maximum likelihood approach to reconstructing ancestral character states of discrete characters on phylogenies","volume":"48","author":"Pagel","year":"1999","journal-title":"Syst. Biol"},{"key":"2023062708515900800_B31","doi-asserted-by":"crossref","first-page":"241","DOI":"10.1016\/0004-3702(86)90072-X","article-title":"Fusion, propagation, and structuring in belief networks","volume":"29","author":"Pearl","year":"1986","journal-title":"Artif. Intell"},{"key":"2023062708515900800_B32","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":"2023062708515900800_B33","doi-asserted-by":"crossref","first-page":"1699","DOI":"10.2307\/2410994","article-title":"Likelihood of ancestor states in adaptive radiation","volume":"51","author":"Schluter","year":"1997","journal-title":"Evolution"},{"key":"2023062708515900800_B34","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1101\/gr.176501","article-title":"Genomes in flux: the evolution of archaeal and proteobacterial gene content","volume":"12","author":"Snel","year":"2002","journal-title":"Genome Res"},{"key":"2023062708515900800_B35","doi-asserted-by":"crossref","first-page":"631","DOI":"10.1126\/science.278.5338.631","article-title":"A genomic perspective on protein families","volume":"278","author":"Tatusov","year":"1997","journal-title":"Science"},{"key":"2023062708515900800_B36","doi-asserted-by":"crossref","first-page":"58","DOI":"10.1093\/nar\/gkg109","article-title":"MBGD: microbial genome database for comparative analysis","volume":"31","author":"Uchiyama","year":"2003","journal-title":"Nucleic Acids Res"},{"key":"2023062708515900800_B37","doi-asserted-by":"crossref","first-page":"D433","DOI":"10.1093\/nar\/gki005","article-title":"STRING: known and predicted protein-protein associations, integrated and transferred across organisms","volume":"33","author":"von Mering","year":"2005","journal-title":"Nucleic Acids Res"},{"key":"2023062708515900800_B38","doi-asserted-by":"crossref","first-page":"411","DOI":"10.1046\/j.1365-2958.2003.03698.x","article-title":"End-to-end fusion of linear deleted chromosomes initiates a cycle of genome instability in Streptomyces ambofaciens","volume":"50","author":"Wenner","year":"2003","journal-title":"Mol. Microbiol"},{"key":"2023062708515900800_B39","doi-asserted-by":"crossref","first-page":"D187","DOI":"10.1093\/nar\/gkj161","article-title":"The Universal Protein Resource (UniProt): an expanding universe of protein information","volume":"34","author":"Wu","year":"2006","journal-title":"Nucleic Acids Res"},{"key":"2023062708515900800_B40","doi-asserted-by":"crossref","first-page":"747","DOI":"10.1016\/j.cell.2006.09.033","article-title":"Analysis of the C. elegans Argonaute family reveals that distinct Argonautes act sequentially during RNAi","volume":"127","author":"Yigit","year":"2006","journal-title":"Cell"},{"key":"2023062708515900800_B41","doi-asserted-by":"crossref","first-page":"1519","DOI":"10.1126\/science.1111444","article-title":"Ribo-gnome: the big world of small RNAs","volume":"309","author":"Zamore","year":"2005","journal-title":"Science"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/23\/13\/i230\/50714740\/bioinformatics_23_13_i230.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/23\/13\/i230\/50714740\/bioinformatics_23_13_i230.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,19]],"date-time":"2025-01-19T21:38:34Z","timestamp":1737322714000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/23\/13\/i230\/224933"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,7,1]]},"references-count":41,"journal-issue":{"issue":"13","published-print":{"date-parts":[[2007,7,1]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btm165","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"type":"electronic","value":"1367-4811"},{"type":"print","value":"1367-4803"}],"subject":[],"published-other":{"date-parts":[[2007,7]]},"published":{"date-parts":[[2007,7,1]]}}}