{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,22]],"date-time":"2026-06-22T14:19:56Z","timestamp":1782137996898,"version":"3.54.5"},"reference-count":70,"publisher":"Public Library of Science (PLoS)","issue":"7","license":[{"start":{"date-parts":[[2024,7,24]],"date-time":"2024-07-24T00:00:00Z","timestamp":1721779200000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"NSF","award":["MCB-2143289"],"award-info":[{"award-number":["MCB-2143289"]}]},{"name":"NSF","award":["MCB-2324909"],"award-info":[{"award-number":["MCB-2324909"]}]},{"name":"NIH","award":["T32GM130546"],"award-info":[{"award-number":["T32GM130546"]}]}],"content-domain":{"domain":["www.ploscompbiol.org"],"crossmark-restriction":false},"short-container-title":["PLoS Comput Biol"],"abstract":"<jats:p>Dense arrangements of binding sites within nucleotide sequences can collectively influence downstream transcription rates or initiate biomolecular interactions. For example, natural promoter regions can harbor many overlapping transcription factor binding sites that influence the rate of transcription initiation. Despite the prevalence of overlapping binding sites in nature, rapid design of nucleotide sequences with many overlapping sites remains a challenge. Here, we show that this is an NP-hard problem, coined here as the nucleotide String Packing Problem (SPP). We then introduce a computational technique that efficiently assembles sets of DNA-protein binding sites into dense, contiguous stretches of double-stranded DNA. For the efficient design of nucleotide sequences spanning hundreds of base pairs, we reduce the SPP to an Orienteering Problem with integer distances, and then leverage modern integer linear programming solvers. Our method optimally packs sets of 20\u2013100 binding sites into dense nucleotide arrays of 50\u2013300 base pairs in 0.05\u201310 seconds. Unlike approximation algorithms or meta-heuristics, our approach finds provably optimal solutions. We demonstrate how our method can generate large sets of diverse sequences suitable for library generation, where the frequency of binding site usage across the returned sequences can be controlled by modulating the objective function. As an example, we then show how adding additional constraints, like the inclusion of sequence elements with fixed positions, allows for the design of bacterial promoters. The nucleotide string packing approach we present can accelerate the design of sequences with complex DNA-protein interactions. When used in combination with synthesis and high-throughput screening, this design strategy could help interrogate how complex binding site arrangements impact either gene expression or biomolecular mechanisms in varied cellular contexts.<\/jats:p>","DOI":"10.1371\/journal.pcbi.1012276","type":"journal-article","created":{"date-parts":[[2024,7,24]],"date-time":"2024-07-24T13:51:08Z","timestamp":1721829068000},"page":"e1012276","update-policy":"https:\/\/doi.org\/10.1371\/journal.pcbi.corrections_policy","source":"Crossref","is-referenced-by-count":1,"title":["Generating information-dense promoter sequences with optimal string packing"],"prefix":"10.1371","volume":"20","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2383-1478","authenticated-orcid":true,"given":"Virgile","family":"Andreani","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4426-3729","authenticated-orcid":true,"given":"Eric J.","family":"South","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9261-8216","authenticated-orcid":true,"given":"Mary J.","family":"Dunlop","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"340","published-online":{"date-parts":[[2024,7,24]]},"reference":[{"issue":"11","key":"pcbi.1012276.ref001","doi-asserted-by":"crossref","first-page":"699","DOI":"10.1038\/s41576-020-0254-8","article-title":"Redefining fundamental concepts of transcription initiation in bacteria","volume":"21","author":"C Mej\u00eda-Almonte","year":"2020","journal-title":"Nat Rev Genet"},{"issue":"6","key":"pcbi.1012276.ref002","doi-asserted-by":"crossref","first-page":"521","DOI":"10.1038\/nbt.2205","article-title":"Inferring gene regulatory logic from high-throughput measurements of thousands of systematically designed promoters","volume":"30","author":"E Sharon","year":"2012","journal-title":"Nat Biotechnol"},{"issue":"1","key":"pcbi.1012276.ref003","doi-asserted-by":"crossref","first-page":"5159","DOI":"10.1038\/s41467-022-32829-5","article-title":"Automated model-predictive design of synthetic promoters to control transcriptional profiles in bacteria","volume":"13","author":"TL LaFleur","year":"2022","journal-title":"Nat Commun"},{"issue":"8","key":"pcbi.1012276.ref004","doi-asserted-by":"crossref","first-page":"e00512","DOI":"10.1128\/JB.00512-20","article-title":"The Context-Dependent Influence of Promoter Sequence Motifs on Transcription Initiation Kinetics and Regulation","volume":"203","author":"D Jensen","year":"2021","journal-title":"J Bacteriol"},{"issue":"1","key":"pcbi.1012276.ref005","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1101\/gr.212316.116","article-title":"Large-scale mapping of gene regulatory logic reveals context-dependent repression by transcriptional activators","volume":"27","author":"D van Dijk","year":"2017","journal-title":"Genome Res"},{"issue":"15","key":"pcbi.1012276.ref006","doi-asserted-by":"crossref","first-page":"7648","DOI":"10.1093\/nar\/gkv616","article-title":"Synthetic biosensors for precise gene control and real-time monitoring of metabolites","volume":"43","author":"JK Rogers","year":"2015","journal-title":"Nucleic Acids Res"},{"key":"pcbi.1012276.ref007","doi-asserted-by":"crossref","first-page":"797","DOI":"10.1016\/j.tibtech.2020.03.013","article-title":"Genetic Biosensor Design for Natural Product Biosynthesis in Microorganisms","volume":"38","author":"GS Hossain","year":"2020","journal-title":"Trends Biotechnol"},{"key":"pcbi.1012276.ref008","article-title":"The architecture of binding cooperativity between densely bound transcription factors","author":"O Lupo","year":"2023","journal-title":"Cell Syst [Internet]"},{"issue":"3","key":"pcbi.1012276.ref009","doi-asserted-by":"crossref","first-page":"459","DOI":"10.1016\/j.molcel.2020.05.032","article-title":"Intrinsically Disordered Regions Direct Transcription Factor In Vivo Binding Specificity","volume":"79","author":"S Brodsky","year":"2020","journal-title":"Mol Cell"},{"key":"pcbi.1012276.ref010","doi-asserted-by":"crossref","first-page":"1051","DOI":"10.1146\/annurev.bi.58.070189.005155","article-title":"Molecular mechanisms of transcriptional regulation in yeast","volume":"58","author":"K. Struhl","year":"1989","journal-title":"Annu Rev Biochem"},{"issue":"17","key":"pcbi.1012276.ref011","doi-asserted-by":"crossref","first-page":"8237","DOI":"10.1093\/nar\/gkt598","article-title":"Widespread evidence of cooperative DNA binding by transcription factors in Drosophila development","volume":"41","author":"M Kazemian","year":"2013","journal-title":"Nucleic Acids Res"},{"issue":"5","key":"pcbi.1012276.ref012","doi-asserted-by":"crossref","first-page":"628","DOI":"10.1111\/j.1574-6976.2010.00227.x","article-title":"Prokaryotic genome regulation: multifactor promoters, multitarget regulators and hierarchic networks","volume":"34","author":"A. Ishihama","year":"2010","journal-title":"FEMS Microbiol Rev"},{"issue":"12","key":"pcbi.1012276.ref013","doi-asserted-by":"crossref","first-page":"e114347","DOI":"10.1371\/journal.pone.0114347","article-title":"The Influence of Promoter Architectures and Regulatory Motifs on Gene Expression in Escherichia coli","volume":"9","author":"M Rydenfelt","year":"2014","journal-title":"PLOS ONE"},{"issue":"1","key":"pcbi.1012276.ref014","doi-asserted-by":"crossref","first-page":"244","DOI":"10.1038\/msb.2009.1","article-title":"Environment-specific combinatorial cis-regulation in synthetic promoters","volume":"5","author":"J Gertz","year":"2009","journal-title":"Mol Syst Biol"},{"issue":"1","key":"pcbi.1012276.ref015","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1038\/s41467-020-20094-3","article-title":"Multiplexed characterization of rationally designed promoter architectures deconstructs combinatorial logic for IPTG-inducible systems","volume":"12","author":"TC Yu","year":"2021","journal-title":"Nat Commun"},{"key":"pcbi.1012276.ref016","first-page":"2020","article-title":"Genome-wide Functional Characterization of Escherichia coli Promoters and Regulatory Elements Responsible for their Function [Internet]","author":"G Urtecho","year":"2020","journal-title":"bioRxiv"},{"issue":"6","key":"pcbi.1012276.ref017","doi-asserted-by":"crossref","first-page":"1519","DOI":"10.1016\/j.cell.2016.04.027","article-title":"Direct Identification of Hundreds of Expression-Modulating Variants using a Multiplexed Reporter Assay","volume":"165","author":"R Tewhey","year":"2016","journal-title":"Cell"},{"issue":"5","key":"pcbi.1012276.ref018","doi-asserted-by":"crossref","first-page":"323","DOI":"10.1038\/nmeth.4633","article-title":"Metagenomic mining of regulatory elements enables programmable species-selective gene expression","volume":"15","author":"NI Johns","year":"2018","journal-title":"Nat Methods"},{"issue":"12","key":"pcbi.1012276.ref019","doi-asserted-by":"crossref","first-page":"2015","DOI":"10.1101\/gr.224964.117","article-title":"Deep learning of the regulatory grammar of yeast 5\u2032 untranslated regions from 500,000 random sequences","volume":"27","author":"JT Cuperus","year":"2017","journal-title":"Genome Res"},{"issue":"1","key":"pcbi.1012276.ref020","doi-asserted-by":"crossref","first-page":"5822","DOI":"10.1038\/s41467-020-19446-w","article-title":"Predictive design of sigma factor-specific promoters","volume":"11","author":"M Van Brempt","year":"2020","journal-title":"Nat Commun"},{"issue":"10","key":"pcbi.1012276.ref021","doi-asserted-by":"crossref","first-page":"2100239","DOI":"10.1002\/biot.202100239","article-title":"Advances in promoter engineering: Novel applications and predefined transcriptional control","volume":"16","author":"AP Cazier","year":"2021","journal-title":"Biotechnol J"},{"issue":"1","key":"pcbi.1012276.ref022","doi-asserted-by":"crossref","first-page":"46","DOI":"10.1002\/biot.201200120","article-title":"Promoter engineering: Recent advances in controlling transcription at the most fundamental level","volume":"8","author":"J Blazeck","year":"2013","journal-title":"Biotechnol J"},{"issue":"1","key":"pcbi.1012276.ref023","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1038\/msb4100187","article-title":"Programming gene expression with combinatorial promoters","volume":"3","author":"RS Cox III","year":"2007","journal-title":"Mol Syst Biol"},{"key":"pcbi.1012276.ref024","doi-asserted-by":"crossref","first-page":"110","DOI":"10.1016\/j.gde.2017.02.007","article-title":"Transcription factor\u2013DNA binding: beyond binding site motifs","volume":"43","author":"S Inukai","year":"2017","journal-title":"Curr Opin Genet Dev"},{"issue":"11","key":"pcbi.1012276.ref025","doi-asserted-by":"crossref","first-page":"1908","DOI":"10.1101\/gr.157891.113","article-title":"Massively parallel synthetic promoter assays reveal the in vivo effects of binding site variants","volume":"23","author":"I Mogno","year":"2013","journal-title":"Genome Res"},{"issue":"1","key":"pcbi.1012276.ref026","doi-asserted-by":"crossref","first-page":"1800298","DOI":"10.1002\/biot.201800298","article-title":"Construction of Synthetic Promoters by Assembling the Sigma Factor Binding \u221235 and \u221210 Boxes","volume":"14","author":"Y Wang","year":"2019","journal-title":"Biotechnol J"},{"issue":"3","key":"pcbi.1012276.ref027","doi-asserted-by":"crossref","first-page":"973","DOI":"10.1534\/genetics.112.143370","article-title":"Why Transcription Factor Binding Sites Are Ten Nucleotides Long","volume":"192","author":"AJ Stewart","year":"2012","journal-title":"Genetics"},{"issue":"9","key":"pcbi.1012276.ref028","doi-asserted-by":"crossref","first-page":"666","DOI":"10.1021\/sb500084f","article-title":"Expanding the Logic of Bacterial Promoters Using Engineered Overlapping Operators for Global Regulators","volume":"3","author":"ME Guazzaroni","year":"2014","journal-title":"ACS Synth Biol"},{"issue":"12","key":"pcbi.1012276.ref029","doi-asserted-by":"crossref","first-page":"1287","DOI":"10.1021\/acssynbio.5b00098","article-title":"Engineering Synthetic cis-Regulatory Elements for Simultaneous Recognition of Three Transcriptional Factors in Bacteria","volume":"4","author":"GR Amores","year":"2015","journal-title":"ACS Synth Biol"},{"key":"pcbi.1012276.ref030","first-page":"614396","article-title":"Modulating Fis and IHF binding specificity, crosstalk and regulatory logic through the engineering of complex promoters [Internet]","author":"LMO Monteiro","year":"2019","journal-title":"bioRxiv"},{"issue":"1","key":"pcbi.1012276.ref031","doi-asserted-by":"crossref","first-page":"2113","DOI":"10.1038\/s41467-020-15977-4","article-title":"Model-driven generation of artificial yeast promoters","volume":"11","author":"BJ Kotopka","year":"2020","journal-title":"Nat Commun"},{"issue":"7","key":"pcbi.1012276.ref032","doi-asserted-by":"crossref","first-page":"803","DOI":"10.1038\/s41587-019-0164-5","article-title":"Human 5\u2032 UTR design and variant effect prediction from a massively parallel translation assay","volume":"37","author":"PJ Sample","year":"2019","journal-title":"Nat Biotechnol"},{"key":"pcbi.1012276.ref033","article-title":"Cell type directed design of synthetic enhancers [Internet]","author":"II Taskiran","year":"2022","journal-title":"bioRxiv"},{"key":"pcbi.1012276.ref034","article-title":"Design of synthetic promoters for cyanobacteria with generative deep-learning model","author":"E Seo","year":"2023","journal-title":"Nucleic Acids Res"},{"key":"pcbi.1012276.ref035","article-title":"Machine-guided design of synthetic cell type-specific cis-regulatory elements [Internet]","author":"SJ Gosai","year":"2023","journal-title":"bioRxiv"},{"key":"pcbi.1012276.ref036","doi-asserted-by":"crossref","first-page":"102941","DOI":"10.1016\/j.copbio.2023.102941","article-title":"Deep learning for optimization of protein expression","volume":"81","author":"EM Nikolados","year":"2023","journal-title":"Curr Opin Biotechnol"},{"key":"pcbi.1012276.ref037","article-title":"Distinguishing word identity and sequence context in DNA language models [Internet","author":"M Sanabria","year":"2023","journal-title":"bioRxiv"},{"issue":"1","key":"pcbi.1012276.ref038","doi-asserted-by":"crossref","first-page":"6309","DOI":"10.1038\/s41467-023-41899-y","article-title":"Deep flanking sequence engineering for efficient promoter design using DeepSEED","volume":"14","author":"P Zhang","year":"2023","journal-title":"Nat Commun"},{"issue":"3","key":"pcbi.1012276.ref039","doi-asserted-by":"crossref","first-page":"btae123","DOI":"10.1093\/bioinformatics\/btae123","article-title":"GPro: generative AI-empowered toolkit for promoter design","volume":"40","author":"H Wang","year":"2024","journal-title":"Bioinformatics"},{"key":"pcbi.1012276.ref040","article-title":"Diffusion-Based Generative Network for de Novo Synthetic Promoter Design.","author":"J Lin","year":"2024","journal-title":"ACS Synth Biol [Internet]"},{"issue":"2","key":"pcbi.1012276.ref041","doi-asserted-by":"crossref","first-page":"196","DOI":"10.1038\/s41587-023-02115-w","article-title":"Generative models for protein structures and sequences","volume":"42","author":"C Hsu","year":"2024","journal-title":"Nat Biotechnol"},{"issue":"7993","key":"pcbi.1012276.ref042","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1038\/s41586-023-06661-w","article-title":"Hold out the genome: a roadmap to solving the cis-regulatory code","volume":"625","author":"CG de Boer","year":"2024","journal-title":"Nature"},{"key":"pcbi.1012276.ref043","volume-title":"Computers and Intractability: a guide to the theory of NP-Completeness","author":"MR Garey","year":"1985"},{"issue":"2","key":"pcbi.1012276.ref044","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1016\/j.ejor.2016.04.059","article-title":"Orienteering Problem: A survey of recent variants, solution approaches and applications","volume":"255","author":"A Gunawan","year":"2016","journal-title":"Eur J Oper Res"},{"key":"pcbi.1012276.ref045","first-page":"233","volume-title":"A Note on the Complexity of the Superstring Problem","author":"D Maier","year":"1977"},{"key":"pcbi.1012276.ref046","unstructured":"Google. OR-Tools, v9.7. 2023; Available from: https:\/\/developers.google.com\/optimization\/"},{"issue":"3","key":"pcbi.1012276.ref047","doi-asserted-by":"crossref","first-page":"307","DOI":"10.1002\/1520-6750(198706)34:3<307::AID-NAV3220340302>3.0.CO;2-D","article-title":"The orienteering problem","volume":"34","author":"BL Golden","year":"1987","journal-title":"Nav Res Logist NRL"},{"issue":"9","key":"pcbi.1012276.ref048","doi-asserted-by":"crossref","first-page":"797","DOI":"10.1057\/jors.1984.162","article-title":"Heuristic Methods Applied to Orienteering","volume":"35","author":"T. Tsiligirides","year":"1984","journal-title":"J Oper Res Soc"},{"key":"pcbi.1012276.ref049","unstructured":"OEIS Foundation Inc. The On-Line Encyclopedia of Integer Sequences. 2023. Entry A000522. Available from: https:\/\/oeis.org\/A000522"},{"issue":"5","key":"pcbi.1012276.ref050","doi-asserted-by":"crossref","first-page":"000833","DOI":"10.1099\/mgen.0.000833","article-title":"RegulonDB 11.0: Comprehensive high-throughput datasets on transcriptional regulation in Escherichia coli K-12","volume":"8","author":"VH Tierrafr\u00eda","year":"2022","journal-title":"Microb Genomics"},{"key":"pcbi.1012276.ref051","unstructured":"Christofides N. Worst-case analysis of a new heuristic for the travelling salesman problem. Graduate School of Industrial Application, Carnegie-Mellon University; 1976 Feb. Report No.: 388."},{"key":"pcbi.1012276.ref052","doi-asserted-by":"crossref","first-page":"118","DOI":"10.1016\/j.hm.2020.04.003","article-title":"A historical note on the 3\/2-approximation algorithm for the metric traveling salesman problem","volume":"53","author":"R van Bevern","year":"2020","journal-title":"Hist Math"},{"key":"pcbi.1012276.ref053","first-page":"76","article-title":"\u041e \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u044d\u043a\u0441\u0442\u0440\u0435\u043c\u0430\u043b\u044c\u043d\u044b\u0445 \u043e\u0431\u0445\u043e\u0434\u0430\u0445 \u0432 \u0433\u0440\u0430\u0444\u0430\u0445","author":"\u0410\u0418 \u0421\u0435\u0440\u0434\u044e\u043a\u043e\u0432","year":"1978","journal-title":"\u0414\u0438\u0441\u043a\u0440\u0435\u0442\u043d\u044b\u0439 \u0410\u043d\u0430\u043b\u0438\u0437 \u0418 \u0418\u0441\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u043d\u0438\u0435 \u041e\u043f\u0435\u0440\u0430\u0446\u0438\u0439"},{"issue":"1","key":"pcbi.1012276.ref054","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0890-5401(89)90044-8","article-title":"Approximation algorithms for the shortest common superstring problem","volume":"83","author":"JS Turner","year":"1989","journal-title":"Inf Comput"},{"key":"pcbi.1012276.ref055","doi-asserted-by":"crossref","unstructured":"Englert M, Matsakis N, Vesel\u00fd P. Improved approximation guarantees for shortest superstrings using cycle classification by overlap to length ratios. In: Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing [Internet]. New York, NY, USA: Association for Computing Machinery; 2022 [cited 2023 Oct 12]. p. 317\u201330. (STOC 2022). Available from: https:\/\/doi.org\/10.1145\/3519935.3520001","DOI":"10.1145\/3519935.3520001"},{"issue":"3","key":"pcbi.1012276.ref056","doi-asserted-by":"crossref","first-page":"481","DOI":"10.1128\/MMBR.00037-08","article-title":"Mechanisms and Evolution of Control Logic in Prokaryotic Transcriptional Regulation","volume":"73","author":"Medema MH van Hijum SAFT","year":"2009","journal-title":"Microbiol Mol Biol Rev MMBR"},{"issue":"4","key":"pcbi.1012276.ref057","doi-asserted-by":"crossref","first-page":"2133","DOI":"10.1093\/nar\/gky010","article-title":"A sigma factor toolbox for orthogonal gene expression in Escherichia coli","volume":"46","author":"I Bervoets","year":"2018","journal-title":"Nucleic Acids Res"},{"issue":"4","key":"pcbi.1012276.ref058","doi-asserted-by":"crossref","first-page":"197","DOI":"10.1016\/j.synbio.2019.10.004","article-title":"Engineering strong and stress-responsive promoters in Bacillus subtilis by interlocking sigma factor binding motifs","volume":"4","author":"Y Wang","year":"2019","journal-title":"Synth Syst Biotechnol"},{"issue":"1\u20132","key":"pcbi.1012276.ref059","first-page":"153","article-title":"The Shortest Common Superstring Problem and Viral Genome Compression","volume":"73","author":"L Ilie","year":"2006","journal-title":"Fundam Informaticae"},{"key":"pcbi.1012276.ref060","volume-title":"Data compression: methods and theory","author":"JA Storer","year":"1987"},{"key":"pcbi.1012276.ref061","first-page":"1","article-title":"C. The continuum of transcription factor affinities","author":"G De Boer","year":"2024","journal-title":"Nat Rev Genet"},{"issue":"2","key":"pcbi.1012276.ref062","doi-asserted-by":"crossref","DOI":"10.1128\/microbiolspec.MGM2-0035-2013","article-title":"Transcription Factor Binding Site Mapping Using ChIP-Seq","volume":"2","author":"S Jaini","year":"2014","journal-title":"Microbiol Spectr"},{"issue":"3","key":"pcbi.1012276.ref063","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1016\/S0968-0004(98)01187-6","article-title":"Specificity, free energy and information content in protein\u2013DNA interactions","volume":"23","author":"GD Stormo","year":"1998","journal-title":"Trends Biochem Sci"},{"issue":"1","key":"pcbi.1012276.ref064","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1186\/gb-2003-5-1-201","article-title":"Computational prediction of transcription-factor binding site locations","volume":"5","author":"ML Bulyk","year":"2003","journal-title":"Genome Biol"},{"key":"pcbi.1012276.ref065","first-page":"624","volume-title":"Approximation Algorithms for NP-Hard Problems","author":"D Hochbaum","year":"1996","edition":"1"},{"key":"pcbi.1012276.ref066","doi-asserted-by":"crossref","unstructured":"Dinur I, Steurer D. Analytical approach to parallel repetition. In: Proceedings of the forty-sixth annual ACM symposium on Theory of computing [Internet]. New York, NY, USA: Association for Computing Machinery; 2014 [cited 2024 Jan 24]. p. 624\u201333. (STOC \u201814). Available from: https:\/\/doi.org\/10.1145\/2591796.2591884","DOI":"10.1145\/2591796.2591884"},{"issue":"4","key":"pcbi.1012276.ref067","doi-asserted-by":"crossref","first-page":"326","DOI":"10.1145\/321043.321046","article-title":"Integer Programming Formulation of Traveling Salesman Problems","volume":"7","author":"CE Miller","year":"1960","journal-title":"J ACM"},{"key":"pcbi.1012276.ref068","article-title":"coin-or\/Cbc: Release releases\/2.10.10 [Internet]","author":"J Forrest","year":"2023","journal-title":"Zenodo"},{"key":"pcbi.1012276.ref069","author":"K Bestuzheva","year":"2023","journal-title":"Global Optimization of Mixed-Integer Nonlinear Programs with SCIP 8"},{"key":"pcbi.1012276.ref070","article-title":"Gurobi Optimizer Reference Manual. [Internet]","author":"LLC Gurobi Optimization","year":"2023"}],"container-title":["PLOS Computational Biology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dx.plos.org\/10.1371\/journal.pcbi.1012276","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,7,24]],"date-time":"2024-07-24T13:52:16Z","timestamp":1721829136000},"score":1,"resource":{"primary":{"URL":"https:\/\/dx.plos.org\/10.1371\/journal.pcbi.1012276"}},"subtitle":[],"editor":[{"given":"Stefan","family":"Klumpp","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"editor"}]}],"short-title":[],"issued":{"date-parts":[[2024,7,24]]},"references-count":70,"journal-issue":{"issue":"7","published-online":{"date-parts":[[2024,7,24]]}},"URL":"https:\/\/doi.org\/10.1371\/journal.pcbi.1012276","relation":{"has-preprint":[{"id-type":"doi","id":"10.1101\/2023.11.01.565124","asserted-by":"object"}]},"ISSN":["1553-7358"],"issn-type":[{"value":"1553-7358","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,7,24]]}}}