{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T16:49:38Z","timestamp":1743094178899,"version":"3.40.3"},"publisher-location":"Cham","reference-count":27,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319679785"},{"type":"electronic","value":"9783319679792"}],"license":[{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2017]]},"DOI":"10.1007\/978-3-319-67979-2_5","type":"book-chapter","created":{"date-parts":[[2017,9,14]],"date-time":"2017-09-14T00:31:23Z","timestamp":1505349083000},"page":"76-100","source":"Crossref","is-referenced-by-count":0,"title":["Algorithms for Computing the Family-Free Genomic Similarity Under DCJ"],"prefix":"10.1007","author":[{"given":"Diego P.","family":"Rubert","sequence":"first","affiliation":[]},{"given":"Gabriel L.","family":"Medeiros","sequence":"additional","affiliation":[]},{"given":"Edna A.","family":"Hoshino","sequence":"additional","affiliation":[]},{"given":"Mar\u00edlia D. V.","family":"Braga","sequence":"additional","affiliation":[]},{"given":"Jens","family":"Stoye","sequence":"additional","affiliation":[]},{"given":"F\u00e1bio V.","family":"Martinez","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,9,15]]},"reference":[{"issue":"8","key":"5_CR1","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. Comput. Biol. 15(8), 1093\u20131115 (2008)","journal-title":"J. Comput. Biol."},{"issue":"1","key":"5_CR2","doi-asserted-by":"crossref","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. J. Graph Algorithms Appl. 13(1), 19\u201353 (2009)","journal-title":"J. Graph Algorithms Appl."},{"issue":"4","key":"5_CR3","doi-asserted-by":"crossref","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. 14(4), 379\u2013393 (2007)","journal-title":"J. Comput. Biol."},{"key":"5_CR4","doi-asserted-by":"crossref","unstructured":"Ausiello, G., Protasi, M., Marchetti-Spaccamela, A., Gambosi, G., Crescenzi, P., Kann, V.: Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties. Springer (1999)","DOI":"10.1007\/978-3-642-58412-1"},{"key":"5_CR5","doi-asserted-by":"crossref","unstructured":"Bafna, V., Pevzner, P.: Genome rearrangements and sorting by reversals. In: Proceedings of the FOCS 1993, pp. 148\u2013157 (1993)","DOI":"10.1109\/SFCS.1993.366872"},{"key":"5_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1007\/11851561_16","volume-title":"Algorithms in Bioinformatics","author":"A Bergeron","year":"2006","unstructured":"Bergeron, A., Mixtacki, J., Stoye, J.: A unifying view of genome rearrangements. In: B\u00fccher, P., Moret, B.M.E. (eds.) WABI 2006. LNCS, vol. 4175, pp. 163\u2013173. Springer, Heidelberg (2006). doi:\n10.1007\/11851561_16"},{"key":"5_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"214","DOI":"10.1007\/3-540-44985-X_19","volume-title":"Algorithm Theory - 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, M.M. (ed.) SWAT 2000. LNCS, vol. 1851, pp. 214\u2013219. Springer, Heidelberg (2000). doi:\n10.1007\/3-540-44985-X_19"},{"key":"5_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"200","DOI":"10.1007\/3-540-48523-6_17","volume-title":"Automata, Languages and Programming","author":"P Berman","year":"1999","unstructured":"Berman, P., Karpinski, M.: On some tighter inapproximability results (extended abstract). In: Wiedermann, J., van Emde Boas, P., Nielsen, M. (eds.) ICALP 1999. LNCS, vol. 1644, pp. 200\u2013209. Springer, Heidelberg (1999). doi:\n10.1007\/3-540-48523-6_17"},{"issue":"9","key":"5_CR9","doi-asserted-by":"crossref","first-page":"1167","DOI":"10.1089\/cmb.2011.0118","volume":"18","author":"MDV Braga","year":"2011","unstructured":"Braga, M.D.V., Willing, E., Stoye, J.: Double cut and join with insertions and deletions. J. Comput. Biol. 18(9), 1167\u20131184 (2011)","journal-title":"J. Comput. Biol."},{"key":"5_CR10","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1007\/978-1-4471-5298-9_13","volume-title":"Models and Algorithms for Genome Evolution","author":"MDV Braga","year":"2013","unstructured":"Braga, M.D.V., Chauve, C., D\u00f6rr, 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. (eds.) Models and Algorithms for Genome Evolution, vol. 19, pp. 287\u2013307. Springer, London (2013). doi:\n10.1007\/978-1-4471-5298-9_13\n\n. Chap. 13"},{"key":"5_CR11","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, J.H. (eds.) Comparative Genomics, pp. 207\u2013211. Kluwer Academic Publishers, Dortrecht (2000)"},{"issue":"6","key":"5_CR12","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. 10(6), 1384\u20131390 (2013)","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinf."},{"key":"5_CR13","doi-asserted-by":"publisher","unstructured":"Crescenzi, P.: A short guide to approximation preserving reductions. In: Twelfth Annual IEEE Conference on Proceedings of Computational Complexity, pp. 262\u2013273 (1997). doi:\n10.1109\/CCC.1997.612321","DOI":"10.1109\/CCC.1997.612321"},{"issue":"4","key":"5_CR14","doi-asserted-by":"crossref","first-page":"1115","DOI":"10.1093\/molbev\/msr268","volume":"29","author":"DA Dalquen","year":"2012","unstructured":"Dalquen, D.A., Anisimova, M., Gonnet, G.H., Dessimoz, C.: ALF - a simulation framework for genome evolution. Mol. Biol. Evol. 29(4), 1115 (2012)","journal-title":"Mol. Biol. Evol."},{"issue":"Suppl 19","key":"5_CR15","doi-asserted-by":"crossref","first-page":"S3","DOI":"10.1186\/1471-2105-13-S19-S3","volume":"13","author":"D D\u00f6rr","year":"2012","unstructured":"D\u00f6rr, D., Th\u00e9venin, A., Stoye, J.: Gene family assignment-free comparative genomics. BMC Bioinform. 13(Suppl 19), S3 (2012)","journal-title":"BMC Bioinform."},{"key":"5_CR16","doi-asserted-by":"publisher","unstructured":"Hannenhalli, S., Pevzner, P.: Transforming men into mice (polynomial algorithm for genomic distance problem). In: Proceedings of the FOCS 1995, pp. 581\u2013592 (1995). doi:\n10.1109\/SFCS.1995.492588","DOI":"10.1109\/SFCS.1995.492588"},{"issue":"4","key":"5_CR17","doi-asserted-by":"crossref","first-page":"798","DOI":"10.1145\/502090.502098","volume":"48","author":"J H\u00e5stad","year":"2001","unstructured":"H\u00e5stad, J.: Some optimal inapproximability results. J. ACM (JACM) 48(4), 798\u2013859 (2001)","journal-title":"J. ACM (JACM)"},{"key":"5_CR18","unstructured":"Hawick, K.A., James, H.A.: Enumerating circuits and loops in graphs with self-arcs and multiple-arcs. Technical report CSTN-013, Massey University (2008)"},{"issue":"1","key":"5_CR19","doi-asserted-by":"crossref","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. 4(1), 77\u201384 (1975)","journal-title":"SIAM J. Comput."},{"key":"5_CR20","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1186\/s13015-015-0041-9","volume":"10","author":"FV Martinez","year":"2015","unstructured":"Martinez, F.V., Feij\u00e3o, P., Braga, M.D.V., Stoye, J.: On the family-free DCJ distance and similarity. Algorithms Mol. Biol. 10, 13 (2015)","journal-title":"Algorithms Mol. Biol."},{"issue":"1","key":"5_CR21","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/S0020-0190(97)00223-8","volume":"65","author":"V Raman","year":"1998","unstructured":"Raman, V., Ravikumar, B., Rao, S.S.: A simplified NP-complete MAXSAT problem. Inf. Process. Lett. 65(1), 1\u20136 (1998)","journal-title":"Inf. Process. Lett."},{"key":"5_CR22","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1186\/s13015-017-0095-y","volume":"12","author":"DP Rubert","year":"2017","unstructured":"Rubert, D.P., Feij\u00e3o, P., Braga, M.D.V., Stoye, J., Martinez, F.V.: Approximating the DCJ distance of balanced genomes in linear time. Algorithms Mol. Biol. 12, 3 (2017)","journal-title":"Algorithms Mol. Biol."},{"key":"5_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1007\/3-540-56024-6_10","volume-title":"Combinatorial Pattern Matching","author":"D Sankoff","year":"1992","unstructured":"Sankoff, D.: Edit distance for genome comparison based on non-local operations. In: Apostolico, A., Crochemore, M., Galil, Z., Manber, U. (eds.) CPM 1992. LNCS, vol. 644, pp. 121\u2013135. Springer, Heidelberg (1992). doi:\n10.1007\/3-540-56024-6_10"},{"issue":"11","key":"5_CR24","doi-asserted-by":"crossref","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 15(11), 909\u2013917 (1999)","journal-title":"Bioinformatics"},{"issue":"Suppl 19","key":"5_CR25","doi-asserted-by":"crossref","first-page":"S13","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. 13(Suppl 19), S13 (2012)","journal-title":"BMC Bioinform."},{"key":"5_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"280","DOI":"10.1007\/978-3-319-05269-4_22","volume-title":"Research in Computational Molecular Biology","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: Sharan, R. (ed.) RECOMB 2014. LNCS, vol. 8394, pp. 280\u2013292. Springer, Cham (2014). doi:\n10.1007\/978-3-319-05269-4_22"},{"issue":"16","key":"5_CR27","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 21(16), 3340\u20133346 (2005)","journal-title":"Bioinformatics"}],"container-title":["Lecture Notes in Computer Science","Comparative Genomics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-67979-2_5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2017,9,21]],"date-time":"2017-09-21T04:54:36Z","timestamp":1505969676000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-67979-2_5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319679785","9783319679792"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-67979-2_5","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2017]]}}}