The core promoter elements are important DNA sequences for the regulation of RNA polymerase II transcription in eukaryotic cells. Despite the broad evolutionary conservation of these elements, there is extensive variation in the nucleotide composition of the actual sequences. In this study, we aim to improve our understanding of the complexity of this sequence variation in the TATA box and initiator core promoter elements inDrosophila melanogaster. Using computational approaches, including an enhanced version of our previously developed MARZ algorithm that utilizes gapped nucleotide matrices, several sequence landscape features are uncovered, including an interdependency between the nucleotides in position 2 and 5 in the initiator. Incorporating this information in an expanded MARZ algorithm improves predictive performance for the identification of the initiator element. Overall our results demonstrate the need to carefully consider detailed sequence composition features in core promoter elements in order to make more robust and accurate bioinformatic predictions.