{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,24]],"date-time":"2025-04-24T20:40:10Z","timestamp":1745527210103,"version":"3.40.4"},"publisher-location":"Cham","reference-count":32,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783031902512","type":"print"},{"value":"9783031902529","type":"electronic"}],"license":[{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2025]]},"DOI":"10.1007\/978-3-031-90252-9_11","type":"book-chapter","created":{"date-parts":[[2025,4,24]],"date-time":"2025-04-24T20:03:59Z","timestamp":1745525039000},"page":"175-189","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["An Exact and\u00a0Fast SAT Formulation for\u00a0the\u00a0DCJ Distance"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0009-0003-6597-739X","authenticated-orcid":false,"given":"Aaryan M.","family":"Sarnaik","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2383-4289","authenticated-orcid":false,"given":"Ke","family":"Chen","sequence":"additional","affiliation":[]},{"given":"Austin","family":"Diaz","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6112-5139","authenticated-orcid":false,"given":"Mingfu","family":"Shao","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,4,25]]},"reference":[{"key":"11_CR1","doi-asserted-by":"crossref","unstructured":"Aken, B.L., et al.: The Ensembl gene annotation system. Database: J. Biol. Databases Curation 2016, baw093 (2016)","DOI":"10.1093\/database\/baw093"},{"issue":"01","key":"11_CR2","doi-asserted-by":"publisher","first-page":"1840001","DOI":"10.1142\/S0218213018400018","volume":"27","author":"G Audemard","year":"2018","unstructured":"Audemard, G., Simon, L.: On the glucose sat solver. Int. J. Artif. Intell. Tools 27(01), 1840001 (2018)","journal-title":"Int. J. Artif. Intell. Tools"},{"issue":"5","key":"11_CR3","doi-asserted-by":"publisher","first-page":"483","DOI":"10.1089\/106652701753216503","volume":"8","author":"D Bader","year":"2001","unstructured":"Bader, D., Moret, B., Yan, M.: A fast linear-time algorithm for inversion distance with an experimental comparison. J. Comput. Biol. 8(5), 483\u2013491 (2001)","journal-title":"J. Comput. Biol."},{"key":"11_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1007\/11851561_16","volume-title":"Algorithms Bioinform.","author":"A Bergeron","year":"2006","unstructured":"Bergeron, A., Mixtacki, J., Stoye, J.: A unifying view of genome rearrangements. In: B\u00fccher, P., Moret, B. (eds.) WABI 2006. LNCS, vol. 4175, pp. 163\u2013173. Springer, Heidelberg (2006). https:\/\/doi.org\/10.1007\/11851561_16"},{"issue":"51","key":"11_CR5","doi-asserted-by":"publisher","first-page":"5300","DOI":"10.1016\/j.tcs.2009.09.008","volume":"410","author":"A Bergeron","year":"2009","unstructured":"Bergeron, A., Mixtacki, J., Stoye, J.: A new linear-time algorithm to compute the genomic distance via the double cut and join distance. Theor. Comput. Sci. 410(51), 5300\u20135316 (2009)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"11_CR6","doi-asserted-by":"publisher","first-page":"122","DOI":"10.1109\/TCBB.2012.168","volume":"10","author":"P Biller","year":"2012","unstructured":"Biller, P., Feij\u00e3o, P., Meidanis, J.: Rearrangement-based phylogeny using the single-cut-or-join operation. IEEE\/ACM Trans. Comput. Biol. Bioinf. 10(1), 122\u2013134 (2012)","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinf."},{"issue":"4","key":"11_CR7","doi-asserted-by":"publisher","first-page":"410","DOI":"10.1089\/cmb.2020.0434","volume":"28","author":"L Bohnenk\u00e4mper","year":"2021","unstructured":"Bohnenk\u00e4mper, L., Braga, M.D., Doerr, D., Stoye, J.: Computing the rearrangement distance of natural genomes. J. Comput. Biol. 28(4), 410\u2013431 (2021)","journal-title":"J. Comput. Biol."},{"key":"11_CR8","doi-asserted-by":"crossref","unstructured":"Chen, J.M., Cooper, D.N., F\u00e9rec, C., Kehrer-Sawatzki, H., Patrinos, G.P.: Genomic rearrangements in inherited disease and cancer. In: Seminars in Cancer Biology, vol.\u00a020, pp. 222\u2013233. Elsevier (2010)","DOI":"10.1016\/j.semcancer.2010.05.007"},{"key":"11_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"439","DOI":"10.1007\/978-3-642-14031-0_47","volume-title":"Comput. Comb.","author":"X Chen","year":"2010","unstructured":"Chen, X.: On sorting permutations by double-cut-and-joins. In: Thai, M.T., Sahni, S. (eds.) COCOON 2010. LNCS, vol. 6196, pp. 439\u2013448. Springer, Heidelberg (2010). https:\/\/doi.org\/10.1007\/978-3-642-14031-0_47"},{"issue":"Suppl 9","key":"11_CR10","doi-asserted-by":"publisher","first-page":"S17","DOI":"10.1186\/1471-2105-12-S9-S17","volume":"12","author":"X Chen","year":"2011","unstructured":"Chen, X., Sun, R., Yu, J.: Approximating the double-cut-and-join distance between unsigned genomes. BMC Bioinform. 12(Suppl 9), S17 (2011)","journal-title":"BMC Bioinform."},{"issue":"4","key":"11_CR11","doi-asserted-by":"publisher","first-page":"302","DOI":"10.1109\/TCBB.2005.48","volume":"2","author":"X Chen","year":"2005","unstructured":"Chen, X., et al.: Assignment of orthologous genes via genome rearrangement. ACM\/IEEE Trans. Comput. Bio. Bioinf. 2(4), 302\u2013315 (2005)","journal-title":"ACM\/IEEE Trans. Comput. Bio. Bioinf."},{"key":"11_CR12","unstructured":"Frisch, A.M., Peugniez, T.J.: Solving non-boolean satisfiability problems with stochastic local search. In: Proceedings of the 17th International Joint Conference on Artificial Intelligence, vol. 1, pp. 282\u2013288 (2001)"},{"issue":"9","key":"11_CR13","doi-asserted-by":"publisher","first-page":"1160","DOI":"10.1089\/cmb.2007.0048","volume":"14","author":"Z Fu","year":"2007","unstructured":"Fu, Z., Chen, X., Vacic, V., Nan, P., Zhong, Y., Jiang, T.: MSOAR: a high-throughput ortholog assignment system based on genome rearrangement. J. Comput. Biol. 14(9), 1160\u20131175 (2007)","journal-title":"J. Comput. Biol."},{"key":"11_CR14","doi-asserted-by":"crossref","unstructured":"Gusfield, D.: From integer linear programming to sat-solving in computational biology (2020)","DOI":"10.1017\/9781108377737"},{"key":"11_CR15","doi-asserted-by":"crossref","unstructured":"Hannenhalli, S., Pevzner, P.: Transforming cabbage into turnip (polynomial algorithm for sorting signed permutations by reversals). In: Proceedings of the 27th Annual ACM Symposium on Theory of Computing (STOC 1995), pp. 178\u2013189. ACM Press, New York (1995)","DOI":"10.1145\/225058.225112"},{"key":"11_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"428","DOI":"10.1007\/978-3-319-94144-8_26","volume-title":"Theory and Applications of Satisfiability Testing \u2013 SAT 2018","author":"A Ignatiev","year":"2018","unstructured":"Ignatiev, A., Morgado, A., Marques-Silva, J.: PySAT: a python toolkit for prototyping with SAT oracles. In: Beyersdorff, O., Wintersteiger, C.M. (eds.) SAT 2018. LNCS, vol. 10929, pp. 428\u2013437. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-319-94144-8_26"},{"key":"11_CR17","unstructured":"Inc., G.O.: Gurobi optimizer reference manual (2013). http:\/\/www.gurobi.com"},{"issue":"1","key":"11_CR18","doi-asserted-by":"publisher","first-page":"14","DOI":"10.1016\/j.ipl.2007.04.011","volume":"104","author":"G Jean","year":"2007","unstructured":"Jean, G., Nikolski, M.: Genome rearrangements: a correct algorithm for optimal capping. Inf. Proc. Letters 104(1), 14\u201320 (2007)","journal-title":"Inf. Proc. Letters"},{"issue":"13","key":"11_CR19","doi-asserted-by":"publisher","first-page":"i114","DOI":"10.1093\/bioinformatics\/btn148","volume":"24","author":"Y Lin","year":"2008","unstructured":"Lin, Y., Moret, B.M.: Estimating true evolutionary distances under the DCJ model. Bioinformatics 24(13), i114\u2013i122 (2008)","journal-title":"Bioinformatics"},{"issue":"1987\u20132018","key":"11_CR20","first-page":"1","volume":"12","author":"CU Manual","year":"1987","unstructured":"Manual, C.U.: IBM ILOG CPLEX optimization studio. Version 12(1987\u20132018), 1 (1987)","journal-title":"Version"},{"key":"11_CR21","series-title":"Computational Biology","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1007\/978-1-4471-5298-9_7","volume-title":"Models and Algorithms for Genome Evolution","author":"B Moret","year":"2013","unstructured":"Moret, B., Lin, Y., Tang, J.: Rearrangements in phylogenetic inference: compare, model, or encode? In: Chauve, C., El-Mabrouk, N., Tannier, E. (eds.) Models and Algorithms for Genome Evolution. Computational Biology, vol. 19, pp. 147\u2013172. Springer, Berlin (2013). https:\/\/doi.org\/10.1007\/978-1-4471-5298-9_7"},{"key":"11_CR22","unstructured":"Nguyen, S.H.V.H.: An efficient encoding of the at-most-one constraint (2013)"},{"key":"11_CR23","doi-asserted-by":"crossref","unstructured":"Nguyen, V.H., Nguyen, V.Q., Kim, K., Barahona, P.: Empirical study on sat-encodings of the at-most-one constraint. In: The 9th International Conference on Smart Media and Applications, pp. 470\u2013475 (2020)","DOI":"10.1145\/3426020.3426170"},{"issue":"1","key":"11_CR24","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1142\/S0219720003000198","volume":"1","author":"M Ozery-Flato","year":"2003","unstructured":"Ozery-Flato, M., Shamir, R.: Two notes on genome rearrangement. J. Bioinf. Comp. Bio. 1(1), 71\u201394 (2003)","journal-title":"J. Bioinf. Comp. Bio."},{"issue":"3","key":"11_CR25","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1016\/S0747-7171(86)80028-1","volume":"2","author":"DA Plaisted","year":"1986","unstructured":"Plaisted, D.A., Greenbaum, S.: A structure-preserving clause form translation. J. Symb. Comput. 2(3), 293\u2013304 (1986)","journal-title":"J. Symb. Comput."},{"key":"11_CR26","doi-asserted-by":"crossref","unstructured":"Prestwich, S.: Finding large cliques using sat local search. Trends in Constraint Programming, pp. 269\u2013274 (2007)","DOI":"10.1002\/9780470612309.ch15"},{"key":"11_CR27","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, Yu., 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). https:\/\/doi.org\/10.1007\/978-3-319-05269-4_22"},{"key":"11_CR28","doi-asserted-by":"crossref","unstructured":"Shi, G., Zhang, L., Jiang, T.: MSOAR 2.0: incorporating tandem duplications into ortholog assignment based on genome rearrangement. BMC Bioinform. 11(1), 10 (2010)","DOI":"10.1186\/1471-2105-11-10"},{"issue":"3","key":"11_CR29","doi-asserted-by":"publisher","first-page":"587","DOI":"10.1016\/S0022-0000(02)00011-9","volume":"65","author":"G Tesler","year":"2002","unstructured":"Tesler, G.: Efficient algorithms for multichromosomal genome rearrangements. J. Comput. Syst. Sci. 65(3), 587\u2013609 (2002)","journal-title":"J. Comput. Syst. Sci."},{"key":"11_CR30","first-page":"234","volume":"8","author":"GS Tseitin","year":"1968","unstructured":"Tseitin, G.S.: On the complexity of proof in prepositional calculus. Zapiski Nauchnykh Seminarov POMI 8, 234\u2013259 (1968)","journal-title":"Zapiski Nauchnykh Seminarov POMI"},{"issue":"16","key":"11_CR31","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 21(16), 3340\u20133346 (2005)","journal-title":"Bioinformatics"},{"key":"11_CR32","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"170","DOI":"10.1007\/978-3-540-87989-3_13","volume-title":"Comparative Genomics","author":"S Yancopoulos","year":"2008","unstructured":"Yancopoulos, S., Friedberg, R.: Sorting genomes with insertions, deletions and duplications by DCJ. In: Nelson, C.E., Vialette, S. (eds.) RECOMB-CG 2008. LNCS, vol. 5267, pp. 170\u2013183. Springer, Heidelberg (2008). https:\/\/doi.org\/10.1007\/978-3-540-87989-3_13"}],"container-title":["Lecture Notes in Computer Science","Research in Computational Molecular Biology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-90252-9_11","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,24]],"date-time":"2025-04-24T20:04:07Z","timestamp":1745525047000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-90252-9_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025]]},"ISBN":["9783031902512","9783031902529"],"references-count":32,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-90252-9_11","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025]]},"assertion":[{"value":"25 April 2025","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"The authors declare that there is no conflict of interest.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Disclosure of Interests"}},{"value":"RECOMB","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Research in Computational Molecular Biology","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Seoul","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Korea (Republic of)","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2025","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"26 April 2025","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"29 April 2025","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"29","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"recomb2025","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/recomb.org\/recomb2025\/index.html","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}