Discovering protein–DNA binding sequence patterns using association rule mining Open Access

Abstract

INTRODUCTION

We first introduce protein–DNA bindings in this section. Existing bioinformatics methods are briefly described, followed by the layout of this article.

Protein–DNA binding

Protein–DNA binding plays a central role in genetic activities such as transcription, packaging, rearrangement, and replication ( 1 , 2 ). Therefor, it is very important to identify and understand the protein–DNA bindings as the basis for further deciphering biological systems. We focus on protein–DNA bindings between transcription factors (TFs) and transcription factor binding sites (TFBSs), which are the primary regulatory activities with abundant data support. TFs bind in a sequence-specific manner to TFBSs to regulate gene transcription (gene expression). The DNA binding domain(s) of a TF can recognize and bind to a collection of similar TFBSs, from which a conserved pattern called motif can be obtained. TFBSs, the nucleotide fragments bound by TFs, are usually short (usually about 5–20 bp) in the cis -regulatory/intergenic regions and can assume very different locations from the transcription start site.

It is expensive and laborious to experimentally identify TF–TFBS binding sequence pairs, for example, using DNA footprinting ( 3 ) or gel electrophoresis ( 4 ). The technology of chromatin immunoprecipitation (ChIP) ( 5 , 6 ) measures the binding of a particular TF to DNA of co-regulated genes on a genome-wide scale in vivo , but at low resolution. Further processing are needed to extract precise TFBSs ( 7 ). TRANSFAC ( 8 ) is one of the largest and most representative databases for regulatory elements including TFs, TFBSs, nucleotide distribution matrices of the TFBSs and regulated genes. The data are expertly annotated and manually curated from peer-reviewed and experimentally proved publications. Other annotation databases of TF families and binding domains are also available [e.g. PROSITE ( 9 ), Pfam ( 10 )]. It is even more difficult and time-consuming to extract high-resolution 3D TF–TFBS complex structures with X-ray crystallography or nuclear magnetic resonance (NMR) spectroscopic analysis. Nevertheless, the high-quality TF–TFBS binding structures provide valuable insights into verifications of putative principles of binding. The Protein Data Bank (PDB) ( 11 ) serves as a representative repository of such experimentally extracted protein–DNA (in particular TF–TFBS) complexes with high resolution at atomic levels. However, the available 3D structures are far from complete. As a result, there is strong motivation to have automatic methods, particularly, computational approaches based on existing abundant data, to provide testable candidates of novel TF domains and/or TFBS motifs with high confidence to guide and accelerate the wet-lab experiments.

Existing methods

The first attempt of computational methods related to TF–TFBS bindings was to discover the motifs of TF domains and TFBSs separately. Moreover, researchers have been trying hard to generalize the one-to-one binding codes from existing 3D structures. Data mining methods have also been proposed with feature transformations and machine learning to decipher complicated binding rules. They are briefly described as follows:

Motif discovery

TF domains and TFBSs sequences are somewhat conserved due to their functional similarity and importance. By exploiting conservation in the sequences, Bioinformatics methods called motif discovery save some of the expensive and laborious laboratory experiments. Motif discovery ( 6 ) can be categorized into two types: (i) motif matching and (ii) de novo motif discovery. (i) Motif matching is to identify putative TF domains ( 9 , 10 ) or TFBSs ( 12 ) based on motif knowledge obtained from annotated data. (ii) de novo motif discovery predicts conserved patterns without knowledge on their appearances, based on certain motif models and scoring functions ( 13 , 14 ) from a set of protein/DNA promoter sequences with similar regulatory functions. While de novo motif discovery is successful for well-conserved TF functional domain motifs, the counterpart for TFBSs remains very challenging with poor performances on real benchmarks ( 6 , 15 , 16 ). A significant limitation of motif discovery is the lack of linkage between the binding counterparts for revealing TF–TFBS relationships.

One-to-one binding codes

Numerous studies have been carried out to analyze existing protein–DNA binding 3D structures comprehensively ( 2 , 17 , 18 ) or with focus on specific families ( 1 ) [e.g. zinc fingers ( 19 )]. Various properties have been discovered concerning, e.g. bonding and force types, TF conservation and mutation ( 1 ), and bending of the DNA ( 17 ). Some are already applicable to predict binding amino acids on the TF side ( 20 ). However, annotated data are far from complete. Alternatively, researchers have sought hard for general binding ‘codes' between proteins and DNA, in particular the one-to-one mapping between amino acids from TFs and nucleotides from TFBSs. Despite many proposed one-one binding propensity mappings ( 1 , 21 , 22 ), it has come to a consensus that there are no simple binding ‘codes' ( 23 ).

Data mining

In the hope of better understanding for protein–DNA bindings, many data mining approaches have also been proposed ( 24 ). Researchers employ and transfer additional detailed information such as base compositions, structures, thermodynamic properties ( 25 , 26 ) as well as expressions ( 27 ), into sophisticated features to fit into certain data mining techniques. Although some approaches may provide interpretable rules, most of them have stringent data requirements which cannot be obtained trivially. Existing data beyond sequences are also insufficient and limited for practitioners. These methods usually extract complicated features rather than working on interpretable data directly. Many data mining techniques, such as neural networks, support vector machines (SVM) ( 28 ) and regressions ( 24 ), may generate rules which are not trivial to interpret. Furthermore, many data mining approaches are based on specific families or particular data sets, where the generality of the results are limited. On the other hand, sequences serve as the most handy primary data that carry important information for protein–DNA bindings ( 23 ). It is desirable to make use of the large-scale and comprehensive sequence data to mine explicit and interpretable TF–TFBS binding rules.

Article layout

In this article, we propose a framework based on association rule mining to discover protein–DNA binding sequence patterns from TRANSFAC. The article layout is as follows: the proposed methods are presented in the next section: ‘Materials and Methods' section; experimental results and verifications are reported in sections ‘Results and Analysis' and ‘Verifications' section, respectively; and finally we have the ‘Discussion' section for the approach.

MATERIALS AND METHODS

In this section, we propose a framework for mining, discovering and verifying TF–TFBS bindings on large-scale databases. The framework starts from data cleansing and transformation on TRANSFAC, and then applies association rule mining to discover TF-TFBS binding sequence patterns. Comprehensive 3D verifications and evaluations are carried out on PDB. Detailed bonding analysis is performed to provide strong support to the discovered rules.

In the following subsections, Apriori algorithm for association rule mining is first introduced. We then elaborate how the algorithm is applied to protein–DNA binding pattern discovery. Finally, we present how the data are preprocessed for the task with a running example.

Association rule mining and Apriori Algorithm

Association rule mining ( 29 ) aims at discovering frequently co-occurring items, called frequent itemsets, from a large number of data samples above a certain count threshold (minimum support) ( 30 ). The support of an itemset is defined as the number of data samples where all the items in the itemset co-occur. In the case of protein–DNA binding, the binding domains of TFs can recognize and form strong bondings with certain sequence-specific patterns of the TFBSs. Therefore, they are likely to co-occur frequently among the combinations between all possible TF and TFBS subsequences, and can be thus identified by association rule mining. In this study, we use the notation of k -mer (a subsequence with k amino acid or nucleotide residues) to represent a candidate item. A frequent TF–TFBS itemset is a TF k -mer and TFBS k -mer (the two k 's can be different) pair, or simply a pair, co-occurring with a frequency no less than the minimum support in the TF–TFBS sequence records (TRANSFAC database).

Apriori algorithm proposed by Agrawal et al. ( 29 ) is a classical approach to find out frequent itemsets. It is outlined in Algorithm 1 in the  Appendix 1 . It is a branch and bound algorithm for discovering association rules in a database. With its downward closure property, an optimal performance is guaranteed. The algorithm first obtains frequent 1-itemsets. Iteratively, it uses the frequent n -itemsets (itemsets with n items) to generate all possible candidate ( n +1)-itemsets. They are then evaluated for their supports ( 30 ). If the support of an ( n +1)-itemset is lower than a threshold, the ( n +1)-itemset is removed. After the removal, the resultant ( n +1)-itemsets are the frequent ( n +1)-itemsets. The above procedure is repeated until an empty set is found.

Discovering associated TF–TFBS sequence patterns

To formulate the TF–TFBS sequence pattern discovery problem into association rule mining, we have to transform the protein–DNA binding records into the formats of itemsets ( k -mers). An illustrative example for the TF–TFBS binding records from TRANSFAC 2008.3 is shown in Figure 1 . The TF (e.g. T01333 RXR-γ) can bind to several TFBS DNA sequences. The DNA sequences may be different in lengths due to experimental methods and noises. Both the TF and TFBS sequences are chopped into overlapping short k -mers, as illustrated in Figure 2 (first part). They together with the corresponding reverse complements (e.g. GACCT and reverse complement: AGGTC) form one data sample. To generate the itemsets, all the k -mers are recorded in a binary array where appearing k -mers are marked 1; and 0 otherwise. Thus, the length of the array depends on the number of all possible TF k -mers and TFBS k -mers ( Figure 2 , second part). Since k is usually short ( 4–6 ), all the possible 4 ^k combinations of TFBS DNA k -mers can be adopted. However, it is computationally infeasible to obtain all the possible 20 ^k combinations of TF k -mers. Thus a data-driven approach is employed by scanning the whole TRANSFAC to obtain frequent TF amino acid k -mers.

Figure 1.

TFBS sequences of a TF (TRANSFAC 2008.3 ID: T01333).

Open in new tabDownload slide

Figure 2.

Flowchart of the proposed framework to discover association rules from TRANSFAC.

Open in new tabDownload slide

Since there are multiple TFBSs for each TF (e.g. Figure 1 ), a question arises: how to define the ‘commonly found' TFBS k -mers of a TF? Without loss of generality, the majority rule ( 31 ) is applied. If the majority of a TF's TFBS sequences contains a certain DNA residue k -mer, then the k -mer is considered ‘commonly found'. We set the majority to be 50% for TFBS k -mers. We only count the number of TFBS sequences in which a certain k-mer appears, in order not to be biased by multiple occurrences of the k -mer appearing in only a few TFBS sequences. Figure 1 illustrates an example where there are five TFBS sequences. The TFBS DNA k -mer AGGTC (or its reverse complement: GACCT) can be found in three of the TFBS sequences. The k -mer appears in 60% (3/5) of the TFBS sequences of the TF, and thus is considered ‘commonly found'. On the other hand, GTTCA is not considered ‘commonly found' because it only appears in 2 (40%) out of the 5 TFBS sequences of the TF.

After all valid TF data samples are transformed into itemsets, Apriori algorithm is applied to generate frequent TF–TFBS k -mer sequence patterns (the links in Figure 2 , second part). The special feature in this study is that the co-occurring pairs should contain both TF and TFBS k -mer items, as illustrated in the third part of Figure 2 . In the current study, we only consider one TF k -mer with one TFBS k -mer in the frequent itemsets, but it is straightforward to generalize it to be multiple TF and TFBS k -mers in principle. The huge computational intensity for the generalization, when applied on the large TRANSFAC database, prevents us from doing so at this time. Finally, the association rules are computed based on the confidence measurements for the frequent itemsets, which are defined as follows:

where conf( k -mer _DNA ⇒ k -mer _AA ) is called forward confidence, conf( k -mer _DNA ⇐ k -mer _AA ) is called backward confidence and support( X ) is the support of itemset X . For each association rule, its forward confidence measures the posterior probability that the corresponding amino acid k -mer can be found in a TF's sequence if the DNA k -mer is commonly found in the TF's TFBS sequences. Its backward confidence measures the posterior probability that the corresponding DNA k -mer can be commonly found in a TF's TFBS sequences if the amino acid k -mer is found in the TF's sequence. The minimum of them is taken as confidence in this article. The higher the confidence, the better the association rule is ( Figure 2 , fourth part). The whole proposed approach is summarized in Figure 2 .

Data preparation

To apply the methodology on TRANSFAC, TF and TFBS data were downloaded and extracted from the flat files of TRANSFAC 2008.3 [a free public (older) version is also available ( http://www.gene-regulation.com/pub/database.html )]. The entries without sequence data were discarded. Since a TF can bind to one or more TFBSs, TFBS data were grouped by TF. TFBS sequences were extracted for each TF to form a TF data set—a TF sequence and the corresponding TFBS sequences—and finally to be transformed into itemsets. To avoid sampling error, TF data sets with less than five TFBS sequences were discarded. Furthermore, the redundancy of TF sequences was removed by BLASTClust using 90% TF sequence identity ( 32 ). Only one TF data set was selected for each cluster. Note that we only used sequence data in TRANSFAC. None of the prior information (e.g. the binding domains of TFs) other than sequences was used. Importantly, it turns out that the results of the proposed approach can be verified by annotations, 3D structures from PDB and even homology modeling as described in the subsequent sections.

After data preparation, the 631 TF data sets (listed in Table 5 in the  Appendix 1 ) were selected. The minimum support ( 30 ) was set to seven TF data sets to avoid sampling error. For the values of k , we try 4–6 for both TF k -mers and TFBS k -mers, resulting in 9 (3 × 3) different combinations. In particular, 256 DNA 4-mers, 1024 DNA 5-mers and 4096 DNA 6-mers were adopted for TFBS, whereas 99 621 amino acid 4-mers, 82 561 amino acid 5-mers, and 39 320 amino acid 6-mers were adopted for TF, as the frequent 1-itemsets.

Apriori algorithm was then applied to discover frequently co-occurring TF–TFBS k -mer pairs (2-itemsets). Finally, the resultant pairs were rescanned in TRANSFAC to measure their forward and backward confidences ( 33 ).

RESULTS AND ANALYSIS

In this section, the discovered rules are reported, followed by analysis with different measurements.

Rules discovered

Varying k from 4 to 6 for both TF k -mers and TFBS k -mers, we have obtained nine sets of associated pairs. For each set of pairs, the forward and backward confidences of each pair were calculated. Then, the pairs in the same set were sorted by the minima of their forward and backward confidences in descending order. The nine sets of rules (pairs) exhibit a similar trend that the number of rules decreases as the association criterion becomes more stringent (with higher confidence levels). The TFBS 5-mers settings in general show the most available rules when the confidence level is high (≥0.5), indicating more conserved and significant results. Therefore, we focus on them and use TFBS 5-mer–TF 5-mer as the representative example throughout the article. The results for all other settings are available in the Supplementary Data .

The number of rules (pairs) discovered is summarized in Table 1 . For instance, there are 70 TF 5-mer–TFBS 5-mer pairs without any further removal (in the N column) with both forward and backward confidences ≥0.5. Considering direct and reverse complement TFBS DNA k -mers as equivalent, we further removed the duplicated pairs (e.g. leaving AGGTC–CEGCK and removing GACCT–CEGCK because AGGTC and GACCT are reverse complements). The results are shown in the N ′ column in Table 1 . For instance, the 70 TF 5-mer–TFBS 5-mer pairs were reduced to 35 at a confidence level of 0.5. Furthermore, we found that most pairs could be merged together to form a longer pair. For instance, GGTCA–SGYHY and GGTCA–GYHYG could be merged to form a pair GGTCA–SGYHYG. Thus the pairs have been merged and the rule numbers are shown in the N_m column in Table 1 . For instance, 35 TF 5-mer–TFBS 5-mer pairs are merged to form 11 merged pairs when the confidence level is equal to 0.5.

Table 1.

Open in new tab

Number of the TFBS 5-mer–TF 5-mer pairs across different confidence levels

Confidence .	.	.	.	.
0.0	262	131	29	9.88 ± 3.68
0.1	262	131	29	9.88 ± 3.68
0.2	240	120	24	10.14 ± 3.73
0.3	180	90	23	10.63 ± 4.11
0.4	126	63	21	11.40 ± 4.59
0.5	70	35	11	13.63 ± 5.05
0.6	24	12	8	15.08 ± 5.28
0.7	6	3	2	10.33 ± 2.36
0.8	0	0	0	N/A
0.9	0	0	0	N/A
1.0	0	0	0	N/A

Confidence .	.	.	.	.
0.0	262	131	29	9.88 ± 3.68
0.1	262	131	29	9.88 ± 3.68
0.2	240	120	24	10.14 ± 3.73
0.3	180	90	23	10.63 ± 4.11
0.4	126	63	21	11.40 ± 4.59
0.5	70	35	11	13.63 ± 5.05
0.6	24	12	8	15.08 ± 5.28
0.7	6	3	2	10.33 ± 2.36
0.8	0	0	0	N/A
0.9	0	0	0	N/A
1.0	0	0	0	N/A

N , number of pairs, N , number of pairs (duplicated pairs removed); , number of merged pairs; S , mean and SD of the support of the pairs in .)

Table 1.

Open in new tab

Number of the TFBS 5-mer–TF 5-mer pairs across different confidence levels

Confidence .	.	.	.	.
0.0	262	131	29	9.88 ± 3.68
0.1	262	131	29	9.88 ± 3.68
0.2	240	120	24	10.14 ± 3.73
0.3	180	90	23	10.63 ± 4.11
0.4	126	63	21	11.40 ± 4.59
0.5	70	35	11	13.63 ± 5.05
0.6	24	12	8	15.08 ± 5.28
0.7	6	3	2	10.33 ± 2.36
0.8	0	0	0	N/A
0.9	0	0	0	N/A
1.0	0	0	0	N/A

Confidence .	.	.	.	.
0.0	262	131	29	9.88 ± 3.68
0.1	262	131	29	9.88 ± 3.68
0.2	240	120	24	10.14 ± 3.73
0.3	180	90	23	10.63 ± 4.11
0.4	126	63	21	11.40 ± 4.59
0.5	70	35	11	13.63 ± 5.05
0.6	24	12	8	15.08 ± 5.28
0.7	6	3	2	10.33 ± 2.36
0.8	0	0	0	N/A
0.9	0	0	0	N/A
1.0	0	0	0	N/A

N , number of pairs, N , number of pairs (duplicated pairs removed); , number of merged pairs; S , mean and SD of the support of the pairs in .)

Quantitative analysis

To evaluate the number of TF data sets supporting each pair (support), the support for each pair was counted. In general, more supports are found when the confidence level is increased. For instance, the average support of the TFBS 5-mer–TF 5-mer pairs is generally increased when the confidence level is increased in the S column of Table 1 . The overall results are summarized in Supplementary Table S4 .

Support is considered the degree of co-occurrence between a TF amino acid k -mer and a TFBS DNA k -mer. Forward and backward confidences consider the cases when either one of them is absent. Some may have questions about the remaining case. How about the case when both of them are absent? To take the case into account, ϕ-coefficients ( 35 ) were measured for each pair, as shown in the ϕ column in Table 2 . The overall results are summarized in Supplementary Table S5 . Most values are >0.4, indicating that positive correlations exist among pairs.

Table 2.

Open in new tab

Quantitative measurements for the TFBS 5-mer–TF 5-mer pairs across different confidence levels

Confidence .	.	L .	FC .	BC .
0.0	0.49 ± 0.11	17.92 ± 7.34	1.89 ± 0.67	3.50 ± 2.29
0.1	0.49 ± 0.11	17.92 ± 7.34	1.89 ± 0.67	3.50 ± 2.29
0.2	0.51 ± 0.11	18.32 ± 7.46	1.94 ± 0.68	3.51 ± 2.30
0.3	0.54 ± 0.10	19.81 ± 7.79	2.02 ± 0.64	3.46 ± 2.31
0.4	0.58 ± 0.09	21.41 ± 8.53	2.23 ± 0.66	3.61 ± 2.40
0.5	0.64 ± 0.07	22.57 ± 10.46	2.49 ± 0.70	4.35 ± 2.65
0.6	0.71 ± 0.06	25.80 ± 13.76	3.33 ± 0.57	4.21 ± 2.55
0.7	0.79 ± 0.03	42.07 ± 14.87	3.70 ± 0.29	4.87 ± 0.00
0.8	N/A	N/A	N/A	N/A
0.9	N/A	N/A	N/A	N/A
1.0	N/A	N/A	N/A	N/A

Confidence .	.	L .	FC .	BC .
0.0	0.49 ± 0.11	17.92 ± 7.34	1.89 ± 0.67	3.50 ± 2.29
0.1	0.49 ± 0.11	17.92 ± 7.34	1.89 ± 0.67	3.50 ± 2.29
0.2	0.51 ± 0.11	18.32 ± 7.46	1.94 ± 0.68	3.51 ± 2.30
0.3	0.54 ± 0.10	19.81 ± 7.79	2.02 ± 0.64	3.46 ± 2.31
0.4	0.58 ± 0.09	21.41 ± 8.53	2.23 ± 0.66	3.61 ± 2.40
0.5	0.64 ± 0.07	22.57 ± 10.46	2.49 ± 0.70	4.35 ± 2.65
0.6	0.71 ± 0.06	25.80 ± 13.76	3.33 ± 0.57	4.21 ± 2.55
0.7	0.79 ± 0.03	42.07 ± 14.87	3.70 ± 0.29	4.87 ± 0.00
0.8	N/A	N/A	N/A	N/A
0.9	N/A	N/A	N/A	N/A
1.0	N/A	N/A	N/A	N/A

ϕ, mean and SD of ϕ-coefficient; L, mean and SD of lift; FC, mean and SD of forward conviction; BC, mean and SD of backward conviction.

Table 2.

Open in new tab

Quantitative measurements for the TFBS 5-mer–TF 5-mer pairs across different confidence levels

Confidence .	.	L .	FC .	BC .
0.0	0.49 ± 0.11	17.92 ± 7.34	1.89 ± 0.67	3.50 ± 2.29
0.1	0.49 ± 0.11	17.92 ± 7.34	1.89 ± 0.67	3.50 ± 2.29
0.2	0.51 ± 0.11	18.32 ± 7.46	1.94 ± 0.68	3.51 ± 2.30
0.3	0.54 ± 0.10	19.81 ± 7.79	2.02 ± 0.64	3.46 ± 2.31
0.4	0.58 ± 0.09	21.41 ± 8.53	2.23 ± 0.66	3.61 ± 2.40
0.5	0.64 ± 0.07	22.57 ± 10.46	2.49 ± 0.70	4.35 ± 2.65
0.6	0.71 ± 0.06	25.80 ± 13.76	3.33 ± 0.57	4.21 ± 2.55
0.7	0.79 ± 0.03	42.07 ± 14.87	3.70 ± 0.29	4.87 ± 0.00
0.8	N/A	N/A	N/A	N/A
0.9	N/A	N/A	N/A	N/A
1.0	N/A	N/A	N/A	N/A

Confidence .	.	L .	FC .	BC .
0.0	0.49 ± 0.11	17.92 ± 7.34	1.89 ± 0.67	3.50 ± 2.29
0.1	0.49 ± 0.11	17.92 ± 7.34	1.89 ± 0.67	3.50 ± 2.29
0.2	0.51 ± 0.11	18.32 ± 7.46	1.94 ± 0.68	3.51 ± 2.30
0.3	0.54 ± 0.10	19.81 ± 7.79	2.02 ± 0.64	3.46 ± 2.31
0.4	0.58 ± 0.09	21.41 ± 8.53	2.23 ± 0.66	3.61 ± 2.40
0.5	0.64 ± 0.07	22.57 ± 10.46	2.49 ± 0.70	4.35 ± 2.65
0.6	0.71 ± 0.06	25.80 ± 13.76	3.33 ± 0.57	4.21 ± 2.55
0.7	0.79 ± 0.03	42.07 ± 14.87	3.70 ± 0.29	4.87 ± 0.00
0.8	N/A	N/A	N/A	N/A
0.9	N/A	N/A	N/A	N/A
1.0	N/A	N/A	N/A	N/A

ϕ, mean and SD of ϕ-coefficient; L, mean and SD of lift; FC, mean and SD of forward conviction; BC, mean and SD of backward conviction.

Consider the following scenario: if a TFBS DNA k -mer and a TF amino acid k -mer are both frequently found in the data sets, it will be very likely that they co-occur frequently merely by chance. To tackle such scenario, forward and backward confidences do play their important roles in pruning them. But for clarity, lift ( 36 ) that estimates the ratio of the actual support to the expected support was measured for each pair, where the expected support was calculated from the random model that the TFBS DNA k -mer is independent of the TF amino acid k -mer for each pair. For instance, the average lift for the TFBS 5-mer–TF 5-mer pairs is shown in the L column in Table 2 . The overall results are summarized in Supplementary Table S6 . Most values of the lift are >5. Thus the DNA residue k -mer and the amino acid residue k -mer of most pairs co-occur at least five times more frequently than the prediction based on the independent assumption made by the lift measurement.

To estimate the validity of the pairs, both forward and backward convictions (the same directions as the forward and backward confidences, respectively) ( 36 ) were measured for each pair. The measurements were averaged for each set of pairs. For instance, the average forward and backward convictions for the TFBS 5-mer–TF 5-mer pairs is shown in the FC and BC columns in Table 2 . The overall results are summarized in Supplementary Tables S7 and S8 . Most values are >1. The pairs commit fewer errors than the prediction based on the statistically independent assumption made by the measurements: forward and backward convictions. In other words, the pairs would have committed more errors if the association between its TFBS k -mer and TF k -mer had happened purely by chance.

Annotation analysis

If the pairs in our results are the actual binding cores between TFs and TFBSs, most of their TF amino acid k -mers should be inside DNA binding domains. Thus, the TF amino acid k -mers were scanned in TRANSFAC to check whether they were within the annotated DNA binding domains. As stated in the previous section, the set of TFBS 4-mer–TF 4-mer pairs constitutes all the pairs in the other sets by the downward closure property. Thus only the TF amino acid 4-mers of the set of TFBS 4-mer–TF 4-mer pairs were needed for the checking: of the 792 TF amino acid 4-mers, of them were found within the DNA binding domains listed in the ‘PFAM 18’ list downloaded from DBD ( 37 ) on 25 January 2010.

Empirical analysis

Since the numbers of results are quite large, they are tabulated in a statistical perspective in the previous sections. This section provides readers with empirical insights into the results obtained. Comparing with the other sets, the set of TFBS 5-mer–TF 5-mer pairs shows its relative invariability to confidence level pruning. Thus, it motivates us to have an in-depth empirical analysis on them. They are listed in Table 3 .

Among the 131 pairs in Table 3 , the TFBS DNA k -mers are quite conserved. There are only 15 distinct TFBS DNA k -mers. Each TFBS DNA k -mer forms pairs with 8.73 TF amino acid k -mers on average. One of the reasons may be the specificity of DNA residue, is lower in view of its alphabet size ( 4 ) as compared to the amino acid alphabet size ( 20 ).

To act as a DNA binding protein, a TF needs to provide a basic interacting surface for the recognition of major/minor grooves as well as the phosphate backbone of DNA. Therefore, we searched through the set of pairs in Table 3 to count the occurring frequency for each residue. Interestingly, we found that the basic residues, lysine (50 times) and arginine (131 times), occur at the highest frequency among 131 pairs of TFBS–TF. On the other hand, the hydrophobic residues ( 38 ) such as isoleucine ( 15 ) and valine ( 13 ) occur at the lowest frequency. These results suggest the potential of the TF sequences for being the binding sequences between TFs and TFBSs. On the other hand, as the nucleotides of TFBSs are somehow negatively charged, it can be deduced that their binding amino acid residues of TFs should be positively charged. Thus the occurring frequencies were further examined. Among the 131 pairs, the positively charged residues: arginine (R) and lysine (K) occur 131 and 50 times, respectively. In contrast, the negatively charged residues aspartic acid (D) and glutamic acid (E) occur 8 and 30 times, respectively. Such discrepancy supports their potential for being the binding sequences between TFs and TFBSs.

Experimental analysis

This section follows the same approach in empirical analysis. The set of TFBS 5-mer–TF5mer pairs in Table 3 is selected for experimental analysis. Out of the 131 pairs, 5 of them were selected and analyzed. The first pair is GGTCA–CEGCK, which have been experimentally proved as binding sequences in Ref. ( 39 ). The TF amino acid k -mer (CEGCK) is considered part of P-box (CEGCKG) within the DNA binding domain of Bp-nhr-2, which is believed to bind the DNA k -mer (GGTCA). The second pair is AAACA–IRHNL mentioned in Ref. ( 40 ). Based on the corresponding PDB entry 3CO6, it is believed that the pair was the binding pair between a TF and a TFBS as shown in Figure 3 . Similarly, the remaining pairs are GATAA–NACGL, GGTCA–GFFRR and CTTCC–LRYYY. They are found as binding pairs in PDB entries 3DFV ( 41 ), 3DZY ( 42 ) and 2NNY ( 43 ) as shown in Figure 3 a, b and c, respectively. The above five pairs reveal that the pairs generated from the proposed approach have biological evidences in literatures. Among the previous figures, two of them (3CO6 and 2NNY) were further analyzed in terms of hydrogen bonding, which also means the specificity of the interaction between amino acids and the bases, as shown in Figure 4 a and b. We have also highlighted the hydrogen bonds as black lines as well as the residues that make contact with the base (only predicted residues), which are the evidence of the significance and accuracy of the prediction of the TF–TFBS pairs. Nevertheless, as the proposed approach is applied on a large-scale database, such extensive and detailed analysis of all the binding core pairs discovered are not practical. Therefore, a scalable verification approach will be presented in the next section to verify the massive results generated.

Figure 3.

Four representative TF–TFBS pairs are shown in ribbon diagram. ( a ) AAACA–IRHNL pair in 3C06, ( b ) GATAA–NACGL pair in 3DFV, ( c ) GGTCA–GFFRR pair in 3DZY and ( d ) CTTCC–LRYYY pair in 2NNY are shown. The TF amino acids and TFBS nucleotides are highlighted in ball and stick format. The sequences of the TF–TFBS pairs are also labeled in the figures. The figures are generated using Protein Workshop ( 34 ).

Open in new tabDownload slide

Figure 4.

The interactions between the TF and TFBS of two representative pairs ( a ) AAACA–IRHNL in 3CO6 and ( b ) CTTCC–LRYYY in 2NNY are shown. The proteins are shown in ribbon diagram with the highlighted TF amino acids in ball and stick format. The helices and strands are colored in red and cyan, respectively. The amino acids that interact with the nucleotides are labeled. The hydrogen bonds are shown in dark line. The figures are generated using DS visualizer, Accelrys.

Open in new tabDownload slide

VERIFICATIONS

In this section, we try to verify the discovered pairs with external data sources, in particular the 3D protein-DNA complex structures experimentally determined from PDB. Homology modeling has also been done for further verifications.

Verification by PDB

In this article, PDB is selected for providing 3D protein–DNA complex data for 3D structural verification. The PDB data were downloaded from RCSB PDB ( http://www.pdb.org ) from 16 September 2009 to 22 September 2009, where the protein–DNA complexes were selected based on the entry-type list provided in ftp://ftp.wwpdb.org/ .

For each set of pairs in Supplementary Table S2 , each pair is independently evaluated as shown in Figure 5 . For each pair, its TF k -mer is used to query which PDB chain has the TF k -mer. Once the corresponding set of PDB chains has been identified and returned, its redundancy is removed by BLASTClust using 90% sequence identity ( 32 ). The removal is to ensure that redundant PDB chains are not double counted. After the removal, the pair is evaluated for binding in the 3D space:

• A TFBS k -mer–TF k -mer pair is considered binding for a PDB chain if and only if an atom of the TFBS k -mer and an atom of the TF k -mer are close to each other. Two atoms are considered close if and only if their distance is <3.5 Å ( 25 , 28 ).

With the pair evaluated in its PDB chains, its PDB chains can be classified into the following three categories:

• PDB chains only having the TF k -mer ( a )

• PDB chains having both TF k -mer and TFBS k -mer

  • The pair binds together ( b )

  • The pair does not bind together ( c )

Thus the number of chains in each category is counted and converted into the following performance metrics:

• TFBS prediction score=( b + c )/( a + b + c )

• TFBS binding prediction score = b /( a + b + c )

• Binding prediction score= b /( b + c )

Given the resultant PDB chains queried by a TF k -mer, TFBS prediction score measures the proportion of PDB chains that contain the corresponding TFBS k -mer. In other words, it measures the backward confidence of a pair in PDB. TFBS binding prediction score is a more stringent metric. It measures the proportion of PDB chains that have the corresponding TFBS k -mer binding with the queried TF k -mer. Lastly, binding prediction score is the most important metric. It measures the proportion of PDB chains in which the pair is really binding. To verify the cases when ( b + c ) = 0 (i.e. the pairs do not appear in PDB), homology modeling is also performed.

Figure 5.

Flowchart of 3D verification for each set of pairs.

Open in new tabDownload slide

For each setting, we have a set of pairs. For each pair, the above performance metrics are calculated. The overall results are averaged and summarized in Supplementary Tables S9–S11 . For each setting, we also have a set of merged pairs. For each merged pair, the above performance metrics are also calculated. The overall results are averaged and summarized in Supplementary Tables S12–S14 . Note that the most conservative calculation has been used for each performance metric for each pair. If a performance metric of a pair does not have enough PDB data for calculation, a value of zero will be given to the performance metric of the pair. For instance, the cases when ( b + c ) = 0 or ( a + b + c ) = 0. Despite the above setting, the performance metrics of the pairs still have reasonable performances. They are shown to be significantly better than the maximal performance of 50 random runs in a later section.

Nevertheless, although the above metrics can capture the performance of a pair quantitatively, the most important point is to know how many generated pairs could be verified [with at least one binding evidence in PDB data ( b > 0)]. To gain more insights, the number of pairs with at least one related PDB chain [( b + c ) > 0] are tabulated in Supplementary Tables S15 and S16 . Correspondingly, the percentage of verified pairs ((Number of pairs with b > 0/Number of pairs with ( b + c ) > 0)) are calculated and tabulated in Supplementary Tables S17 and S18 . In the tables, the percentage of verified pairs is high enough to justify that the proposed approach has produced pairs proven to be binding in PDB. For instance, the statistics for the TFBS 5-mer–TF 5-mer pairs is extracted in Table 4 and Figure 6 . Among the 80 TFBS 5-mer–TF 5-mer pairs with at least one related PDB chain [( b + c ) > 0] when the confidence level = 0.0, more than 81% of them have at least one binding evidence ( b > 0).

Table 4.

Open in new tab

Number of the TFBS 5-mer–TF 5-mer pairs verified across different confidence levels

Confidence .	.	.	.	.
0.0	80	65	19	16
0.1	80	65	19	16
0.2	71	59	15	13
0.3	50	44	15	13
0.4	32	28	12	11
0.5	19	17	7	6
0.6	9	9	5	5
0.7	2	2	1	1
0.8	0	0	0	0
0.9	0	0	0	0
1.0	0	0	0	0

Confidence .	.	.	.	.
0.0	80	65	19	16
0.1	80	65	19	16
0.2	71	59	15	13
0.3	50	44	15	13
0.4	32	28	12	11
0.5	19	17	7	6
0.6	9	9	5	5
0.7	2	2	1	1
0.8	0	0	0	0
0.9	0	0	0	0
1.0	0	0	0	0

, number of the TFBS 5-mer–TF 5-mer pairs with at least one related PDB chain [ ]; , number of the TFBS 5-mer–TF 5-mer pairs with at least one PDB chain as a binding evidence [ ]; , number of the TFBS 5-mer–TF 5-mer merged pairs with at least one related PDB chain [ ]; , number of the TFBS 5-mer–TF 5-mer merged pairs with at least one PDB chain as a binding evidence [ )].

Table 4.

Open in new tab

Number of the TFBS 5-mer–TF 5-mer pairs verified across different confidence levels

Confidence .	.	.	.	.
0.0	80	65	19	16
0.1	80	65	19	16
0.2	71	59	15	13
0.3	50	44	15	13
0.4	32	28	12	11
0.5	19	17	7	6
0.6	9	9	5	5
0.7	2	2	1	1
0.8	0	0	0	0
0.9	0	0	0	0
1.0	0	0	0	0

Confidence .	.	.	.	.
0.0	80	65	19	16
0.1	80	65	19	16
0.2	71	59	15	13
0.3	50	44	15	13
0.4	32	28	12	11
0.5	19	17	7	6
0.6	9	9	5	5
0.7	2	2	1	1
0.8	0	0	0	0
0.9	0	0	0	0
1.0	0	0	0	0

, number of the TFBS 5-mer–TF 5-mer pairs with at least one related PDB chain [ ]; , number of the TFBS 5-mer–TF 5-mer pairs with at least one PDB chain as a binding evidence [ ]; , number of the TFBS 5-mer–TF 5-mer merged pairs with at least one related PDB chain [ ]; , number of the TFBS 5-mer–TF 5-mer merged pairs with at least one PDB chain as a binding evidence [ )].

Figure 6.

Percentage of the TFBS 5-mer–TF 5-mer pairs verified across different confidence levels.

Open in new tabDownload slide