{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,11]],"date-time":"2025-12-11T07:30:49Z","timestamp":1765438249083},"reference-count":18,"publisher":"Springer Science and Business Media LLC","issue":"S9","content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["BMC Bioinformatics"],"published-print":{"date-parts":[[2011,12]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:sec>\n            <jats:title>Background<\/jats:title>\n            <jats:p>Segmental duplications in genomes have been studied for many years. Recently, several studies have highlighted a biological phenomenon called <jats:italic>breakpoint-duplication<\/jats:italic> that apparently associates a significant proportion of segmental duplications in Mammals, and the Drosophila species group, to breakpoints in rearrangement events.<\/jats:p>\n          <\/jats:sec>\n          <jats:sec>\n            <jats:title>Results<\/jats:title>\n            <jats:p>In this paper, we introduce and study a combinatorial problem, inspired from the breakpoint-duplication phenomenon, called the <jats:italic>Genome Dedoubling Problem.<\/jats:italic> It consists of finding a minimum length rearrangement scenario required to transform a genome with duplicated segments into a non-duplicated genome such that duplications are caused by rearrangement breakpoints. We show that the problem, in the Double-Cut-and-Join (DCJ) and the reversal rearrangement models, can be reduced to an APX-complete problem, and we provide algorithms for the Genome Dedoubling Problem with 2-approximable parts. We apply the methods for the reconstruction of a non-duplicated ancestor of <jats:italic>Drosophila yakuba.<\/jats:italic>\n            <\/jats:p>\n          <\/jats:sec>\n          <jats:sec>\n            <jats:title>Conclusions<\/jats:title>\n            <jats:p>We present the <jats:italic>Genome Dedoubling Problem<\/jats:italic>, and describe two algorithms solving the problem in the DCJ model, and the reversal model. The usefulness of the problems and the methods are showed through an application to real Drosophila data.<\/jats:p>\n          <\/jats:sec>","DOI":"10.1186\/1471-2105-12-s9-s20","type":"journal-article","created":{"date-parts":[[2011,10,5]],"date-time":"2011-10-05T18:48:11Z","timestamp":1317840491000},"update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["Genome dedoubling by DCJ and reversal"],"prefix":"10.1186","volume":"12","author":[{"given":"Antoine","family":"Thomas","sequence":"first","affiliation":[]},{"given":"Jean-St\u00e9phane","family":"Varr\u00e9","sequence":"additional","affiliation":[]},{"given":"A\u00efda","family":"Ouangraoua","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2011,10,5]]},"reference":[{"key":"4827_CR1","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1038\/nrg705","volume":"6","author":"R Samonte","year":"2002","unstructured":"Samonte R, Eichler E: Segmental duplications and the evolution of the primate genome. Nature Reviews Genetics 2002, 6: 65\u201372.","journal-title":"Nature Reviews Genetics"},{"issue":"17","key":"4827_CR2","doi-asserted-by":"publisher","first-page":"2201","DOI":"10.1093\/hmg\/ddg223","volume":"12","author":"L Armengol","year":"2003","unstructured":"Armengol L, Pujana M, Cheung J, Scherer S, Estivill X: Enrichment of segmental duplications in regions of breaks of synteny between the human and mouse genomes suggest their involvement in evolutionary rearrangements. Human Molecular Genetics 2003, 12(17):2201\u20132208. 10.1093\/hmg\/ddg223","journal-title":"Human Molecular Genetics"},{"issue":"4","key":"4827_CR3","doi-asserted-by":"publisher","first-page":"R23","DOI":"10.1186\/gb-2004-5-4-r23","volume":"5","author":"J Bailey","year":"2004","unstructured":"Bailey J, Baertsch R, Kent W, Haussler D, Eichler E: Hotspots of mammalian chromosomal evolution. Genome Biology 2004, 5(4):R23. 10.1186\/gb-2004-5-4-r23","journal-title":"Genome Biology"},{"issue":"6","key":"4827_CR4","doi-asserted-by":"publisher","first-page":"e152+","DOI":"10.1371\/journal.pbio.0050152","volume":"5","author":"J Ranz","year":"2007","unstructured":"Ranz J, Maurin D, Chan Y, Von Grotthuss M: Principles of genome evolution in the Drosophila melanogaster species group. PLoS biology 2007, 5(6):e152+.","journal-title":"PLoS biology"},{"key":"4827_CR5","doi-asserted-by":"publisher","first-page":"1143","DOI":"10.1534\/genetics.104.038810","volume":"170","author":"L Matzkin","year":"2005","unstructured":"Matzkin L, Merritt T, Zhu CT, Eanes W: The structure and population genetics of the breakpoints associated with the cosmopolitan chromosomal inversion In(3R)Payne in Drosophila melanogaster. Genetics 2005, 170: 1143\u20131152. 10.1534\/genetics.104.038810","journal-title":"Genetics"},{"key":"4827_CR6","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1101\/gr.3059305","volume":"15","author":"S Richards","year":"2005","unstructured":"Richards S, Liu Y, Bettencourt B, Hradecky P, Letovsky S: Comparative genome sequencing of Drosophila pseudoobscura: Chromosomal, gene, and cis-element evolution. Genome Research 2005, 15: 1\u201318. 10.1101\/gr.3059305","journal-title":"Genome Research"},{"issue":"1-2","key":"4827_CR7","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.gene.2009.02.019","volume":"438","author":"R Meisel","year":"2009","unstructured":"Meisel R: Repeat mediated gene duplication in the Drosophila pseudoobscura genome. Gene 2009, 438(1\u20132):1\u20137. 10.1016\/j.gene.2009.02.019","journal-title":"Gene"},{"key":"4827_CR8","doi-asserted-by":"publisher","first-page":"623","DOI":"10.1101\/gr.102970.109","volume":"20","author":"A Quinlan","year":"2010","unstructured":"Quinlan A, Clark R, Sokolova S, Leibowitz M, Zhang Y, Hurles M, Mell J, Hall I: Genome-wide mapping and assembly of structural variant breakpoints in the mouse genome. Genome Research 2010, 20: 623\u2013635. 10.1101\/gr.102970.109","journal-title":"Genome Research"},{"issue":"4","key":"4827_CR9","doi-asserted-by":"publisher","first-page":"525","DOI":"10.1101\/gr.114116.110","volume":"21","author":"KD Howarth","year":"2011","unstructured":"Howarth KD, Pole JCM, Beavis JC, Batty EM, Newman S, Bignell GR, Edwards PAW: Large duplications at reciprocal translocation breakpoints that might be the counterpart of large deletions and could arise from stalled replication bubbles. Genome Research 2011, 21(4):525\u2013534. 10.1101\/gr.114116.110","journal-title":"Genome Research"},{"key":"4827_CR10","doi-asserted-by":"publisher","first-page":"56","DOI":"10.1093\/gbe\/evp006","volume":"1","author":"C Lemaitre","year":"2009","unstructured":"Lemaitre C, Braga M, Gautier C, Sagot MF, Tannier E, Marais G: Footprints of Inversions at Present and Past Pseudoautosomal Boundaries in Human Sex Chromosomes. Genome Biology 2009, 1: 56\u201366.","journal-title":"Genome Biology"},{"key":"4827_CR11","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1007\/BFb0030793","volume-title":"In proc. of Combinatorial Pattern Matching. LNCS 1448","author":"N El-Mabrouk","year":"1998","unstructured":"El-Mabrouk N, Nadeau J, Sankoff D: Genome Halving. In In proc. of Combinatorial Pattern Matching. LNCS 1448. Springer; 1998:235\u2013250."},{"key":"4827_CR12","first-page":"581","volume-title":"In proc. of FOCS 1995","author":"S Hannenhalli","year":"1995","unstructured":"Hannenhalli S, Pevzner PA: Transforming Men into Mice (Polynomial Algorithm for Genomic Distance Problem). In In proc. of FOCS 1995. IEEE Press; 1995:581\u2013592."},{"issue":"2","key":"4827_CR13","doi-asserted-by":"publisher","first-page":"134","DOI":"10.1016\/j.dam.2004.04.010","volume":"146","author":"A Bergeron","year":"2005","unstructured":"Bergeron A: A very elementary presentation of the Hannenhalli-Pevzner theory. Discrete Applied Mathematics 2005, 146(2):134\u2013145. 10.1016\/j.dam.2004.04.010","journal-title":"Discrete Applied Mathematics"},{"key":"4827_CR14","doi-asserted-by":"publisher","first-page":"388","DOI":"10.1007\/978-3-540-27801-6_29","volume-title":"In proc. of Combinatorial Pattern Matching. LNCS 3109","author":"A Bergeron","year":"2004","unstructured":"Bergeron A, Mixtacki J, Stoye J: Reversal distance without hurdles and fortresses. In In proc. of Combinatorial Pattern Matching. LNCS 3109. Springer-Verlag; 2004:388\u2013399."},{"issue":"1112","key":"4827_CR15","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1098\/rspb.1976.0046","volume":"193","author":"F Lemeunier","year":"1976","unstructured":"Lemeunier F, Ashburner M: Relationships within the melanogaster species subgroup of the genus Drosophila (Sophophora). II. Phylogenetic relationships between six species based upon polytene chromosome banding sequences. Proceedings of the Royal Society of London, Series B, Biological Science 1976, 193(1112):275\u2013294. 10.1098\/rspb.1976.0046","journal-title":"Proceedings of the Royal Society of London, Series B, Biological Science"},{"key":"4827_CR16","doi-asserted-by":"crossref","first-page":"319","DOI":"10.1177\/117693430600200028","volume":"2","author":"C Zheng","year":"2006","unstructured":"Zheng C, Zhu Q, Sankoff D: Genome halving with an outgroup. Evolutionary Bioinformatics 2006, 2: 319\u2013326.","journal-title":"Evolutionary Bioinformatics"},{"key":"4827_CR17","doi-asserted-by":"publisher","first-page":"449","DOI":"10.1007\/3-540-60220-8_84","volume-title":"In proc. of Workshop on Algorithms and Data Structures. LNCS 955","author":"P Berman","year":"1995","unstructured":"Berman P, Fujito T: Approximating independent sets in degree 3 graphs. In In proc. of Workshop on Algorithms and Data Structures. LNCS 955. Springer-Verlag; 1995:449\u2013460."},{"key":"4827_CR18","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1016\/0166-218X(83)90080-X","volume":"6","author":"DS Hochbaum","year":"2004","unstructured":"Hochbaum DS: Efficient bounds for the stable set, vertex cover and set packing problems. Discrete Applied Mathematics 2004, 6: 243\u2013254.","journal-title":"Discrete Applied Mathematics"}],"container-title":["BMC Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/1471-2105-12-S9-S20.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,9,1]],"date-time":"2021-09-01T16:48:52Z","timestamp":1630514932000},"score":1,"resource":{"primary":{"URL":"https:\/\/bmcbioinformatics.biomedcentral.com\/articles\/10.1186\/1471-2105-12-S9-S20"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,10,5]]},"references-count":18,"journal-issue":{"issue":"S9","published-print":{"date-parts":[[2011,12]]}},"alternative-id":["4827"],"URL":"https:\/\/doi.org\/10.1186\/1471-2105-12-s9-s20","relation":{},"ISSN":["1471-2105"],"issn-type":[{"value":"1471-2105","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,10,5]]},"assertion":[{"value":"5 October 2011","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"S20"}}