{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,27]],"date-time":"2026-03-27T05:31:44Z","timestamp":1774589504194,"version":"3.50.1"},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"1","funder":[{"DOI":"10.13039\/501100006769","name":"Russian Science Foundation","doi-asserted-by":"publisher","award":["14-50-00150"],"award-info":[{"award-number":["14-50-00150"]}],"id":[{"id":"10.13039\/501100006769","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100006769","name":"Russian Science Foundation","doi-asserted-by":"publisher","award":["14-50-00150"],"award-info":[{"award-number":["14-50-00150"]}],"id":[{"id":"10.13039\/501100006769","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100006769","name":"Russian Science Foundation","doi-asserted-by":"publisher","award":["14-50-00150"],"award-info":[{"award-number":["14-50-00150"]}],"id":[{"id":"10.13039\/501100006769","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["BMC Bioinformatics"],"published-print":{"date-parts":[[2017,12]]},"DOI":"10.1186\/s12859-017-1944-x","type":"journal-article","created":{"date-parts":[[2017,12,6]],"date-time":"2017-12-06T11:59:04Z","timestamp":1512561544000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":11,"title":["Chromosome structures: reduction of certain problems with unequal gene content and gene paralogs to integer linear programming"],"prefix":"10.1186","volume":"18","author":[{"given":"Vassily","family":"Lyubetsky","sequence":"first","affiliation":[]},{"given":"Roman","family":"Gershgorin","sequence":"additional","affiliation":[]},{"given":"Konstantin","family":"Gorbunov","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,12,6]]},"reference":[{"key":"1944_CR1","doi-asserted-by":"crossref","unstructured":"Hannenhalli S, Pevzner P. Transforming men into mice (polynomial algorithm for genomic distance problem). In 36th Annual IEEE Symposium on Foundations of Computer Science. Proc FOCS. 1995:581\u201392.","DOI":"10.1109\/SFCS.1995.492588"},{"issue":"2","key":"1944_CR2","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1007\/PL00006542","volume":"49","author":"M Blanchette","year":"1999","unstructured":"Blanchette M, Kunisawa T, Sankoff D. Gene order breakpoint evidence in animal mitochondrial phylogeny. J Mol Evol. 1999;49(2):193\u2013203.","journal-title":"J Mol Evol"},{"key":"1944_CR3","doi-asserted-by":"crossref","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. Algorithms Bioinform, LNCS. 2006;4175:163\u201373.","journal-title":"Algorithms Bioinform, LNCS"},{"issue":"9","key":"1944_CR4","doi-asserted-by":"crossref","first-page":"1167","DOI":"10.1089\/cmb.2011.0118","volume":"18","author":"MDV Braga","year":"2011","unstructured":"Braga MDV, Willing E, Stoye J. Double cut and join with insertions and deletions. J Comput Biol. 2011;18(9):1167\u201384.","journal-title":"J Comput Biol"},{"key":"1944_CR5","first-page":"280","volume-title":"Proc. of RECOMB 2014, LNBI","author":"M Shao","year":"2014","unstructured":"Shao M, Lin Y, Moret B. An exact algorithm to compute the DCJ distance for genomes with duplicate genes. In: Proc. of RECOMB 2014, LNBI, vol. 8394. Heidelberg: Springer Verlag; 2014. p. 280\u201392."},{"issue":"3","key":"1944_CR6","doi-asserted-by":"publisher","first-page":"327","DOI":"10.7868\/S0026898415030076","volume":"49","author":"KY Gorbunov","year":"2015","unstructured":"Gorbunov KY, Gershgorin RA, Lyubetsky VA. Rearrangement and inference of chromosome structures. Mol Biol (Moscow). 2015;49(3):327\u201338. https:\/\/doi.org\/10.7868\/S0026898415030076 .","journal-title":"Mol Biol (Moscow)"},{"key":"1944_CR7","doi-asserted-by":"crossref","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:3340\u20136.","journal-title":"Bioinformatics"},{"issue":"3","key":"1944_CR8","first-page":"1","volume":"12","author":"MDV Braga","year":"2015","unstructured":"Braga MDV, Stoye J. Sorting linear genomes with rearrangements and Indels. IEEE\/ACM Trans Comput Biol Bioinform. 2015;12(3):1\u201313.","journal-title":"IEEE\/ACM Trans Comput Biol Bioinform"},{"issue":"4","key":"1944_CR9","doi-asserted-by":"crossref","first-page":"1165","DOI":"10.1007\/s10878-015-9940-4","volume":"32","author":"Z Yin","year":"2016","unstructured":"Yin Z, Tang J, Schaeffer SW, Bader DA. Exemplar or matching: modeling DCJ problems with unequal content genome data. J Comb Optim. 2016;32(4):1165\u201381.","journal-title":"J Comb Optim"},{"key":"1944_CR10","doi-asserted-by":"publisher","unstructured":"Chauve C, El-Mabrouk N, Tannier E. (eds.) Models and Algorithms for Genome Evolution. Computational Biology, Springer; 2013;19. doi: 10.1007\/978-1-4471-5298-9 .","DOI":"10.1007\/978-1-4471-5298-9"},{"key":"1944_CR11","doi-asserted-by":"crossref","first-page":"1311","DOI":"10.1089\/cmb.2009.0092","volume":"16","author":"S Yancopoulos","year":"2009","unstructured":"Yancopoulos S, Friedberg R. DCJ path formulation for genome transformations which include insertions, deletions, and duplications. J Comput Biol. 2009;16:1311\u201338.","journal-title":"J Comput Biol"},{"key":"1944_CR12","doi-asserted-by":"crossref","first-page":"6","DOI":"10.1186\/1748-7188-8-6","volume":"8","author":"PEC Compeau","year":"2013","unstructured":"Compeau PEC. DCJ-indel sorting revisited. Algorithms Mol Biol. 2013;8:6.","journal-title":"Algorithms Mol Biol"},{"issue":"3","key":"1944_CR13","doi-asserted-by":"crossref","first-page":"150","DOI":"10.1089\/cmb.2015.0160","volume":"23","author":"P Avdeyev","year":"2016","unstructured":"Avdeyev P, Jiang S, Aganezov S, Hu F, Alekseyev MA. Reconstruction of ancestral genomes in presence of gene gain and loss. J Comput Biol. 2016;23(3):150\u201364.","journal-title":"J Comput Biol"},{"key":"1944_CR14","doi-asserted-by":"crossref","first-page":"i329","DOI":"10.1093\/bioinformatics\/btv229","volume":"31","author":"M Shao","year":"2015","unstructured":"Shao M, Moret B. Comparing genomes with rearrangements and segmental duplications. Bioinformatics. 2015;31:i329\u201338.","journal-title":"Bioinformatics"},{"key":"1944_CR15","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1186\/s13015-015-0041-9","volume":"10","author":"FV Martinez","year":"2015","unstructured":"Martinez FV, Feij\u00e3o P, Braga MDV, Stoye J. On the family-free DCJ distance and similarity. Algorithms Mol Biol. 2015;10:13. https:\/\/doi.org\/10.1186\/s13015-015-0041-9 .","journal-title":"Algorithms Mol Biol"},{"issue":"1","key":"1944_CR16","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1134\/S0032946017010057","volume":"53","author":"KY Gorbunov","year":"2017","unstructured":"Gorbunov KY, Lyubetsky VA. Linear algorithm of the minimal reconstruction of structures. Probl Inf Transm. 2017;53(1):55\u201372.","journal-title":"Probl Inf Transm"},{"key":"1944_CR17","doi-asserted-by":"publisher","first-page":"40","DOI":"10.1186\/s12859-016-0878-z","volume":"17","author":"VA Lyubetsky","year":"2016","unstructured":"Lyubetsky VA, Gershgorin RA, Seliverstov AV, Gorbunov KY. Algorithms for reconstruction of chromosomal structures. BMC Bioinform. 2016;17:40. https:\/\/doi.org\/10.1186\/s12859-016-0878-z .","journal-title":"BMC Bioinform"},{"key":"1944_CR18","doi-asserted-by":"crossref","unstructured":"Klotz Ed, Newman Alexandra M. Practical guidelines for solving difficult linear programs. Surv Oper Res Manag Sci 2013; 18(1\u20132):1\u201317.","DOI":"10.1016\/j.sorms.2012.11.001"},{"issue":"1\u20132","key":"1944_CR19","first-page":"18","volume":"18","author":"K Ed","year":"2013","unstructured":"Ed K, Newman Alexandra M. Practical guidelines for solving difficult mixed integer linear programs. Surv Oper Res Manag Sci. 2013;18(1\u20132):18\u201332.","journal-title":"Surv Oper Res Manag Sci"},{"key":"1944_CR20","first-page":"195","volume":"28","author":"AM Vershik","year":"1983","unstructured":"Vershik AM, Sporyshev PV. An estimate of the average number of steps in the simplex method, and problems in asymptotic integral geometry. Sov Math Dokl. 1983;28:195\u20139.","journal-title":"Sov Math Dokl"},{"issue":"3","key":"1944_CR21","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1007\/BF02591902","volume":"27","author":"S Smale","year":"1983","unstructured":"Smale S. On the average number of steps of the simplex method of linear programming. Math Program. 1983;27(3):241\u201362. https:\/\/doi.org\/10.1007\/BF02591902 .","journal-title":"Math Program"},{"key":"1944_CR22","series-title":"CSR 2017. Lecture notes in computer science","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1007\/978-3-319-58747-9_25","volume-title":"Computer science \u2013 theory and applications","author":"A Seliverstov","year":"2017","unstructured":"Seliverstov A. On probabilistic algorithm for solving almost all instances of the set partition problem. In: Weil P, editor. Computer science \u2013 theory and applications, CSR 2017. Lecture notes in computer science, vol. 10304. Cham: Springer; 2017. p. 285\u201393. https:\/\/doi.org\/10.1007\/978-3-319-58747-9_25 ."},{"issue":"6","key":"1944_CR23","doi-asserted-by":"crossref","first-page":"653","DOI":"10.1134\/S1064226917060092","volume":"62","author":"KY Gorbunov","year":"2017","unstructured":"Gorbunov KY, Lyubetsky VA. A linear algorithm for the shortest transformation of graphs with different operation costs. J Commun Technol Electron. 2017;62(6):653\u201362.","journal-title":"J Commun Technol Electron"},{"key":"1944_CR24","first-page":"162","volume-title":"CEUR workshop proceedings (CEUR-WS.Org), selected papers of the first international scientific conference \"convergent cognitive information technologies (convergent 2016)\", Moscow, Russia","author":"KY Gorbunov","year":"2016","unstructured":"Gorbunov KY, Lyubetsky VA. A modified algorithm for transformation of chromosomal structures: a condition of absolute exactness. In: CEUR workshop proceedings (CEUR-WS.Org), selected papers of the first international scientific conference \"convergent cognitive information technologies (convergent 2016)\", Moscow, Russia, vol. 1763; 2016. p. 162\u201372. in Russian."},{"issue":"2\u20133","key":"1944_CR25","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1016\/j.tcs.2008.01.013","volume":"395","author":"MA Alekseyev","year":"2008","unstructured":"Alekseyev MA, Pevzner PA. Multi-break rearrangements and chromosomal evolution. Theor Comput Sci. 2008;395(2\u20133):193\u2013202.","journal-title":"Theor Comput Sci"},{"key":"1944_CR26","doi-asserted-by":"publisher","first-page":"314","DOI":"10.1016\/j.ympev.2013.10.007","volume":"70","author":"TR Bachvaroff","year":"2014","unstructured":"Bachvaroff TR, Gornik SG, Concepcion GT, Waller RF, Mendez GS, Lippmeier JC, Delwiche CF. Dinoflagellate phylogeny revisited: using ribosomal proteins to resolve deep branching dinoflagellate clades. Mol Phylogenet Evol. 2014;70:314\u201322. https:\/\/doi.org\/10.1016\/j.ympev.2013.10.007 .","journal-title":"Mol Phylogenet Evol"},{"key":"1944_CR27","unstructured":"Lyubetsky VA, Gershgorin RA, Rubanov LI, Seliverstov AV, Zverkov OA. Evolution and systematics of plastids of rhodophytic branch. In: Proceedings of the Moscow conference on computational molecular biology (MCCMB'17), Moscow, Russia; 2017, July 27\u201330, 4 pp."},{"issue":"11","key":"1944_CR28","doi-asserted-by":"publisher","first-page":"975","DOI":"10.1089\/cmb.2015.0073","volume":"22","author":"L Chin Lung","year":"2015","unstructured":"Chin Lung L. An efficient algorithm for the Contig ordering problem under algebraic rearrangement distance. J Comput Biol. 2015;22(11):975\u201387. https:\/\/doi.org\/10.1089\/cmb.2015.0073 .","journal-title":"J Comput Biol"},{"key":"1944_CR29","unstructured":"Utility for generation of ILP problems represented in IBM lp format. http:\/\/lab6.iitp.ru\/en\/ilp_generatorggl\/3 . Accessed 24 July 2017."}],"container-title":["BMC Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1186\/s12859-017-1944-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,28]],"date-time":"2025-06-28T07:17:28Z","timestamp":1751095048000},"score":1,"resource":{"primary":{"URL":"https:\/\/bmcbioinformatics.biomedcentral.com\/articles\/10.1186\/s12859-017-1944-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,12]]},"references-count":29,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2017,12]]}},"alternative-id":["1944"],"URL":"https:\/\/doi.org\/10.1186\/s12859-017-1944-x","relation":{},"ISSN":["1471-2105"],"issn-type":[{"value":"1471-2105","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,12]]},"article-number":"537"}}