{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T13:28:33Z","timestamp":1740144513222,"version":"3.37.3"},"reference-count":19,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2019,11,5]],"date-time":"2019-11-05T00:00:00Z","timestamp":1572912000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"},{"start":{"date-parts":[[2019,11,5]],"date-time":"2019-11-05T00:00:00Z","timestamp":1572912000000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100003593","name":"Conselho Nacional de Desenvolvimento Cient\u00edfico e Tecnol\u00f3gico","doi-asserted-by":"publisher","award":["400487\/2016-0","425340\/2016-3"],"award-info":[{"award-number":["400487\/2016-0","425340\/2016-3"]}],"id":[{"id":"10.13039\/501100003593","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003593","name":"Conselho Nacional de Desenvolvimento Cient\u00edfico e Tecnol\u00f3gico","doi-asserted-by":"publisher","award":["140466\/2018-5"],"award-info":[{"award-number":["140466\/2018-5"]}],"id":[{"id":"10.13039\/501100003593","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001807","name":"Funda\u00e7\u00e3o de Amparo \u00e0 Pesquisa do Estado de S\u00e3o Paulo","doi-asserted-by":"crossref","award":["2013\/08293-7","2015\/11937-9"],"award-info":[{"award-number":["2013\/08293-7","2015\/11937-9"]}],"id":[{"id":"10.13039\/501100001807","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001807","name":"Funda\u00e7\u00e3o de Amparo \u00e0 Pesquisa do Estado de S\u00e3o Paulo","doi-asserted-by":"crossref","award":["2017\/12646-3","2017\/16246-0"],"award-info":[{"award-number":["2017\/12646-3","2017\/16246-0"]}],"id":[{"id":"10.13039\/501100001807","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100002322","name":"Coordena\u00e7\u00e3o de Aperfei\u00e7oamento de Pessoal de N\u00edvel Superior","doi-asserted-by":"crossref","award":["CAPES\/COFECUB 831\/15"],"award-info":[{"award-number":["CAPES\/COFECUB 831\/15"]}],"id":[{"id":"10.13039\/501100002322","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithms Mol Biol"],"published-print":{"date-parts":[[2019,12]]},"abstract":"<jats:title>Abstract<\/jats:title>\n              <jats:sec>\n                <jats:title>Background<\/jats:title>\n                <jats:p>The evolutionary distance between two genomes can be estimated by computing a minimum length sequence of operations, called <jats:italic>genome rearrangements<\/jats:italic>, that transform one genome into another. Usually, a genome is modeled as an ordered sequence of genes, and most of the studies in the genome rearrangement literature consist in shaping biological scenarios into mathematical models. For instance, allowing different genome rearrangements operations at the same time, adding constraints to these rearrangements (e.g., each rearrangement can affect at most a given number of genes), considering that a rearrangement implies a cost depending on its length rather than a unit cost, etc. Most of the works, however, have overlooked some important features inside genomes, such as the presence of sequences of nucleotides between genes, called <jats:italic>intergenic regions<\/jats:italic>.<\/jats:p>\n              <\/jats:sec>\n              <jats:sec>\n                <jats:title>Results and conclusions<\/jats:title>\n                <jats:p>In this work, we investigate the problem of computing the distance between two genomes, taking into account both gene order and intergenic sizes. The genome rearrangement operations we consider here are constrained types of reversals and transpositions, called <jats:italic>super short reversals<\/jats:italic> (SSRs) and <jats:italic>super short transpositions<\/jats:italic> (SSTs), which affect up to two (consecutive) genes. We denote by <jats:italic>super short operations<\/jats:italic> (SSOs) any SSR or SST. We show 3-approximation algorithms when the orientation of the genes is not considered when we allow SSRs, SSTs, or SSOs, and 5-approximation algorithms when considering the orientation for either SSRs or SSOs. We also show that these algorithms improve their approximation factors when the input permutation has a higher number of inversions, where the approximation factor decreases from 3 to either 2 or 1.5, and from 5 to either 3 or 2.<\/jats:p>\n              <\/jats:sec>","DOI":"10.1186\/s13015-019-0156-5","type":"journal-article","created":{"date-parts":[[2019,11,5]],"date-time":"2019-11-05T16:03:18Z","timestamp":1572969798000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["Super short operations on both gene order and intergenic sizes"],"prefix":"10.1186","volume":"14","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0568-1859","authenticated-orcid":false,"given":"Andre R.","family":"Oliveira","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1534-2682","authenticated-orcid":false,"given":"G\u00e9raldine","family":"Jean","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8251-2012","authenticated-orcid":false,"given":"Guillaume","family":"Fertin","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4763-3046","authenticated-orcid":false,"given":"Ulisses","family":"Dias","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3333-6822","authenticated-orcid":false,"given":"Zanoni","family":"Dias","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2019,11,5]]},"reference":[{"issue":"2","key":"156_CR1","doi-asserted-by":"publisher","first-page":"224","DOI":"10.1137\/S089548019528280X","volume":"11","author":"V Bafna","year":"1998","unstructured":"Bafna V, Pevzner PA. Sorting by transpositions. SIAM J Discrete Math. 1998;11(2):224\u201340. \n                    https:\/\/doi.org\/10.1137\/S089548019528280X\n                    \n                  .","journal-title":"SIAM J Discrete Math"},{"key":"156_CR2","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1007\/BF01188586","volume":"13","author":"JD Kececioglu","year":"1995","unstructured":"Kececioglu JD, Sankoff D. Exact and approximation algorithms for sorting by reversals, with application to genome rearrangement. Algorithmica. 1995;13:180\u2013210. \n                    https:\/\/doi.org\/10.1007\/BF01188586\n                    \n                  .","journal-title":"Algorithmica"},{"issue":"16","key":"156_CR3","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. \n                    https:\/\/doi.org\/10.1093\/bioinformatics\/bti535\n                    \n                  .","journal-title":"Bioinformatics"},{"key":"156_CR4","doi-asserted-by":"publisher","unstructured":"Hannenhalli S, Pevzner PA. Transforming men into mice (polynomial algorithm for genomic distance problem). In: Proceedings of the 36th annual symposium on foundations of computer science (FOCS\u20191995). Washington, DC: IEEE Computer Society Press; 1995. \n                    https:\/\/doi.org\/10.1109\/SFCS.1995.492588\n                    \n                  . p. 581\u201392.","DOI":"10.1109\/SFCS.1995.492588"},{"issue":"4","key":"156_CR5","doi-asserted-by":"publisher","first-page":"369","DOI":"10.1109\/TCBB.2006.44","volume":"3","author":"I Elias","year":"2006","unstructured":"Elias I, Hartman T. A 1.375-approximation algorithm for sorting by transpositions. IEEE\/ACM Trans Comput Biol Bioinform. 2006;3(4):369\u201379. \n                    https:\/\/doi.org\/10.1109\/TCBB.2006.44\n                    \n                  .","journal-title":"IEEE\/ACM Trans Comput Biol Bioinform"},{"key":"156_CR6","volume-title":"Computational molecular biology","author":"G Fertin","year":"2009","unstructured":"Fertin G, Labarre A, Rusu I, Tannier E, Vialette S. Combinatorics of genome rearrangements. Computational molecular biology. London: The MIT Press; 2009."},{"issue":"1\u20133","key":"156_CR7","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1016\/S0166-218X(96)00069-8","volume":"71","author":"T Chen","year":"1996","unstructured":"Chen T, Skiena SS. Sorting with fixed-length reversals. Discrete Appl Math. 1996;71(1\u20133):269\u201395. \n                    https:\/\/doi.org\/10.1016\/S0166-218X(96)00069-8\n                    \n                  .","journal-title":"Discrete Appl Math"},{"key":"156_CR8","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1186\/s13015-015-0040-x","volume":"10","author":"GR Galv\u00e3o","year":"2015","unstructured":"Galv\u00e3o GR, Lee O, Dias Z. Sorting signed permutations by short operations. Algor Mol Biol. 2015;10:12. \n                    https:\/\/doi.org\/10.1186\/s13015-015-0040-x\n                    \n                  .","journal-title":"Algor Mol Biol."},{"issue":"1","key":"156_CR9","doi-asserted-by":"publisher","first-page":"190","DOI":"10.1093\/bioinformatics\/btg1025","volume":"19","author":"J-F Lefebvre","year":"2003","unstructured":"Lefebvre J-F, El-Mabrouk N, Tillier ERM, Sankoff D. Detection and validation of single gene inversions. Bioinformatics. 2003;19(1):190\u20136. \n                    https:\/\/doi.org\/10.1093\/bioinformatics\/btg1025\n                    \n                  .","journal-title":"Bioinformatics"},{"issue":"1","key":"156_CR10","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1007\/s00239-001-0087-9","volume":"55","author":"DA Dalevi","year":"2002","unstructured":"Dalevi DA, Eriksen N, Eriksson K, Andersson SGE. Measuring genome divergence in bacteria: a case study using Chlamydian Data. J Mol Evol. 2002;55(1):24\u201336. \n                    https:\/\/doi.org\/10.1007\/s00239-001-0087-9\n                    \n                  .","journal-title":"J Mol Evol"},{"issue":"26","key":"156_CR11","doi-asserted-by":"publisher","first-page":"14433","DOI":"10.1073\/pnas.240462997","volume":"97","author":"C Seoighe","year":"2000","unstructured":"Seoighe C, Federspiel N, Jones T, Hansen N, Bivolarovic V, Surzycki R, Tamse R, Komp C, Huizar L, Davis RW, Scherer S, Tait E, Shaw DJ, Harris D, Murphy L, Oliver K, Taylor K, Rajandream M-A, Barrell BG, Wolfe KH. Prevalence of small inversions in yeast gene order evolution. Proc Natl Acad Sci. 2000;97(26):14433\u20137. \n                    https:\/\/doi.org\/10.1073\/pnas.240462997\n                    \n                  .","journal-title":"Proc Natl Acad Sci"},{"key":"156_CR12","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1007\/978-94-011-4309-7_6","volume-title":"Comparative genomics: empirical and analytical approaches to gene order dynamics, map alignment and the evolution of gene families","author":"A McLysaght","year":"2000","unstructured":"McLysaght A, Seoighe C, Wolfe KH. High frequency of inversions during eukaryote gene order evolution. In: Sankoff D, Nadeau JH, editors. Comparative genomics: empirical and analytical approaches to gene order dynamics, map alignment and the evolution of gene families. New York: Springer; 2000. p. 47\u201358. \n                    https:\/\/doi.org\/10.1007\/978-94-011-4309-7_6\n                    \n                  ."},{"issue":"5","key":"156_CR13","doi-asserted-by":"publisher","first-page":"1427","DOI":"10.1093\/gbe\/evw083","volume":"8","author":"P Biller","year":"2016","unstructured":"Biller P, Gu\u00e9guen L, Knibbe C, Tannier E. Breaking good: accounting for fragility of genomic regions in rearrangement distance estimation. Genome Biol Evol. 2016;8(5):1427\u201339. \n                    https:\/\/doi.org\/10.1093\/gbe\/evw083\n                    \n                  .","journal-title":"Genome Biol Evol"},{"key":"156_CR14","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1007\/978-3-319-40189-8_4","volume-title":"Pursuit of the universal lecture notes in computer science","author":"P Biller","year":"2016","unstructured":"Biller P, Knibbe C, Beslon G, Tannier E. Comparative genomics on artificial life. In: Beckmann A, Bienvenu L, Jonoska N, editors. Pursuit of the universal lecture notes in computer science. Cham: Springer International Publishing; 2016. p. 35\u201344. \n                    https:\/\/doi.org\/10.1007\/978-3-319-40189-8_4\n                    \n                  ."},{"key":"156_CR15","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. Algor Mol Biol. 2017;12:16. \n                    https:\/\/doi.org\/10.1186\/s13015-017-0107-y\n                    \n                  .","journal-title":"Algor Mol Biol."},{"issue":"S14","key":"156_CR16","doi-asserted-by":"publisher","first-page":"225","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(S14):225\u201331. \n                    https:\/\/doi.org\/10.1186\/s12859-016-1264-6\n                    \n                  .","journal-title":"BMC Bioinform"},{"key":"156_CR17","volume-title":"The art of computer programming, Volume 3: Sorting and searching","author":"DE Knuth","year":"1998","unstructured":"Knuth DE. The art of computer programming, Volume 3: Sorting and searching. Reading: Addison-Wesley Publishing Company; 1998."},{"issue":"4","key":"156_CR18","doi-asserted-by":"publisher","first-page":"429","DOI":"10.1002\/net.3230120407","volume":"12","author":"D Rotem","year":"1982","unstructured":"Rotem D, Urrutia J. Circular permutation graphs. Networks. 1982;12(4):429\u201337. \n                    https:\/\/doi.org\/10.1002\/net.3230120407\n                    \n                  .","journal-title":"Networks"},{"issue":"2","key":"156_CR19","first-page":"65","volume":"12","author":"M Bousquet-Melou","year":"2010","unstructured":"Bousquet-Melou M. The expected number of inversions after n adjacent transpositions. Discrete Math Theor Comput Sci. 2010;12(2):65\u201388.","journal-title":"Discrete Math Theor Comput Sci"}],"container-title":["Algorithms for Molecular Biology"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1186\/s13015-019-0156-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1186\/s13015-019-0156-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1186\/s13015-019-0156-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,4]],"date-time":"2020-11-04T00:07:34Z","timestamp":1604448454000},"score":1,"resource":{"primary":{"URL":"https:\/\/almob.biomedcentral.com\/articles\/10.1186\/s13015-019-0156-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,11,5]]},"references-count":19,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2019,12]]}},"alternative-id":["156"],"URL":"https:\/\/doi.org\/10.1186\/s13015-019-0156-5","relation":{},"ISSN":["1748-7188"],"issn-type":[{"type":"electronic","value":"1748-7188"}],"subject":[],"published":{"date-parts":[[2019,11,5]]},"assertion":[{"value":"16 February 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 October 2019","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 November 2019","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"The authors declare that they have no competing interests.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"21"}}