EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Generating information-dense promoter sequences with optimal string packing

Virgile Andreani iD, Eric J South iD, Mary J Dunlop iD

PLOS Computational Biology · 2024

DOI: 10.1371/journal.pcbi.1012276 ↗

Kurz gefasst

Fachartikel in der Zeitschrift PLOS Computational Biology, 2024. Verfasst von Virgile Andreani und 2 weiteren Autor:innen. Beteiligte Einrichtung: Biomedical Engineering Department, Boston University, Boston, Massachusetts, United States of America. Hauptthemen laut MEDLINE: Promoter Regions, Genetic, Computational Biology, Algorithms. Die Arbeit nennt 70 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: NIGMS NIH HHS, NSF, NIH.

AbstractSchlagwörterBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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–100 binding sites into dense nucleotide arrays of 50–300 base pairs in 0.05–10 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.

Schlagwörter

MeSH-Schlagwörter (MEDLINE)

Promoter Regions, GeneticComputational BiologyAlgorithmsBinding SitesDNATranscription FactorsSequence Analysis, DNABase SequenceProtein Binding

Substanzen

DNATranscription Factors

Autor:innen und Institutionen

  • Biomedical Engineering Department, Boston University, Boston, Massachusetts, United States of America.
  • Biological Design Center, Boston University, Boston, Massachusetts, United States of America.
  • Molecular Biology, Cell Biology & Biochemistry Program, Boston University, Boston, Massachusetts, United States of America.

ORCID-Profile: Virgile Andreani, Eric J South, Mary J Dunlop

Förderung

  • NIGMS NIH HHS
  • NSF
  • NIH

Zitieren

APA

Andreani, V., South, E. J., & Dunlop, M. J. (2024). Generating information-dense promoter sequences with optimal string packing. PLOS Computational Biology. https://doi.org/10.1371/journal.pcbi.1012276

Vancouver

Andreani V, South EJ, Dunlop MJ. Generating information-dense promoter sequences with optimal string packing. PLOS Computational Biology. 2024. doi:10.1371/journal.pcbi.1012276

BibTeX
@article{Andreani2024,
  author = {Andreani, Virgile and South, Eric J and Dunlop, Mary J},
  title = {Generating information-dense promoter sequences with optimal string packing},
  journal = {PLOS Computational Biology},
  year = {2024},
  doi = {10.1371/journal.pcbi.1012276}
}
Kostenlos starten →