{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,2]],"date-time":"2026-06-02T08:34:28Z","timestamp":1780389268208,"version":"3.54.1"},"reference-count":15,"publisher":"Springer Science and Business Media LLC","issue":"1","content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithms Mol Biol"],"published-print":{"date-parts":[[2017,12]]},"DOI":"10.1186\/s13015-017-0095-y","type":"journal-article","created":{"date-parts":[[2017,3,9]],"date-time":"2017-03-09T14:18:17Z","timestamp":1489069097000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":12,"title":["Approximating the DCJ distance of balanced genomes in linear time"],"prefix":"10.1186","volume":"12","author":[{"given":"Diego P.","family":"Rubert","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Pedro","family":"Feij\u00e3o","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mar\u00edlia Dias Vieira","family":"Braga","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4656-7155","authenticated-orcid":false,"given":"Jens","family":"Stoye","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"F\u00e1bio Henrique Viduani","family":"Martinez","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2017,3,9]]},"reference":[{"issue":"16","key":"95_CR1","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 interchanges. Bioinformatics. 2005;21(16):3340\u20136.","journal-title":"Bioinformatics"},{"key":"95_CR2","doi-asserted-by":"crossref","unstructured":"Bergeron A, Mixtacki J, Stoye J. A unifying view of genome rearrangements. In: Proceedings of workshop on algorithms in Bioinformatics 2006. Heidelberg: LNBI; 2006. vol. 4175, p. 163\u201373","DOI":"10.1007\/11851561_16"},{"issue":"6","key":"95_CR3","doi-asserted-by":"crossref","first-page":"1384","DOI":"10.1109\/TCBB.2012.144","volume":"10","author":"L Bulteau","year":"2013","unstructured":"Bulteau L, Jiang M. Inapproximability of (1, 2)-exemplar distance. IEEE\/ACM Trans Comput Biol Bioinf. 2013;10(6):1384\u201390.","journal-title":"IEEE\/ACM Trans Comput Biol Bioinf"},{"issue":"5","key":"95_CR4","doi-asserted-by":"crossref","first-page":"425","DOI":"10.1089\/cmb.2014.0096","volume":"22","author":"M Shao","year":"2015","unstructured":"Shao M, Lin Y, Moret B. An exact algorithm to compute the double-cut-and-join distance for genomes with duplicate genes. J Comput Biol. 2015;22(5):425\u201335.","journal-title":"J Comput Biol"},{"key":"95_CR5","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1007\/978-94-011-4309-7_19","volume-title":"Comparative Genomics","author":"D Bryant","year":"2000","unstructured":"Bryant D. The complexity of calculating exemplar distances. In: Sankoff D, Nadeau JH, editors. Comparative Genomics. Dortrecht: Kluwer Academic Publishers; 2000. p. 207\u201311."},{"key":"95_CR6","doi-asserted-by":"crossref","unstructured":"Goldstein A, Kolman P, Zheng J. Minimum common string partition problem: hardness and approximations. Electron J Comb. 2005;12(R50)","DOI":"10.1007\/978-3-540-30551-4_43"},{"key":"95_CR7","first-page":"121","volume":"2005","author":"K Swenson","year":"2005","unstructured":"Swenson K, Marron M, Earnest-DeYong K, Moret BME. Approximating the true evolutionary distance between two genomes. Proc ALENEX\/ANALCO. 2005;2005:121\u20139.","journal-title":"Proc ALENEX\/ANALCO"},{"key":"95_CR8","doi-asserted-by":"crossref","unstructured":"Jiang H, Zheng C, Sankoff D, Zhu B. Scaffold filling under the breakpoint distance. In: Proceeding of RECOMB\u2014comparative genomics 2010. Lecture Notes on Bioinformatics; 2010. vol. 6398, p. 83\u201392.","DOI":"10.1007\/978-3-642-16181-0_8"},{"issue":"1","key":"95_CR9","doi-asserted-by":"crossref","first-page":"50","DOI":"10.37236\/968","volume":"14","author":"P Kolman","year":"2007","unstructured":"Kolman P, Wale\u0144 T. Reversal distance for strings with duplicates: linear time approximation using hitting set. Elec J Comb. 2007;14(1):50.","journal-title":"Elec J Comb"},{"key":"95_CR10","doi-asserted-by":"crossref","unstructured":"Rubert DP, Feij\u00e3o P, Braga MDV, Stoye J, Martinez FV. A linear time approximation algorithm for the DCJ distance for genomes with bounded number of duplicates. In: Proceedings of WABI 2016. Heidelberg: LNBI; 2016. vol. 9838, p. 293\u2013306","DOI":"10.1007\/978-3-319-43681-4_24"},{"issue":"9","key":"95_CR11","doi-asserted-by":"crossref","first-page":"1145","DOI":"10.1089\/cmb.2010.0109","volume":"17","author":"MDV Braga","year":"2010","unstructured":"Braga MDV, Stoye J. The solution space of sorting by DCJ. J Comp Biol. 2010;17(9):1145\u201365.","journal-title":"J Comp Biol"},{"issue":"8","key":"95_CR12","doi-asserted-by":"crossref","first-page":"1093","DOI":"10.1089\/cmb.2008.0061","volume":"15","author":"S Angibaud","year":"2008","unstructured":"Angibaud S, Fertin G, Rusu I, Th\u00e9venin A, Vialette S. Efficient tools for computing the number of breakpoints and the number of adjacencies between two genomes with duplicate genes. J Comp Biol. 2008;15(8):1093\u2013115.","journal-title":"J Comp Biol"},{"key":"95_CR13","first-page":"137","volume":"1997","author":"M Farach","year":"1997","unstructured":"Farach M. Optimal suffix tree construction with large alphabets. Proc IEEE\/FOCS. 1997;1997:137\u201343.","journal-title":"Proc IEEE\/FOCS"},{"key":"95_CR14","unstructured":"Meidanis J, Walter MEMT, Dias Z. Reversal distance of signed circular chromosomes. Technical report. Campinas: University of Campinas and University of Brasilia; 2000."},{"issue":"2","key":"95_CR15","doi-asserted-by":"crossref","first-page":"275","DOI":"10.1016\/j.ic.2005.09.002","volume":"204","author":"T Hartman","year":"2006","unstructured":"Hartman T, Shamir R. A simpler and faster 1.5-approximation algorithm for sorting by transpositions. Inf Comput. 2006;204(2):275\u201390.","journal-title":"Inf Comput"}],"container-title":["Algorithms for Molecular Biology"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1186\/s13015-017-0095-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,10,3]],"date-time":"2020-10-03T16:56:20Z","timestamp":1601744180000},"score":1,"resource":{"primary":{"URL":"http:\/\/almob.biomedcentral.com\/articles\/10.1186\/s13015-017-0095-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,3,9]]},"references-count":15,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2017,12]]}},"alternative-id":["95"],"URL":"https:\/\/doi.org\/10.1186\/s13015-017-0095-y","relation":{},"ISSN":["1748-7188"],"issn-type":[{"value":"1748-7188","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,3,9]]},"article-number":"3"}}