{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T10:52:12Z","timestamp":1740135132924,"version":"3.37.3"},"reference-count":33,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2016,9,29]],"date-time":"2016-09-29T00:00:00Z","timestamp":1475107200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2016,9,29]],"date-time":"2016-09-29T00:00:00Z","timestamp":1475107200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100000002","name":"National Institutes of Health","doi-asserted-by":"publisher","award":["HG002371-13"],"award-info":[{"award-number":["HG002371-13"]}],"id":[{"id":"10.13039\/100000002","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000002","name":"National Institutes of Health","doi-asserted-by":"publisher","award":["HG007990-03"],"award-info":[{"award-number":["HG007990-03"]}],"id":[{"id":"10.13039\/100000002","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000051","name":"National Human Genome Research Institute","doi-asserted-by":"publisher","award":["5U54HG007990"],"award-info":[{"award-number":["5U54HG007990"]}],"id":[{"id":"10.13039\/100000051","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000051","name":"National Human Genome Research Institute","doi-asserted-by":"publisher","award":["5U54HG007990"],"award-info":[{"award-number":["5U54HG007990"]}],"id":[{"id":"10.13039\/100000051","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["BMC Bioinformatics"],"abstract":"<jats:title>Abstract<\/jats:title><jats:sec>\n                <jats:title>Background<\/jats:title>\n                <jats:p>The study of genomic variation has provided key insights into the functional role of mutations. Predominantly, studies have focused on single nucleotide variants (SNV), which are relatively easy to detect and can be described with rich mathematical models. However, it has been observed that genomes are highly plastic, and that whole regions can be moved, removed or duplicated in bulk. These structural variants (SV) have been shown to have significant impact on phenotype, but their study has been held back by the combinatorial complexity of the underlying models.<\/jats:p>\n              <\/jats:sec><jats:sec>\n                <jats:title>Results<\/jats:title>\n                <jats:p>We describe here a general model of structural variation that encompasses both balanced rearrangements and arbitrary copy-number variants (CNV).<\/jats:p>\n              <\/jats:sec><jats:sec>\n                <jats:title>Conclusions<\/jats:title>\n                <jats:p>In this model, we show that the space of possible evolutionary histories that explain the structural differences between any two genomes can be sampled ergodically.<\/jats:p>\n              <\/jats:sec>","DOI":"10.1186\/s12859-016-1258-4","type":"journal-article","created":{"date-parts":[[2016,9,29]],"date-time":"2016-09-29T12:41:59Z","timestamp":1475152919000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Representing and decomposing genomic structural variants as balanced integer flows on sequence graphs"],"prefix":"10.1186","volume":"17","author":[{"given":"Daniel R.","family":"Zerbino","sequence":"first","affiliation":[]},{"given":"Tracy","family":"Ballinger","sequence":"additional","affiliation":[]},{"given":"Benedict","family":"Paten","sequence":"additional","affiliation":[]},{"given":"Glenn","family":"Hickey","sequence":"additional","affiliation":[]},{"given":"David","family":"Haussler","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2016,9,29]]},"reference":[{"key":"1258_CR1","doi-asserted-by":"publisher","first-page":"52","DOI":"10.1038\/nature09298","volume":"467","author":"The International HapMap3 Consortium","year":"2010","unstructured":"The International HapMap3 Consortium. Integrating common and rare genetic variation in diverse human populations. Nature. 2010; 467:52\u20138.","journal-title":"Nature"},{"key":"1258_CR2","doi-asserted-by":"publisher","first-page":"56","DOI":"10.1038\/nature11632","volume":"491","author":"The 1000 Genomes Project Consortium","year":"2012","unstructured":"The 1000 Genomes Project Consortium. An integrated map of genetic variation from 1,092 human genomes. Nature. 2012; 491:56\u201365.","journal-title":"Nature"},{"key":"1258_CR3","doi-asserted-by":"crossref","unstructured":"Cancer Genome Atlas Research Network. Comprehensive genomic characterization defines human glioblastoma genes and core pathways. Nature. 2008; 455(7216):1061\u20138. doi:http:\/\/dx.doi.org\/10.1038\/nature07385.","DOI":"10.1038\/nature07385"},{"key":"1258_CR4","doi-asserted-by":"publisher","first-page":"993","DOI":"10.1038\/nature08987","volume":"464","author":"The International Cancer Genome Consortium","year":"2010","unstructured":"The International Cancer Genome Consortium. International network of cancer genome projects. Nature. 2010; 464:993\u20138.","journal-title":"Nature"},{"key":"1258_CR5","volume-title":"Evolution of Protein Molecules. Mammalian Protein Metabolism. Vol. 3","author":"T Jukes","year":"1969","unstructured":"Jukes T, Cantor C. Evolution of Protein Molecules. Mammalian Protein Metabolism. Vol. 3. New York: Academic Press; 1969."},{"key":"1258_CR6","doi-asserted-by":"crossref","unstructured":"Yancopoulos S, Attie O, Friedberg R. Efficient sorting of genomic permutations by translocation, inversion and block interchange. Bioinformatics. 2005; 21(16):3340\u2013346. doi:http:\/\/dx.doi.org\/10.1093\/bioinformatics\/bti535.","DOI":"10.1093\/bioinformatics\/bti535"},{"issue":"5","key":"1258_CR7","doi-asserted-by":"publisher","first-page":"1318","DOI":"10.1109\/TCBB.2011.34","volume":"8","author":"P Feij\u00e3o","year":"2011","unstructured":"Feij\u00e3o P, Meidanis J. Scj: A breakpoint-like distance that simplifies real several rearrangement problems. IEEE-ACM Trans Comp Biol Bioinf. 2011; 8(5):1318\u201329.","journal-title":"IEEE-ACM Trans Comp Biol Bioinf"},{"key":"1258_CR8","doi-asserted-by":"crossref","unstructured":"Yancopoulos S, Friedberg R. DCJ path formulation for genome transformations which include insertions, deletions, and duplications. J Comput Biol. 2009; 16(10):1311\u201338. doi:http:\/\/dx.doi.org\/10.1089\/cmb.2009.0092.","DOI":"10.1089\/cmb.2009.0092"},{"key":"1258_CR9","doi-asserted-by":"publisher","first-page":"451","DOI":"10.1146\/annurev.genom.9.081307.164217","volume":"10","author":"F Zhang","year":"2009","unstructured":"Zhang F, Gu W, Hurles M, Lupski J. Copy number variation in human health, disease, and evolution. Annu Rev Hum Genet. 2009; 10:451\u201381.","journal-title":"Annu Rev Hum Genet"},{"key":"1258_CR10","doi-asserted-by":"crossref","unstructured":"Shlien A, Malkin D. Copy number variations and cancer. Genome Med. 2009; 1(6):62. doi:http:\/\/dx.doi.org\/10.1186\/gm62.","DOI":"10.1186\/gm62"},{"issue":"1","key":"1258_CR11","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/300515.300516","volume":"46","author":"S Hannenhalli","year":"1999","unstructured":"Hannenhalli S, Pevzner PA. Transforming cabbage into turnip: polynomial algorithm for sorting signed permutations by reversals. J ACM. 1999; 46(1):1\u201327.","journal-title":"J ACM"},{"key":"1258_CR12","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1007\/11851561_16","volume":"4175","author":"A Bergeron","year":"2006","unstructured":"Bergeron A, Mixtacki J, Stoye J. A unifying view of genome rearrangements. Algorithm Bioinforma. 2006; 4175:163\u201373.","journal-title":"Algorithm Bioinforma"},{"key":"1258_CR13","volume-title":"Statistical Methods in Molecular Evolution","author":"R Durrett","year":"2005","unstructured":"Durrett R. Genome Rearrangement: Recent Progress and Open Problems In: Nielsen R, editor. Statistical Methods in Molecular Evolution. New York: Springer-Verlag: 2005."},{"key":"1258_CR14","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1007\/BFb0030793","volume":"1448","author":"N El-Mabrouk","year":"1998","unstructured":"El-Mabrouk N, Nadeau JH, Sankoff D. Genome halving. Lect Notes Comput Sci. 1998; 1448:235\u201350.","journal-title":"Lect Notes Comput Sci"},{"key":"1258_CR15","first-page":"83","volume":"10","author":"N El-Mabrouk","year":"1999","unstructured":"El-Mabrouk N, Sankoff D. On the reconstruction of ancient doubled circular genomes using minimum reversal. Genome Inf. 1999; 10:83\u201393.","journal-title":"Genome Inf"},{"key":"1258_CR16","volume-title":"Proc. Third Ann. Int\u2019l Conf. Computational Molecular Biology (RECOMB)","author":"N El-Mabrouk","year":"1999","unstructured":"El-Mabrouk N, Bryant B, Sankoff D. Reconstructing the pre-doubling genome. In: Proc. Third Ann. Int\u2019l Conf. Computational Molecular Biology (RECOMB). Berlin: Springer-Verlag: 1999. p. 153\u2013163."},{"key":"1258_CR17","doi-asserted-by":"publisher","first-page":"754","DOI":"10.1137\/S0097539700377177","volume":"32","author":"N El-Mabrouk","year":"2003","unstructured":"El-Mabrouk N, Sankoff D. The reconstruction of doubled genomes. SIAM J Comput. 2003; 32:754\u201392.","journal-title":"SIAM J Comput"},{"issue":"1","key":"1258_CR18","doi-asserted-by":"publisher","first-page":"98","DOI":"10.1109\/TCBB.2007.1002","volume":"4","author":"MA Alekseyev","year":"2007","unstructured":"Alekseyev MA, Pevzner PA. Colored de bruijn graphs and the genome halving problem. IEEE-ACM Trans Comp Biol Bioinf. 2007; 4(1):98\u2013107.","journal-title":"IEEE-ACM Trans Comp Biol Bioinf"},{"key":"1258_CR19","first-page":"105","volume":"1","author":"N El-Mabrouk","year":"2001","unstructured":"El-Mabrouk N. Sorting signed permutations by reversals and insertions\/deletions of contiguous segments. J Discrete Algorithm. 2001; 1:105\u201322.","journal-title":"J Discrete Algorithm"},{"key":"1258_CR20","doi-asserted-by":"crossref","unstructured":"Braga MDV, Willing E, Stoye J. Double cut and join with insertions and deletions. J Comput Biol. 2011; 18(9):1167\u201384. doi:http:\/\/dx.doi.org\/10.1089\/cmb.2011.0118.","DOI":"10.1089\/cmb.2011.0118"},{"issue":"4","key":"1258_CR21","doi-asserted-by":"publisher","first-page":"302","DOI":"10.1109\/TCBB.2005.48","volume":"2","author":"X Chen","year":"2005","unstructured":"Chen X, Zheng J, Fu Z, Nan P, Zhong Y, Lonardi S, Jiang T. Assignment of orthologous genes via genome rearrangement. IEEE-ACM Trans Comp Biol Bioinf. 2005; 2(4):302\u201315.","journal-title":"IEEE-ACM Trans Comp Biol Bioinf"},{"issue":"Suppl 19","key":"1258_CR22","doi-asserted-by":"publisher","first-page":"513","DOI":"10.1186\/1471-2105-13-S19-S13","volume":"13","author":"M Shao","year":"2012","unstructured":"Shao M, Lin Y. Approximating the edit distance for genomes with duplicate genes under dcj, insertion and deletion. BMC Bioinforma. 2012; 13(Suppl 19):513.","journal-title":"BMC Bioinforma"},{"key":"1258_CR23","doi-asserted-by":"publisher","first-page":"329","DOI":"10.1093\/bioinformatics\/btv229","volume":"31","author":"M Shao","year":"2015","unstructured":"Shao M, Moret BME. Comparing genomes with rearrangements and segmental duplications. Bioinformatics. 2015; 31:329\u20138.","journal-title":"Bioinformatics"},{"issue":"Suppl 15","key":"1258_CR24","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1186\/1471-2105-14-S15-S9","volume":"14","author":"M Shao","year":"2013","unstructured":"Shao M, Lin Y, Moret BME. Sorting genomes with rearrangements and segmental duplications through trajectory graphs. BMC Bioinforma. 2013; 14(Suppl 15):9.","journal-title":"BMC Bioinforma"},{"key":"1258_CR25","doi-asserted-by":"crossref","unstructured":"Bader M. Sorting by reversals, block interchanges, tandem duplications, and deletions. BMC Bioinforma. 2009; 10(Suppl 1):9. doi:http:\/\/dx.doi.org\/10.1186\/1471-2105-10-S1-S9.","DOI":"10.1186\/1471-2105-10-S1-S9"},{"issue":"Suppl 1","key":"1258_CR26","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1186\/1471-2105-11-S1-S27","volume":"11","author":"M Bader","year":"2010","unstructured":"Bader M. Genome rearrangements with duplications. BMC Bioinforma. 2010; 11(Suppl 1):27.","journal-title":"BMC Bioinforma"},{"issue":"10","key":"1258_CR27","doi-asserted-by":"publisher","first-page":"1445","DOI":"10.1089\/cmb.2009.0083","volume":"16","author":"M Ozery-Flato","year":"2009","unstructured":"Ozery-Flato M, Shamir R. Sorting cancer karyotypes by elementary operations. J Comput Biol. 2009; 16(10):1445\u201360.","journal-title":"J Comput Biol"},{"key":"1258_CR28","doi-asserted-by":"crossref","unstructured":"Zeira R, Shamir R. Sorting by cuts, joins and whole chromosome duplications. Combinatorial Pattern Matching. Lecture Notes in Computer Science. vol. 9133. Heidelberg: Springer: 2015. p. 396\u2013409.","DOI":"10.1007\/978-3-319-19929-0_34"},{"key":"1258_CR29","doi-asserted-by":"publisher","first-page":"206","DOI":"10.1186\/1471-2105-15-206","volume":"15","author":"B Paten","year":"2014","unstructured":"Paten B, Zerbino D, Hickey G, Haussler D. A unifying parsimony model of genome evolution. BMC Bioinforma. 2014; 15:206.","journal-title":"BMC Bioinforma"},{"key":"1258_CR30","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1007\/BF01188582","volume":"13","author":"PA Pevzner","year":"1995","unstructured":"Pevzner PA. DNA phyical mapping and alternating eulerian cycles in colored graphs. Algorithmica. 1995; 13:77\u2013105.","journal-title":"Algorithmica"},{"issue":"1","key":"1258_CR31","first-page":"76","volume":"18","author":"A Kotzig","year":"1968","unstructured":"Kotzig A. Moves without forbidden transitions in a graph. Matematick\u00fd \u010dasopis. 1968; 18(1):76\u201380.","journal-title":"Matematick\u00fd \u010dasopis"},{"key":"1258_CR32","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1073\/pnas.39.4.315","volume":"39","author":"F Harary","year":"1952","unstructured":"Harary F, Uhlenbeck GE. On the number of husimi trees: I. Proc Natl Acad Sci. 1952; 39:315\u201322.","journal-title":"Proc Natl Acad Sci"},{"key":"1258_CR33","doi-asserted-by":"crossref","first-page":"22","DOI":"10.4064\/fm-28-1-22-32","volume":"28","author":"S MacLane","year":"1937","unstructured":"MacLane S. A combinatorial condition for planar graphs. Fundam Math. 1937; 28:22\u201332.","journal-title":"Fundam Math"}],"container-title":["BMC Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s12859-016-1258-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1186\/s12859-016-1258-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s12859-016-1258-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,2,1]],"date-time":"2024-02-01T17:58:14Z","timestamp":1706810294000},"score":1,"resource":{"primary":{"URL":"https:\/\/bmcbioinformatics.biomedcentral.com\/articles\/10.1186\/s12859-016-1258-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,9,29]]},"references-count":33,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2016,12]]}},"alternative-id":["1258"],"URL":"https:\/\/doi.org\/10.1186\/s12859-016-1258-4","relation":{},"ISSN":["1471-2105"],"issn-type":[{"type":"electronic","value":"1471-2105"}],"subject":[],"published":{"date-parts":[[2016,9,29]]},"assertion":[{"value":"28 January 2016","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 September 2016","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 September 2016","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"400"}}