Protein–DNA recognition: Breaking the combinatorial barrier

We have developed a computational methodology that aims at predicting the binding sites of proteins on DNA. The crucial point of the methodology is to enable the protein binding energies to be calculated for very large numbers of DNA sequences (>1080) in a reasonable amount of computer time. In contrast to an earlier approach, we take into account both DNA and protein flexibility during the calculations. The speed-up comes from dividing the optimization into sub-problems involving overlapping DNA fragments, several nucleotide pairs in length, with associated protein fragments. Each optimization provides energies that can be added together to reconstitute the total binding energy of the protein for any chosen base sequence. We describe this new methodology and carry out some preliminary tests on biologically relevant proteins and protein complexes.