{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,18]],"date-time":"2026-03-18T21:37:34Z","timestamp":1773869854102,"version":"3.50.1"},"reference-count":35,"publisher":"Oxford University Press (OUP)","issue":"13","license":[{"start":{"date-parts":[[2016,10,2]],"date-time":"2016-10-02T00:00:00Z","timestamp":1475366400000},"content-version":"vor","delay-in-days":3015,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc\/2.0\/uk\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2008,7,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Motivation: Deciphering the location of gene duplications and multiple gene duplication episodes on the Tree of Life is fundamental to understanding the way gene families and genomes evolve. The multiple gene duplication problem provides a framework for placing gene duplication events onto nodes of a given species tree, and detecting episodes of multiple gene duplication. One version of the multiple gene duplication problem was defined by Guig\u00f3 et al. in 1996. Several heuristic solutions have since been proposed for this problem, but no exact algorithms were known.<\/jats:p>\n               <jats:p>Results: In this article we solve this longstanding open problem by providing the first exact and efficient solution. We also demonstrate the improvement offered by our algorithm over the best heuristic approaches, by applying it to several simulated as well as empirical datasets.<\/jats:p>\n               <jats:p>Contact: \u00a0oeulenst@cs.iastate.edu<\/jats:p>","DOI":"10.1093\/bioinformatics\/btn150","type":"journal-article","created":{"date-parts":[[2008,6,27]],"date-time":"2008-06-27T07:43:13Z","timestamp":1214552593000},"page":"i132-i138","source":"Crossref","is-referenced-by-count":40,"title":["The multiple gene duplication problem revisited"],"prefix":"10.1093","volume":"24","author":[{"given":"Mukul S.","family":"Bansal","sequence":"first","affiliation":[{"name":"Department of Computer Science, Iowa State University, Ames, IA 50011, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Oliver","family":"Eulenstein","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Iowa State University, Ames, IA 50011, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2008,7,1]]},"reference":[{"key":"2023020210355465200_B1","first-page":"7","article-title":"Bayesian gene\/species tree reconciliation and orthology analysis using mcmc. In","author":"Arvestad","year":"2003"},{"key":"2023020210355465200_B2","first-page":"326","article-title":"Gene tree reconstruction and orthology analysis based on an integrated model for duplications and sequence evolution. In","author":"Arvestad","year":"2004"},{"key":"2023020210355465200_B3","doi-asserted-by":"crossref","first-page":"1093","DOI":"10.1105\/tpc.021345","article-title":"Widespread paleopolyploidy in model plant species inferred from age distributions of duplicate genes","volume":"16","author":"Blanc","year":"2004","journal-title":"Plant Cell"},{"key":"2023020210355465200_B4","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1101\/gr.751803","article-title":"A recent polyploidy superimposed on older large-scale duplications in theArabidopsis genome","volume":"13","author":"Blanc","year":"2003","journal-title":"Genome Res"},{"key":"2023020210355465200_B5","doi-asserted-by":"crossref","first-page":"36","DOI":"10.1016\/j.tcs.2005.05.016","article-title":"Reconciling a gene tree to a species tree under the duplication cost model","volume":"347","author":"Bonizzoni","year":"2005","journal-title":"Theor. Comput. Sci."},{"key":"2023020210355465200_B6","doi-asserted-by":"crossref","first-page":"433","DOI":"10.1038\/nature01521","article-title":"Unravelling angiosperm genome evolution by phylogenetic analysis of chromosomal duplication events","volume":"422","author":"Bowers","year":"2003","journal-title":"Nature"},{"key":"2023020210355465200_B7","first-page":"273","article-title":"Locating multiple gene duplications through reconciled trees. Vol. 4955 in","volume-title":"Lecture Notes in Computer Science","author":"Burleigh","year":"2008"},{"key":"2023020210355465200_B8","doi-asserted-by":"crossref","first-page":"14959","DOI":"10.1073\/pnas.0603228103","article-title":"Legume genome evolution viewed through the Medicago truncatula and Lotus japonicus genomes","volume":"103","author":"Cannon","year":"2006","journal-title":"Proc. Natl Acad. Sci."},{"key":"2023020210355465200_B9","doi-asserted-by":"crossref","first-page":"429","DOI":"10.1089\/106652700750050871","article-title":"Notung: a program for dating gene duplications and optimizing gene family trees","volume":"7","author":"Chen","year":"2000","journal-title":"J. Comput. Biol."},{"key":"2023020210355465200_B10","first-page":"103","article-title":"Analogs & duals of the MAST problem for sequences & trees. Vol. 1533 in","volume-title":"Lecture Notes in Computer Science","author":"Fellows","year":"1998"},{"key":"2023020210355465200_B11","first-page":"347","article-title":"On the multiple gene duplication problem. In","author":"Fellows","year":"1998"},{"key":"2023020210355465200_B12","doi-asserted-by":"crossref","first-page":"132","DOI":"10.2307\/2412519","article-title":"Fitting the gene lineage into its species lineage. a parsimony strategy illustrated by cladograms constructed from globin sequences","volume":"28","author":"Goodman","year":"1979","journal-title":"Syst. Zool."},{"key":"2023020210355465200_B13","article-title":"On the structure of reconciliations. In","volume-title":"Recomb Comparative Genomics Workshop 2004","author":"G\u00f3recki","year":"2004"},{"key":"2023020210355465200_B14","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1006\/mpev.1996.0071","article-title":"Reconstruction of ancient molecular phylogeny","volume":"6","author":"Guig\u00f3","year":"1996","journal-title":"Mol. Phylogenet. Evol."},{"key":"2023020210355465200_B15","doi-asserted-by":"crossref","first-page":"610","DOI":"10.1139\/g04-016","article-title":"Ancestral genome duplication in rice","volume":"47","author":"Guyot","year":"2004","journal-title":"Genome"},{"key":"2023020210355465200_B16","first-page":"138","article-title":"New algorithms for the duplication-loss model. In","author":"Hallett","year":"2000"},{"key":"2023020210355465200_B17","doi-asserted-by":"crossref","first-page":"729","DOI":"10.1137\/S0097539798343362","article-title":"From gene trees to species trees","volume":"30","author":"Ma","year":"2000","journal-title":"SIAM J. Comput."},{"key":"2023020210355465200_B18","doi-asserted-by":"crossref","first-page":"493","DOI":"10.1089\/cmb.1995.2.493","article-title":"A biologically consistent model for comparing molecular phylogenies","volume":"2","author":"Mirkin","year":"1995","journal-title":"J. Comput. Biol."},{"key":"2023020210355465200_B19","first-page":"58","article-title":"Maps between trees and cladistic analysis of historical associations among genes, organisms and areas","volume":"43","author":"Page","year":"1994","journal-title":"Syst. Biol."},{"key":"2023020210355465200_B20","first-page":"536","article-title":"Vertebrate phylogenomics: reconciled trees and gene duplications. In","author":"Page","year":"2002"},{"key":"2023020210355465200_B21","doi-asserted-by":"crossref","first-page":"9903","DOI":"10.1073\/pnas.0307901101","article-title":"Ancient polyploidization predating divergence of the cereals, and its consequences for comparative genomics","volume":"101","author":"Paterson","year":"2004","journal-title":"Proc. Natl. Acad. Sci."},{"key":"2023020210355465200_B22","doi-asserted-by":"crossref","first-page":"130","DOI":"10.1186\/1471-2148-7-130","article-title":"An ancient genome duplication contributed to the abundance of metabolic genes in the moss physcomitrella patens","volume":"7","author":"Rensing","year":"2007","journal-title":"BMC Evol. Biol."},{"key":"2023020210355465200_B23","doi-asserted-by":"crossref","first-page":"389","DOI":"10.1534\/genetics.166.1.389","article-title":"A 3347-locus genetic recombination map of sequence-tagged sites reveals features of genome organization, transmission and evolution of cotton (Gossypium)","volume":"166","author":"Rong","year":"2004","journal-title":"Genetics"},{"key":"2023020210355465200_B24","doi-asserted-by":"crossref","first-page":"868","DOI":"10.1139\/g04-047","article-title":"Mining EST databases to resolve evolutionary events in major crop species","volume":"47","author":"Schlueter","year":"2004","journal-title":"Genome"},{"key":"2023020210355465200_B25","doi-asserted-by":"crossref","first-page":"1152","DOI":"10.1105\/tpc.106.041111","article-title":"Independent ancient polyploidy events in sister families Brassicaceae and Cleomaceae","volume":"18","author":"Schranz","year":"2006","journal-title":"Plant Cell"},{"key":"2023020210355465200_B26","doi-asserted-by":"crossref","first-page":"13627","DOI":"10.1073\/pnas.212522399","article-title":"The hidden duplication past of Arabidopsis thaliana","volume":"99","author":"Simillion","year":"2002","journal-title":"Proc. Natl. Acad. Sci."},{"key":"2023020210355465200_B27","doi-asserted-by":"crossref","DOI":"10.1007\/3-540-48447-7_29","article-title":"Gene trees and species trees: the gene-duplication problem is fixed-parameter tractable. In","author":"Stege","year":"1999"},{"key":"2023020210355465200_B28","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1111\/j.1469-8137.2005.01378.x","article-title":"EST data suggest that poplar is an ancient polyploidy","volume":"167","author":"Sterck","year":"2005","journal-title":"New Phytol."},{"key":"2023020210355465200_B29","doi-asserted-by":"crossref","first-page":"2192","DOI":"10.1105\/tpc.014019","article-title":"Evidence that rice and other cereals are ancient aneuploids","volume":"15","author":"Vandepoele","year":"2003","journal-title":"Plant Cell"},{"key":"2023020210355465200_B30","doi-asserted-by":"crossref","first-page":"2114","DOI":"10.1126\/science.290.5499.2114","article-title":"The origins of genome duplications in Arabidopsis","volume":"290","author":"Vision","year":"2000","journal-title":"Science"},{"key":"2023020210355465200_B31","doi-asserted-by":"crossref","first-page":"937","DOI":"10.1111\/j.1469-8137.2004.01293.x","article-title":"Duplication and DNA segmental loss in the rice genome: implications for diploidization","volume":"165","author":"Wang","year":"2005","journal-title":"New Phytol."},{"key":"2023020210355465200_B32","first-page":"549","article-title":"Automatic genome-wide reconstruction of phylogenetic gene trees. In","author":"Wapinski","year":"2007"},{"key":"2023020210355465200_B33","doi-asserted-by":"crossref","first-page":"54","DOI":"10.1038\/nature06107","article-title":"Natural history and evolutionary principles of gene duplication in fungi","volume":"449","author":"Wapinski","year":"2007","journal-title":"Nature"},{"key":"2023020210355465200_B34","doi-asserted-by":"crossref","first-page":"266","DOI":"10.1371\/journal.pbio.0030038","article-title":"The genomes of Oryza sativa: a history of duplication","volume":"3","author":"Yu","year":"2005","journal-title":"PLoS Biol."},{"key":"2023020210355465200_B35","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1089\/cmb.1997.4.177","article-title":"On a Mirkin-Muchnik-Smith conjecture for comparing molecular phylogenies","volume":"4","author":"Zhang","year":"1997","journal-title":"J. Comput. Biol."}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/24\/13\/i132\/49051363\/bioinformatics_24_13_i132.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/24\/13\/i132\/49051363\/bioinformatics_24_13_i132.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,2]],"date-time":"2023-02-02T12:13:35Z","timestamp":1675340015000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/24\/13\/i132\/229115"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,7,1]]},"references-count":35,"journal-issue":{"issue":"13","published-print":{"date-parts":[[2008,7,1]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btn150","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2008,7,1]]},"published":{"date-parts":[[2008,7,1]]}}}