Generating information-dense promoter sequences with optimal string packing.

Area of Science:

• Computational Biology
• Synthetic Biology
• Bioinformatics

Background:

• Natural promoter regions contain overlapping transcription factor binding sites that regulate transcription initiation.
• Designing nucleotide sequences with dense, overlapping binding sites is a significant challenge in molecular biology.

Purpose of the Study:

• To address the challenge of designing nucleotide sequences with dense, overlapping binding sites.
• To develop a computational technique for efficiently assembling DNA-protein binding sites into contiguous DNA stretches.

Main Methods:

• The nucleotide String Packing Problem (SPP) was identified as an NP-hard problem.
• The SPP was reduced to an Orienteering Problem with integer distances.
• Modern integer linear programming solvers were utilized to find optimal solutions.

Main Results:

• The method optimally packs 20-100 binding sites into 50-300 base pair DNA arrays within 0.05-10 seconds.
• The approach guarantees provably optimal solutions, outperforming approximation algorithms.
• The method allows control over binding site frequency and can incorporate fixed sequence elements for designing specific elements like bacterial promoters.

Conclusions:

• The presented nucleotide string packing approach accelerates the design of sequences with complex DNA-protein interactions.
• This strategy can aid in interrogating how complex binding site arrangements impact gene expression and biomolecular mechanisms.
• Integration with synthesis and screening can advance understanding of gene regulation and cellular functions.