{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,19]],"date-time":"2025-03-19T12:00:27Z","timestamp":1742385627505},"reference-count":22,"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":"Abstract<\/jats:title>\n Motivation: Some present day species have incurred a whole genome doubling event in their evolutionary history, and this is reflected today in patterns of duplicated segments scattered throughout their chromosomes. These duplications may be used as data to \u2018halve\u2019 the genome, i.e. to reconstruct the ancestral genome at the moment of doubling, but the solution is often highly nonunique. To resolve this problem, we take account of outgroups, external reference genomes, to guide and narrow down the search.<\/jats:p>\n Results: We improve on a previous, computationally costly, \u2018brute force\u2019 method by adapting the genome halving algorithm of El-Mabrouk and Sankoff so that it rapidly and accurately constructs an ancestor close the outgroups, prior to a local optimization heuristic. We apply this to reconstruct the predoubling ancestor of Saccharomyces cerevisiae and Candida glabrata, guided by the genomes of three other yeasts that diverged before the genome doubling event. We analyze the results in terms (1) of the minimum evolution criterion, (2) how close the genome halving result is to the final (local) minimum and (3) how close the final result is to an ancestor manually constructed by an expert with access to additional information. We also visualize the set of reconstructed ancestors using classic multidimensional scaling to see what aspects of the two doubled and three unduplicated genomes influence the differences among the reconstructions.<\/jats:p>\n Availability: The experimental software is available on request.<\/jats:p>\n Contact: \u00a0sankoff@uottawa.ca<\/jats:p>","DOI":"10.1093\/bioinformatics\/btn146","type":"journal-article","created":{"date-parts":[[2008,6,27]],"date-time":"2008-06-27T07:43:13Z","timestamp":1214552593000},"page":"i96-i104","source":"Crossref","is-referenced-by-count":26,"title":["Guided genome halving: hardness, heuristics and the history of the Hemiascomycetes"],"prefix":"10.1093","volume":"24","author":[{"given":"Chunfang","family":"Zheng","sequence":"first","affiliation":[{"name":"1 Department of Biology, 2Department of Biochemistry, Microbiology and Immunology, 3School of Information Technology and Engineering and 4Department of Mathematics and Statistics, University of Ottawa, Ottawa, Ontario, Canada"}]},{"given":"Qian","family":"Zhu","sequence":"additional","affiliation":[{"name":"1 Department of Biology, 2Department of Biochemistry, Microbiology and Immunology, 3School of Information Technology and Engineering and 4Department of Mathematics and Statistics, University of Ottawa, Ottawa, Ontario, Canada"}]},{"given":"Zaky","family":"Adam","sequence":"additional","affiliation":[{"name":"1 Department of Biology, 2Department of Biochemistry, Microbiology and Immunology, 3School of Information Technology and Engineering and 4Department of Mathematics and Statistics, University of Ottawa, Ottawa, Ontario, Canada"}]},{"given":"David","family":"Sankoff","sequence":"additional","affiliation":[{"name":"1 Department of Biology, 2Department of Biochemistry, Microbiology and Immunology, 3School of Information Technology and Engineering and 4Department of Mathematics and Statistics, University of Ottawa, Ottawa, Ontario, Canada"}]}],"member":"286","published-online":{"date-parts":[[2008,7,1]]},"reference":[{"key":"2023020210393696900_B1","first-page":"163","article-title":"A unifying view of genome rearrangements. In","volume-title":"Algorithms in Bioinformatics. Proceedings of WABI 2006. Lecture Notes in Computer Science","author":"Bergeron","year":"2006"},{"key":"2023020210393696900_B2","first-page":"26","article-title":"Genome-scale evolution: reconstructing gene orders in the ancestral species","volume":"12","author":"Bourque","year":"2002","journal-title":"Genome Res"},{"key":"2023020210393696900_B3","article-title":"The complexity of the breakpoint median problem","volume-title":"Technical Report CRM\u20132579","author":"Bryant","year":"1998"},{"key":"2023020210393696900_B4","doi-asserted-by":"crossref","first-page":"1456","DOI":"10.1101\/gr.3672305","article-title":"The Yeast Gene Order Browser: combining curated homology and syntenic context reveals gene fate in polyploid species","volume":"15","author":"Byrne","year":"2005","journal-title":"Genome Res"},{"key":"2023020210393696900_B5","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1287\/ijoc.15.1.93.15155","article-title":"The reversals median problem","volume":"15","author":"Caprara","year":"2003","journal-title":"INFORMS J. Comput"},{"key":"2023020210393696900_B6","first-page":"277","article-title":"Algorithms for the extraction of synteny blocks from comparative maps. In","volume-title":"Proceedings of the WABI 2007 Workshop on Algorithms in Bioinformatics. Lecture Notes in Bioinformatics 4645","author":"Choi","year":"2007"},{"key":"2023020210393696900_B7","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1038\/nature02579","article-title":"Genome evolution in yeasts","volume":"430","author":"Dujon","year":"2004","journal-title":"Nature"},{"key":"2023020210393696900_B8","doi-asserted-by":"crossref","first-page":"754","DOI":"10.1137\/S0097539700377177","article-title":"The reconstruction of doubled genomes","volume":"32","author":"El-Mabrouk","year":"2003","journal-title":"SIAM J. Comput"},{"key":"2023020210393696900_B9","doi-asserted-by":"crossref","first-page":"154","DOI":"10.1145\/299432.299475","article-title":"Reconstructing the pre-doubling genome. In","volume-title":"Proceedings of the Third Annual International Conference on Computational Molecular Biology (RECOMB 99)","author":"El-Mabrouk","year":"1999"},{"key":"2023020210393696900_B10","first-page":"1051","article-title":"Life with 6000 genes","volume":"275","author":"Goffeau","year":"1996","journal-title":"Science"},{"key":"2023020210393696900_B11","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1093\/biomet\/53.3-4.325","article-title":"Some distance properties of latent root and vector methods used in multivariate analysis","volume":"53","author":"Gower","year":"1966","journal-title":"Biometrika"},{"key":"2023020210393696900_B12","unstructured":"GRAPPA (Genome Rearrangements Analysis under Parsimony and Other Phylogenetic Algorithms.)\n (Date last accessed May 2008)\n Available at http:\/\/www.cs.unm.edu\/~moret\/GRAPPA\/"},{"key":"2023020210393696900_B13","doi-asserted-by":"crossref","first-page":"417","DOI":"10.1016\/S1567-1356(03)00012-6","article-title":"Phylogenetic relationships among yeasts of the \u2018Saccharomyces complex\u2019 determined from multigene sequence analyses","volume":"3","author":"Kurtzman","year":"2003","journal-title":"FEMS Yeast Res"},{"key":"2023020210393696900_B14","unstructured":"Pe'er\n I\n \n \u00a0ShamirR\n The median problems for breakpoints are NP- complete\n Electronic Colloquium on Computational Complexity Technical Report 98-071\n 1998\n Date last accessed May 2008\n Available at http:\/\/www.eccc.uni-trier.de\/eccc"},{"key":"2023020210393696900_B15","unstructured":"R Development Core Team\n R: A language and environment for statistical computing\n R Foundation for Statistical Computing\n 2007\n Date last accessed May 2008\n Available at http:\/\/www.R-project.org"},{"key":"2023020210393696900_B16","doi-asserted-by":"crossref","first-page":"i433","DOI":"10.1093\/bioinformatics\/btm169","article-title":"Polyploids, genome halving and phylogeny","volume":"23","author":"Sankoff","year":"2007","journal-title":"Bioinformatics"},{"key":"2023020210393696900_B17","doi-asserted-by":"crossref","first-page":"587","DOI":"10.1016\/S0022-0000(02)00011-9","article-title":"Efficient algorithms for multichromosomal genome rearrangements","volume":"65","author":"Tesler","year":"2002","journal-title":"J. Comput. Syst. Sci"},{"key":"2023020210393696900_B18","doi-asserted-by":"crossref","first-page":"708","DOI":"10.1038\/42711","article-title":"Molecular evidence for an ancient duplication of the entire yeast genome","volume":"387","author":"Wolfe","year":"1997","journal-title":"Nature"},{"key":"2023020210393696900_B19","doi-asserted-by":"crossref","first-page":"3340","DOI":"10.1093\/bioinformatics\/bti535","article-title":"Efficient sorting of genomic permutations by translocation, inversion, and block interchange","volume":"21","author":"Yancopoulos","year":"2005","journal-title":"Bioinformatics"},{"key":"2023020210393696900_B20","doi-asserted-by":"crossref","first-page":"319","DOI":"10.1177\/117693430600200028","article-title":"Genome halving with an outgroup","volume":"2","author":"Zheng","year":"2006","journal-title":"Evol. Bioinform"},{"key":"2023020210393696900_B21","doi-asserted-by":"crossref","first-page":"515","DOI":"10.1109\/TCBB.2007.1075","article-title":"Removing noise and ambiguities from comparative maps in rearrangement analysis","volume":"4","author":"Zheng","year":"2007","journal-title":"Trans. Comput. Biol. Bioinform"},{"key":"2023020210393696900_B22","first-page":"162","article-title":"Parts of the problem of polyploids in rearrangement phylogeny. In","volume-title":"Proceedings of the RECOMB 2007 Workshop on Comparative Genomics. Lecture Notes in Computer Science 4751","author":"Zheng","year":"2007"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/24\/13\/i96\/49052305\/bioinformatics_24_13_i96.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/24\/13\/i96\/49052305\/bioinformatics_24_13_i96.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,2]],"date-time":"2023-02-02T12:22:35Z","timestamp":1675340555000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/24\/13\/i96\/227404"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,7,1]]},"references-count":22,"journal-issue":{"issue":"13","published-print":{"date-parts":[[2008,7,1]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btn146","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]]}}}