{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T14:36:22Z","timestamp":1761662182383},"reference-count":35,"publisher":"Oxford University Press (OUP)","issue":"7","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005,4,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Motivation: Duplication of an organism's entire genome is a rare but spectacular event, enabling the rapid emergence of multiple new gene functions. Over time, the parallel linkage of duplicated genes across chromosomes may be disrupted by reciprocal translocations, while the intra-chromosomal order of genes may be shuffled by inversions and transpositions. Some duplicate genes may evolve unrecognizably or be deleted. As a consequence, the only detectable signature of an ancient duplication event in a modern genome may be the presence of various chromosomal segments containing parallel paralogous genes, with each segment appearing exactly twice in the genome. The problem of reconstructing the linkage structure of an ancestral genome before duplication is known as genome halving with unordered chromosomes.<\/jats:p>\n               <jats:p>Results: In this paper, we derive a new upper bound on the genome halving distance that is tighter than the best known, and a new lower bound that is almost always tighter than the best known. We also define the notion of genome halving diameter, and obtain both upper and lower bounds for it. Our tighter bounds on genome halving distance yield a new algorithm for reconstructing an ancestral duplicated genome. We create a software package GenomeHalving based on this new algorithm and test it on the yeast genome, identifying a sequence of translocations for halving the yeast genome that is shorter than previously conjectured possible.<\/jats:p>\n               <jats:p>Availability: \u00a0GenomeHalving is available upon email request.<\/jats:p>\n               <jats:p>Contact: \u00a0py@cs.duke.edu; amink@cs.duke.edu<\/jats:p>","DOI":"10.1093\/bioinformatics\/bti107","type":"journal-article","created":{"date-parts":[[2004,10,29]],"date-time":"2004-10-29T00:51:45Z","timestamp":1099011105000},"page":"869-879","source":"Crossref","is-referenced-by-count":5,"title":["Theoretical and practical advances in genome halving"],"prefix":"10.1093","volume":"21","author":[{"given":"Peng","family":"Yin","sequence":"first","affiliation":[{"name":"Department of Computer Science, Duke University Box 90129, Durham, NC 27708-0129, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alexander J.","family":"Hartemink","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Duke University Box 90129, Durham, NC 27708-0129, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2004,10,28]]},"reference":[{"key":"2023013107421159300_B1","unstructured":"AGI: Arabidopsis Genome Initiative. 2000Analysis of the genome sequence of the flowering plant Arabidopsis thaliana. Nature408796\u2013815"},{"key":"2023013107421159300_B2","doi-asserted-by":"crossref","unstructured":"Ahn, S. and Tanksley, S.D. 1993Comparative linkage maps of rice and maize genomes. Proc. Natl Acad. Sci. USA907980\u20137984","DOI":"10.1073\/pnas.90.17.7980"},{"key":"2023013107421159300_B3","unstructured":"Coissac, E., Maillier, E., Netter, P. 1997A comparative study of duplication in bacteria and eukaryotes: the importance of telomeres. Mol. Biol. Evol.141062\u20131074"},{"key":"2023013107421159300_B4","unstructured":"Dietrich, F.S., Voegeli, S., Brachat, S., Lerch, A., Gates, K., Steiner, S., Mohr, C., Pohlmann, R., Luedi, P., Choi, S., et al. 2004The Ashbya gossypii genome as a tool for mapping the ancient Saccharomyces cerevisiae genome. Science304304\u2013307"},{"key":"2023013107421159300_B5","unstructured":"Durand, D. 2003Vertebrate evolution: doubling and shuffling with a full deck. Trends Genet.192\u20135"},{"key":"2023013107421159300_B6","doi-asserted-by":"crossref","unstructured":"El-Mabrouk, N., Nadeau, J.H., Sankoff, D. 1998Genome halving. Lect. Notes Comput. Sci.1448235\u2013250","DOI":"10.1007\/BFb0030793"},{"key":"2023013107421159300_B7","doi-asserted-by":"crossref","unstructured":"El-Mabrouk, N., Bryant, D., Sankoff, D. 1999Reconstructing the pre-doubling genome. Proceedings of the Third Annual International Conference on Computational Molecular Biology (RECOMB99) , New York  ACM Press,  pp. 154\u2013163","DOI":"10.1145\/299432.299475"},{"key":"2023013107421159300_B8","unstructured":"El-Mabrouk, N. 2000Recovery of ancestral tetraploids. In Sankoff, D. and Nadeau, J.H. (Eds.). Comparative Genomics: Empirical and Analytical Approaches to Gene Order Dynamics, Map Alignment and the Evolution of Gene Families. Computational Biology Series , The Netherlands  Kluwer Academic Publishers Vol. 1,  pp. 465\u2013477"},{"key":"2023013107421159300_B9","unstructured":"El-Mabrouk, N. and Sankoff, D. 2002The reconstruction of doubled genomes. SIAM J. Comput.32754\u2013792"},{"key":"2023013107421159300_B10","unstructured":"Fryxell, K.J. 1996The co-evolutation of gene family trees. Trends Genet.12364\u2013369"},{"key":"2023013107421159300_B11","doi-asserted-by":"crossref","unstructured":"Gaut, B.S. and Doebley, J.F. 1997DNA sequence evidence for the segmental allotetraploid origin of maize. Proc. Natl Acad. Sci. USA946809\u20136814","DOI":"10.1073\/pnas.94.13.6809"},{"key":"2023013107421159300_B12","unstructured":"Gibson, T.J. and Spring, J. 2000Evidence in favor of ancient octaploidy in the vertebrate genome. Biochem. Soc. Trans.2259\u2013264"},{"key":"2023013107421159300_B13","doi-asserted-by":"crossref","unstructured":"Gu, X., Wang, Y., Gu, J. 2002Age distribution of human gene families shows significant roles of both large- and small-scale duplications in vertebrate evolution. Nat. Genet.31205\u2013209","DOI":"10.1038\/ng902"},{"key":"2023013107421159300_B14","doi-asserted-by":"crossref","unstructured":"Kellis, M., Birren, B.W., Lander, E.S. 2004Proof and evolutionary analysis of ancient genome duplication in the yeast Saccharomyces cerevisiae. Nature428617\u2013624","DOI":"10.1038\/nature02424"},{"key":"2023013107421159300_B15","doi-asserted-by":"crossref","unstructured":"Ku, H.M., Vision, T., Liu, J., Tanksley, S.D. 2000Comparing sequence segments of the tomato and Arabidopsis genomes: large-scale duplication followed by selective gene loss creates a network of synteny. Proc. Natl Acad. Sci. USA979121\u20139126","DOI":"10.1073\/pnas.160271297"},{"key":"2023013107421159300_B16","unstructured":"Langkj\u00e6r, R.B., Cliften, P.F., Johnston, M., Piskur, J. 2003Yeast genome duplication was followed by asynchronous differentiation of duplicated genes. Nature421848\u2013852"},{"key":"2023013107421159300_B17","doi-asserted-by":"crossref","unstructured":"Llorente, B., Malpertuy, A., Neuveglise, C., de Montigny, J., Aigle, M., Artiguenave, F., Blandin, G., Bolotin-Fukuhara, M., Bon, E., Brottier, P., et al. 2000Genomic exploration of the hemiascomycetous yeasts 18. Comparative analysis of chromosome maps and synteny with Saccharomyces cerevisiae. FEBS Lett.487101\u2013112","DOI":"10.1016\/S0014-5793(00)02289-4"},{"key":"2023013107421159300_B18","doi-asserted-by":"crossref","unstructured":"Llorente, B., Durrens, P., Malpertuy, A., Aigle, M., Artiguenave, F., Blandin, G., Bolotin-Fukuhara, M., Bon, E., Brottier, P., Casaregola, S., et al. 2000Genomic exploration of the hemiascomycetous yeasts 20. Evolution of gene redundancy compared to Saccharomyces cerevisiae. FEBS Lett.487122\u2013133","DOI":"10.1016\/S0014-5793(00)02291-2"},{"key":"2023013107421159300_B19","doi-asserted-by":"crossref","unstructured":"Lundin, L.G. 1993Evolution of vertebrate genome as reflected in paralogous chromosomal regions in man and in the house mouse. Genomics161\u201319","DOI":"10.1006\/geno.1993.1133"},{"key":"2023013107421159300_B20","unstructured":"Lynch, M. and Conery, J.S. 2000The evolutionary fate and consequences of duplicated genes. Science2901151\u20131155"},{"key":"2023013107421159300_B21","doi-asserted-by":"crossref","unstructured":"McLysaght, A., Hokamp, K., Wolfe, K.H. 2002Extensive genomic duplication during early chordate evolution. Nat. Genet.31200\u2013204","DOI":"10.1038\/ng884"},{"key":"2023013107421159300_B22","doi-asserted-by":"crossref","unstructured":"Mewes, H.W., Albermann, K., Bahr, M., Frishman, D., Gleissner, A., Hani, J., Heumann, K., Kleine, K., Maierl, A., Oliver, S.G., Pfeiffer, F., Zollner, A. 1997Overview of the yeast genome. Nature387S7\u2013S65","DOI":"10.1038\/387s007"},{"key":"2023013107421159300_B23","doi-asserted-by":"crossref","unstructured":"Moore, G., Devos, K.M., Wang, Z., Gale, M.D. 1995Cereal genome evolution. Grasses, line up and form a circle. Curr. Biol.5737\u2013739","DOI":"10.1016\/S0960-9822(95)00148-5"},{"key":"2023013107421159300_B24","unstructured":"Nadeau, J.H. 1991Genome duplication and comparative mapping. In Adolph, K.W. (Ed.). Advanced Techniques in Chromosome Research , New York  Marcel Dekker Press,  pp. 269\u2013296"},{"key":"2023013107421159300_B25","unstructured":"Ohno, S. Evolution by Gene Duplication1970, New York  Springer-Verlag Press"},{"key":"2023013107421159300_B26","doi-asserted-by":"crossref","unstructured":"Paterson, A.H., Lan, T.H., Reischmann, K.P., Chang, C., Lin, Y.R., Liu, S.C., Burow, M.D., Kowalski, S.P., Katsar, C.S., DelMonte, T.A., et al. 1996Toward a unified genetic map of higher plants, transcending the monocot-dicot divergence. Nat. Genet.14,  pp. 380\u2013382","DOI":"10.1038\/ng1296-380"},{"key":"2023013107421159300_B27","doi-asserted-by":"crossref","unstructured":"Paterson, A.H., Bowers, J.E., Burow, M.D., Draye, X., Elsik, C.G., Jiang, C.X., Katsar, C.S., Lan, T.H., Lin, Y.R., Ming, R., Wright, R.J. 2000Comparative genomics of plant chromosomes. Plant Cell121523\u20131540","DOI":"10.1007\/978-94-011-4309-7_38"},{"key":"2023013107421159300_B28","doi-asserted-by":"crossref","unstructured":"Scheffler, J.A., Sharpe, A.G., Schmidt, H., Sperling, P., Parkin, I.A.P., Luhs, W., Lydiate, D.J., Heinz, E. 1997Desaturase multigene families of Brassica napus arose through genome duplication. Theor. Appl. Genet.94583\u2013591","DOI":"10.1007\/s001220050454"},{"key":"2023013107421159300_B29","unstructured":"Seoighe, C., Federspiel, N., Jones, T., Hansen, N., Bivolarovic, V., Surzycki, R., Tamse, R., Komp, C., Huizar, L., Davis, R.W., et al. 2000Prevalence of small inversions in yeast gene order evolution. Proc. Natl Acad. Sci. USA9714 433\u201314 437"},{"key":"2023013107421159300_B30","doi-asserted-by":"crossref","unstructured":"Seoighe, C. and Wolfe, K.H. 1998Extent of genomic rearrangement after genome duplication in yeast. Proc. Natl Acad. Sci. USA954447\u20134452","DOI":"10.1073\/pnas.95.8.4447"},{"key":"2023013107421159300_B31","unstructured":"Shoemaker, R.C., Polzin, K., Labate, J., Specht, J., Brummer, E.C., Olson, T., Young, N., Concibido, V., Wilcox, J., Tamulonis, J.P., et al. 1996Genome duplication in soybean. Genetics144329\u2013338"},{"key":"2023013107421159300_B32","unstructured":"Vision, T.J. and Brown, D.G. In Sankoff, D and Nadeau, J.H. (Eds.). Comparative Genomics: Empirical and Analytical Approaches to Gene Order Dynamics, Map Alignment and the Evolution of Gene Families. Computational Biology Series2000, The Netherlands  Kluwer Academic Publishers Vol. 1,  pp. 479\u2013491"},{"key":"2023013107421159300_B33","unstructured":"Vision, T.J., Brown, D.G., Tanksley, S.D. 2000The origins of genomic duplications in Arabidopsis. Science2902114\u20132117"},{"key":"2023013107421159300_B34","unstructured":"Wolfe, K.H. 2001Yesterday's polyploids and the mystery of diploidization. Nat. Rev. Genet.233\u201341"},{"key":"2023013107421159300_B35","unstructured":"Wolfe, K.H. and Shields, D.C. 1997Molecular evidence for an ancient duplication of the entire yeast genome. Nature387708\u2013713"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/21\/7\/869\/48972229\/bioinformatics_21_7_869.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/21\/7\/869\/48972229\/bioinformatics_21_7_869.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,31]],"date-time":"2023-01-31T10:45:35Z","timestamp":1675161935000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/21\/7\/869\/268899"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004,10,28]]},"references-count":35,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2005,4,1]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/bti107","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2005,4,1]]},"published":{"date-parts":[[2004,10,28]]}}}