{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,1]],"date-time":"2022-04-01T23:39:36Z","timestamp":1648856376171},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"S6","license":[{"start":{"date-parts":[[2018,5,1]],"date-time":"2018-05-01T00:00:00Z","timestamp":1525132800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["BMC Bioinformatics"],"published-print":{"date-parts":[[2018,5]]},"DOI":"10.1186\/s12859-018-2130-5","type":"journal-article","created":{"date-parts":[[2018,5,8]],"date-time":"2018-05-08T09:21:25Z","timestamp":1525771285000},"update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Computing the family-free DCJ similarity"],"prefix":"10.1186","volume":"19","author":[{"given":"Diego P.","family":"Rubert","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Edna A.","family":"Hoshino","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mar\u00edlia D. V.","family":"Braga","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jens","family":"Stoye","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"F\u00e1bio V.","family":"Martinez","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2018,5,8]]},"reference":[{"key":"2130_CR1","doi-asserted-by":"crossref","unstructured":"Sankoff D. Edit distance for genome comparison based on non-local operations. In: Proc. of CPM 1992 LNCS, vol. 644.1992. p. 121\u201335.","DOI":"10.1007\/3-540-56024-6_10"},{"issue":"11","key":"2130_CR2","doi-asserted-by":"publisher","first-page":"909","DOI":"10.1093\/bioinformatics\/15.11.909","volume":"15","author":"D Sankoff","year":"1999","unstructured":"Sankoff D. Genome rearrangement with gene families. Bioinformatics. 1999; 15(11):909\u201317.","journal-title":"Bioinformatics"},{"key":"2130_CR3","volume-title":"Proc. of FOCS 1993","author":"V Bafna","year":"1993","unstructured":"Bafna V, Pevzner P. Genome rearrangements and sorting by reversals. In: Proc. of FOCS 1993. Palo Alto: IEEE: 1993. p. 148\u201357."},{"key":"2130_CR4","volume-title":"Proc. of FOCS 1995","author":"S Hannenhalli","year":"1995","unstructured":"Hannenhalli S, Pevzner P. Transforming men into mice (polynomial algorithm for genomic distance problem). In: Proc. of FOCS 1995. Milwaukee: IEEE: 1995. p. 581\u201392."},{"issue":"16","key":"2130_CR5","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 interchanges. Bioinformatics. 2005; 21(16):3340\u20136.","journal-title":"Bioinformatics"},{"key":"2130_CR6","volume-title":"Proc. of WABI 2006. LNBI, vol. 4175","author":"A Bergeron","year":"2006","unstructured":"Bergeron A, Mixtacki J, Stoye J. A unifying view of genome rearrangements In: Bucher P, Moret BME, editors. Proc. of WABI 2006. LNBI, vol. 4175. Zurich: Springer: 2006. p. 163\u201373."},{"issue":"9","key":"2130_CR7","doi-asserted-by":"publisher","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":"2130_CR8","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."},{"issue":"6","key":"2130_CR9","doi-asserted-by":"publisher","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":"4","key":"2130_CR10","doi-asserted-by":"publisher","first-page":"379","DOI":"10.1089\/cmb.2007.A001","volume":"14","author":"S Angibaud","year":"2007","unstructured":"Angibaud S, Fertin G, Rusu I, Vialette S. A pseudo-boolean framework for computing rearrangement distances between genomes with duplicates. J Comput Biol. 2007; 14(4):379\u201393.","journal-title":"J Comput Biol"},{"issue":"8","key":"2130_CR11","doi-asserted-by":"publisher","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 Comput Biol. 2008; 15(8):1093\u2013115.","journal-title":"J Comput Biol"},{"issue":"1","key":"2130_CR12","doi-asserted-by":"publisher","first-page":"19","DOI":"10.7155\/jgaa.00175","volume":"13","author":"S Angibaud","year":"2009","unstructured":"Angibaud S, Fertin G, Rusu I, Th\u00e9venin A, Vialette S. On the approximability of comparing genomes with duplicates. Journal of Graph Algorithms and Applications. 2009; 13(1):19\u201353.","journal-title":"Journal of Graph Algorithms and Applications"},{"key":"2130_CR13","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. Pittsburg: Springer: 2014. p. 280\u2013292."},{"issue":"Suppl 19","key":"2130_CR14","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1186\/1471-2105-13-S19-S3","volume":"13","author":"D Doerr","year":"2012","unstructured":"Doerr D, Th\u00e9venin A, Stoye J. Gene family assignment-free comparative genomics. BMC Bioinformatics. 2012; 13(Suppl 19):3.","journal-title":"BMC Bioinformatics"},{"key":"2130_CR15","volume-title":"Models and Algorithms for Genome Evolution","author":"MDV Braga","year":"2013","unstructured":"Braga MDV, Chauve C, Doerr D, Jahn K, Stoye J, Th\u00e9venin A, Wittler R. The potential of family-free genome comparison In: Chauve C, El-Mabrouk N, Tannier E, editors. Models and Algorithms for Genome Evolution. London: Springer: 2013. p. 287\u2013307. Chap. 13."},{"issue":"1","key":"2130_CR16","doi-asserted-by":"publisher","first-page":"621","DOI":"10.1534\/genetics.166.1.621","volume":"166","author":"R Durrett","year":"2004","unstructured":"Durrett R, Nielsen R, York TL. Bayesian estimation of genomic distance. Genetics. 2004; 166(1):621\u20139.","journal-title":"Genetics"},{"key":"2130_CR17","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. Algoritm Mol Biol. 2015; 10:13.","journal-title":"Algoritm Mol Biol"},{"key":"2130_CR18","volume-title":"Proc. of RECOMB-CG 2017. LNBI","author":"DP Rubert","year":"2017","unstructured":"Rubert DP, Medeiros GL, Hoshino EA, Braga MDV, Stoye J, Martinez FV. Algorithms for computing the family-free genomic similarity under DCJ. In: Proc. of RECOMB-CG 2017. LNBI. Barcelona: Springer International Publishing: 2017. p. 76\u2013100."},{"key":"2130_CR19","volume-title":"Proc. of Combinatorial Pattern Matching (CPM 2007)","author":"Z Chen","year":"2007","unstructured":"Chen Z, Fu B, Xu J, Yang B, Zhao Z, Zhu B. Non-breaking similarity of genomes with gene repetitions. In: Proc. of Combinatorial Pattern Matching (CPM 2007). Heidelberg: Springer: 2007. p. 137\u201343."},{"key":"2130_CR20","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1186\/s13015-017-0095-y","volume":"12","author":"DP Rubert","year":"2017","unstructured":"Rubert DP, Feij\u00e3o P, Braga MDV, Stoye J, Martinez FV. Approximating the DCJ distance of balanced genomes in linear time. Algoritm Mol Biol. 2017; 12:3.","journal-title":"Algoritm Mol Biol"},{"issue":"Suppl 19","key":"2130_CR21","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 Bioinformatics. 2012; 13(Suppl 19):13.","journal-title":"BMC Bioinformatics"},{"issue":"1","key":"2130_CR22","first-page":"32","volume":"5","author":"J Munkres","year":"1957","unstructured":"Munkres J. Algorithms for the assignment and transportation problems. J SIAM. 1957; 5(1):32\u201328.","journal-title":"J SIAM"},{"issue":"2","key":"2130_CR23","doi-asserted-by":"publisher","first-page":"248","DOI":"10.1145\/321694.321699","volume":"19","author":"J Edmonds","year":"1972","unstructured":"Edmonds J, Karp RM. Theoretical improvements in algorithmic efficiency for network flow problems. J ACM. 1972; 19(2):248\u201364.","journal-title":"J ACM"},{"issue":"2","key":"2130_CR24","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1002\/net.3230010206","volume":"1","author":"N Tomizawa","year":"1971","unstructured":"Tomizawa N. On some techniques useful for solution of transportation network problems. Networks. 1971; 1(2):173\u201394.","journal-title":"Networks"},{"key":"2130_CR25","unstructured":"Hawick KA, James HA. Enumerating circuits and loops in graphs with self-arcs and multiple-arcs, Technical Report CSTN-013: Massey University; 2008."},{"issue":"1","key":"2130_CR26","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1137\/0204007","volume":"4","author":"D Johnson","year":"1975","unstructured":"Johnson D. Finding all the elementary circuits of a directed graph. SIAM J Comput. 1975; 4(1):77\u201384.","journal-title":"SIAM J Comput"},{"key":"2130_CR27","volume-title":"Proc. of SWAT 2000","author":"P Berman","year":"2000","unstructured":"Berman P. A d\/2 approximation for maximum weight independent set in d-claw free graphs In: Halld\u00f3rsson MM, editor. Proc. of SWAT 2000. Bergen: Springer-Verlag Berlin Heidelberg: 2000. p. 214\u20139."},{"issue":"4","key":"2130_CR28","doi-asserted-by":"publisher","first-page":"1115","DOI":"10.1093\/molbev\/msr268","volume":"29","author":"DA Dalquen","year":"2012","unstructured":"Dalquen DA, Anisimova M, Gonnet GH, Dessimoz C. Alf \u2013 a simulation framework for genome evolution. Mol Biol Evol. 2012; 29(4):1115.","journal-title":"Mol Biol Evol"},{"key":"2130_CR29","unstructured":"Doerr D. Family Free Genome Comparison (FFGC). 2017. \n                    https:\/\/bibiserv2.cebitec.uni-bielefeld.de\/ffgc\n                    \n                  . Accessed 31 Jan 2018."},{"key":"2130_CR30","volume-title":"Sex Chromosomes and Sex-linked Genes. Endocrinology, vol. 1","author":"S Ohno","year":"2013","unstructured":"Ohno S. Sex Chromosomes and Sex-linked Genes. Endocrinology, vol. 1. Berlin, Heidelberg: Springer; 2013."}],"container-title":["BMC Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1186\/s12859-018-2130-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1186\/s12859-018-2130-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1186\/s12859-018-2130-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,7]],"date-time":"2019-05-07T23:35:28Z","timestamp":1557272128000},"score":1,"resource":{"primary":{"URL":"https:\/\/bmcbioinformatics.biomedcentral.com\/articles\/10.1186\/s12859-018-2130-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,5]]},"references-count":30,"journal-issue":{"issue":"S6","published-print":{"date-parts":[[2018,5]]}},"alternative-id":["2130"],"URL":"https:\/\/doi.org\/10.1186\/s12859-018-2130-5","relation":{},"ISSN":["1471-2105"],"issn-type":[{"value":"1471-2105","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,5]]},"assertion":[{"value":"8 May 2018","order":1,"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"}},{"value":"Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.","order":4,"name":"Ethics","group":{"name":"EthicsHeading","label":"Publisher\u2019s Note"}}],"article-number":"152"}}