{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,2]],"date-time":"2026-06-02T08:36:25Z","timestamp":1780389385763,"version":"3.54.1"},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2019,7,19]],"date-time":"2019-07-19T00:00:00Z","timestamp":1563494400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"},{"start":{"date-parts":[[2019,7,19]],"date-time":"2019-07-19T00:00:00Z","timestamp":1563494400000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"CNRS"},{"name":"NUMEV"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithms Mol Biol"],"published-print":{"date-parts":[[2019,12]]},"DOI":"10.1186\/s13015-019-0149-4","type":"journal-article","created":{"date-parts":[[2019,7,19]],"date-time":"2019-07-19T13:03:00Z","timestamp":1563541380000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["A general framework for genome rearrangement with biological constraints"],"prefix":"10.1186","volume":"14","author":[{"given":"Pijus","family":"Simonaitis","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Annie","family":"Chateau","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8690-1261","authenticated-orcid":false,"given":"Krister M.","family":"Swenson","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2019,7,19]]},"reference":[{"issue":"1","key":"149_CR1","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1016\/0378-1119(95)00878-0","volume":"172","author":"M Blanchette","year":"1996","unstructured":"Blanchette M, Kunisawa T, Sankoff D. Parametric genome rearrangement. Gene. 1996;172(1):11\u20137.","journal-title":"Gene"},{"issue":"19","key":"149_CR2","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1186\/1471-2105-16-S19-S3","volume":"16","author":"C Baudet","year":"2015","unstructured":"Baudet C, Dias U, Dias Z. Sorting by weighted inversions considering length and symmetry. BMC Bioinform. 2015;16(19):3.","journal-title":"BMC Bioinform"},{"key":"149_CR3","doi-asserted-by":"publisher","first-page":"1427","DOI":"10.1093\/gbe\/evw083","volume":"8","author":"P Biller","year":"2016","unstructured":"Biller P, Knibbe C, Gu\u00e9guen L, Tannier E. Breaking good: accounting for the diversity of fragile regions for estimating rearrangement distances. Genome Biol Evol. 2016;8:1427\u201339.","journal-title":"Genome Biol Evol"},{"issue":"3","key":"149_CR4","doi-asserted-by":"publisher","first-page":"814","DOI":"10.1073\/pnas.81.3.814","volume":"81","author":"JH Nadeau","year":"1984","unstructured":"Nadeau JH, Taylor BA. Lengths of chromosomal segments conserved since divergence of man and mouse. Proc Natl Acad Sci. 1984;81(3):814\u20138.","journal-title":"Proc Natl Acad Sci"},{"key":"149_CR5","doi-asserted-by":"publisher","first-page":"160","DOI":"10.1007\/978-3-642-86659-3","volume-title":"Evolution by gene duplication","author":"S Ohno","year":"1970","unstructured":"Ohno S. Evolution by gene duplication. Berlin: Springer; 1970. p. 160."},{"issue":"1","key":"149_CR6","doi-asserted-by":"publisher","first-page":"16","DOI":"10.1186\/s13015-017-0107-y","volume":"12","author":"G Fertin","year":"2017","unstructured":"Fertin G, Jean G, Tannier E. Algorithms for computing the double cut and join distance on both gene order and intergenic sizes. Algorithms Mol Biol. 2017;12(1):16.","journal-title":"Algorithms Mol Biol"},{"issue":"14","key":"149_CR7","doi-asserted-by":"publisher","first-page":"426","DOI":"10.1186\/s12859-016-1264-6","volume":"17","author":"L Bulteau","year":"2016","unstructured":"Bulteau L, Fertin G, Tannier E. Genome rearrangements with indels in intergenes restrict the scenario space. BMC Bioinform. 2016;17(14):426.","journal-title":"BMC Bioinform"},{"issue":"5950","key":"149_CR8","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1126\/science.1181369","volume":"326","author":"E Lieberman-Aiden","year":"2009","unstructured":"Lieberman-Aiden E, Van Berkum NL, Williams L, Imakaev M, Ragoczy T, Telling A, Amit I, Lajoie BR, Sabo PJ, Dorschner MO, et al. Comprehensive mapping of long-range interactions reveals folding principles of the human genome. Science. 2009;326(5950):289\u201393.","journal-title":"Science"},{"issue":"1","key":"149_CR9","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1186\/1471-2164-12-303","volume":"12","author":"A Veron","year":"2011","unstructured":"Veron A, Lemaitre C, Gautier C, Lacroix V, Sagot M-F. Close 3D proximity of evolutionary breakpoints argues for the notion of spatial synteny. BMC Genomics. 2011;12(1):303.","journal-title":"BMC Genomics"},{"key":"149_CR10","doi-asserted-by":"crossref","unstructured":"Pulicani S, Simonaitis P, Rivals E, Swenson KM. Rearrangement scenarios guided by chromatin structure. In: RECOMB international workshop on comparative genomics. Berlin: Springer; 2017; p. 141\u201355","DOI":"10.1007\/978-3-319-67979-2_8"},{"issue":"1","key":"149_CR11","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1186\/s13015-016-0065-9","volume":"11","author":"KM Swenson","year":"2016","unstructured":"Swenson KM, Simonaitis P, Blanchette M. Models and algorithms for genome rearrangement with positional constraints. Algorithms Mol Biol. 2016;11(1):13.","journal-title":"Algorithms Mol Biol"},{"issue":"1","key":"149_CR12","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1186\/s13015-018-0127-2","volume":"13","author":"P Simonaitis","year":"2018","unstructured":"Simonaitis P, Swenson KM. Finding local genome rearrangements. Algorithms Mol Biol. 2018;13(1):9.","journal-title":"Algorithms Mol Biol"},{"issue":"16","key":"149_CR13","doi-asserted-by":"publisher","first-page":"3340","DOI":"10.1093\/bioinformatics\/bti535","volume":"21","author":"S Yancopoulos","year":"2005","unstructured":"Yancopoulos S, Attie O, Friedberg R. Efficient sorting of genomic permutations by translocation, inversion and block interchange. Bioinformatics. 2005;21(16):3340\u20136.","journal-title":"Bioinformatics"},{"key":"149_CR14","first-page":"163","volume-title":"Lecture Notes in Computer Science","author":"Anne Bergeron","year":"2006","unstructured":"Bergeron A, Mixtacki J, Stoye J. A unifying view of genome rearrangements. In: International workshop on algorithms in bioinformatics. Berlin: Springer; 2006. p. 163\u201373."},{"key":"149_CR15","doi-asserted-by":"publisher","first-page":"13","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 Bioinform. 2012;13:13.","journal-title":"BMC Bioinform"},{"issue":"2","key":"149_CR16","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1137\/16M1087175","volume":"60","author":"BK Fosdick","year":"2018","unstructured":"Fosdick BK, Larremore DB, Nishimura J, Ugander J. Configuring random graph models with fixed degree sequences. SIAM Rev. 2018;60(2):315\u201355.","journal-title":"SIAM Rev"},{"issue":"2","key":"149_CR17","doi-asserted-by":"publisher","first-page":"272","DOI":"10.1137\/S0097539793250627","volume":"25","author":"V Bafna","year":"1996","unstructured":"Bafna V, Pevzner PA. Genome rearrangements and sorting by reversals. SIAM J Comput. 1996;25(2):272\u201389.","journal-title":"SIAM J Comput"},{"key":"149_CR18","first-page":"1","volume-title":"Algorithms and applications","author":"A Amir","year":"2010","unstructured":"Amir A, Levy A. String rearrangement metrics: a survey. Algorithms and applications. Berlin: Springer; 2010. p. 1\u201333."},{"issue":"1","key":"149_CR19","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1109\/TIT.2011.2171532","volume":"58","author":"F Farnoud","year":"2012","unstructured":"Farnoud F, Milenkovic O. Sorting of permutations by cost-constrained transpositions. IEEE Trans Inf Theory. 2012;58(1):3\u201323.","journal-title":"IEEE Trans Inf Theory"},{"issue":"4","key":"149_CR20","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1002\/net.3230240402","volume":"24","author":"D Bienstock","year":"1994","unstructured":"Bienstock D, G\u00fcnl\u00fck O. A degree sequence problem related to network design. Networks. 1994;24(4):195\u2013205.","journal-title":"Networks"},{"key":"149_CR21","doi-asserted-by":"crossref","unstructured":"Feder T, Guetz A, Mihail M, Saberi A. A local switch markov chain on given degree graphs with application in connectivity of peer-to-peer networks. In: FOCS\u201906. 47th annual IEEE symposium on foundations of computer science. 2006. p. 69\u201376.","DOI":"10.1109\/FOCS.2006.5"},{"key":"149_CR22","doi-asserted-by":"crossref","unstructured":"Caprara A. Sorting by reversals is difficult. In: Proceedings of the first annual international conference on computational molecular biology. New York: ACM; 1997. p. 75\u201383.","DOI":"10.1145\/267521.267531"},{"key":"149_CR23","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-72031-7_27","volume-title":"The solution space of sorting by reversals","author":"MDV Braga","year":"2007","unstructured":"Braga MDV, Sagot M-F, Scornavacca C, Tannier E. Bioinformatics research and applications: proceedings from ISBRA. The solution space of sorting by reversals. Berlin: Springer; 2007."},{"issue":"2","key":"149_CR24","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1137\/0211019","volume":"11","author":"JR Bitner","year":"1982","unstructured":"Bitner JR. An asymptotically optimal algorithm for the dutch national flag problem. SIAM J Comput. 1982;11(2):243\u201362.","journal-title":"SIAM J Comput"},{"key":"149_CR25","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 Bioinform. 2013;14:9.","journal-title":"BMC Bioinform"},{"key":"149_CR26","doi-asserted-by":"crossref","unstructured":"Birmel\u00e9 E, Ferreira R, Grossi R, Marino A, Pisanti N, Rizzi R, Sacomoto G. Optimal listing of cycles and st-paths in undirected graphs. In: Proceedings of the twenty-fourth annual ACM-SIAM symposium on discrete algorithms. Society for Industrial and Applied Mathematics; 2013. p. 1884\u201396.","DOI":"10.1137\/1.9781611973105.134"},{"key":"149_CR27","doi-asserted-by":"publisher","first-page":"512","DOI":"10.1007\/3-540-44676-1_43","volume-title":"Algorithms \u2014 ESA 2001","author":"Alberto Caprara","year":"2001","unstructured":"Caprara A, Panconesi A, Rizzi R. Packing cycles and cuts in undirected graphs. In: European symposium on algorithms. Berlin: Springer; 2001. p. 512\u201323."},{"key":"149_CR28","doi-asserted-by":"crossref","unstructured":"Zeng X, Nesbitt MJ, Pei J, Wang K, Vergara IA, Chen N. Orthocluster: a new tool for mining synteny blocks and applications in comparative genomics. In: Proceedings of the 11th international conference on extending database technology: advances in database technology. New York: ACM; 2008. p. 656\u201367.","DOI":"10.1145\/1353343.1353423"},{"issue":"4","key":"149_CR29","doi-asserted-by":"publisher","first-page":"356","DOI":"10.1186\/s12864-017-3733-3","volume":"18","author":"N Alexeev","year":"2017","unstructured":"Alexeev N, Alekseyev MA. Estimation of the true evolutionary distance under the fragile breakage model. BMC Genomics. 2017;18(4):356.","journal-title":"BMC Genomics"}],"container-title":["Algorithms for Molecular Biology"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1186\/s13015-019-0149-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1186\/s13015-019-0149-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1186\/s13015-019-0149-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,7,17]],"date-time":"2020-07-17T23:08:34Z","timestamp":1595027314000},"score":1,"resource":{"primary":{"URL":"https:\/\/almob.biomedcentral.com\/articles\/10.1186\/s13015-019-0149-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,7,19]]},"references-count":29,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2019,12]]}},"alternative-id":["149"],"URL":"https:\/\/doi.org\/10.1186\/s13015-019-0149-4","relation":{},"ISSN":["1748-7188"],"issn-type":[{"value":"1748-7188","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,7,19]]},"assertion":[{"value":"29 April 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 June 2019","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 July 2019","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Not applicable.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethics approval and consent to participate"}},{"value":"Not applicable.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent for publication"}},{"value":"The authors declare that they have no competing interests.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"15"}}