MAPPER: a search engine for the computational identification of putative transcription factor binding sites in multiple genomes

The computational identification of Transcription Factor Binding Sites (TFBSs) in DNA sequences normally relies on the application of pattern matching methods to the nucleotide sequence data. If enough examples of experimentally validated binding sites for a given transcription factor can be found, their sequences can be aligned in order to generate a consensus sequence. The consensus sequence can be represented either deterministically or probabilistically in different ways, and according to the representation chosen, different algorithms are available to detect new instances of a binding site in a sequence of interest. Traditionally, the most used pattern matching method for this purpose is based on Nucleotide Weight Matrices (NWMs), that describe the probability of each one of the four DNA bases at each position in the consensus. The most important source of NWM data is TRANSFAC^®, a curated database containing information on over one thousand transcription factors from multiple organisms. In addition, JASPAR is a curated database that contains high quality NWMs for several transcription factors.

Our method uses Hidden Markov Models (HMMs) to detect TFBSs in genomic sequences. As described in our paper, we used binding site sequence information from TRANSFAC and JASPAR to train 1,079 HMMs corresponding to 888 transcription factor entries in the databases that have a distinct name. Table 1 lists the 888 distinct transcription factor entries considered in this study and the models that describe them.

HMMs posses high descriptive and predictive power and may, therefore, be able to detect TFBSs with higher accuracy and, most importantly, with a smaller number of false positives. In order to validate this hypothesis we compared the performance of our method (based on HMMER) against other publicly available programs for TFBS detection, by measuring their ability to detect "true" binding sites and to limit the number of false positives returned. We performed both a limited evaluation on experimentally validated binding sites for a small number of transcription factors, and a large-scale validation using synthetic data. In the following sections we describe in detail the procedure we used and we present the results of our evaluation.

The search engine for the computational identification of putative transcription factor binding sites in multiple genomes using our methodology is accessible through MAPPER.

We tested our method on 17 binding sites for three transcription factors (p53, Su(H), MEF-2) in 9 control sequences. The results of this analysis are available here.

We then compared the performance of our method in detecting experimentally validated TFBS against that of four other publicly available programs: Match, Patser, LMM and ScanACE. The input dataset consists of 89 sequences each of which contains exactly one binding site for one of the following TFs: E2F, ER, GR, HNF1, HNF3, HNF4. For each method, we evaluated the percentage of true positives returned (i.e., the percentage of the true sites that were actually detected) and the percentage of false positives (defined as those hits that do not match a true binding site but have a score higher than the worst-scoring true positive). The detailed results are available in this file, while the following table describes the comparative performance of the different methods tested.

TP = percentage of true hits detected; min FP = smallest false positive percentage across the six TFs; max FP = largest false positive percentage across the six TFs; M = using model based on TRANSFAC matrix; T = using factor-derived model.

For the simulations described here we considered the 491 models for which both a TRANSFAC NWM and a HMMER model were available, and the two were generated on exactly the same training data (i.e., the HMM was trained on the same alignment used to generate the NWM). The test was performed independently for each model, and consisted in repeating the following procedure 20 times:

1. We generated a random sequence of 50,000 bp, and we inserted 100 non-overlapping "synthetic" binding sites into it, at random locations. The synthetic binding sites were generated from the same alignment used to generate the HMMER and NWM binding site models through an ad-hoc algorithm designed to make the test as fair as possible for the two methods (see the Methods section of the paper for details). Before a site was inserted the sequence was scanned to eliminate other random occurrences of the same site.
2. We ran HMMER and Match on the sequence, collecting the list of predicted TFBSs (referred to below as "hits") produced by both methods. We used a threshold of 0.7 for both the core and whole-matrix similarity score in Match.
3. We marked heach hit as a true or false positive according to whether its position coincided with one of the 100 planted sites.

At the end of the 20 runs, we generated numerical scores comparing the performance of the two methods in detecting binding sites using the model under consideration. In both methods, hits are returned if their score (used to describe the goodness of their match to the model) is above a set threshold, but the scores used by the two methods have different meanings and cannot be directly compared.

We used ROC curves to compare the ability of the two methods to correctly classify a hit as a true or false positive. An ROC curve displays the sensitivity and specificity of the two methods for different values of the threshold. Normally, the area under an ROC curve can be used as a measure of the predictive accuracy of the method. In our case this is not possible, since our experimental procedure does not explicitely define the "true negatives". Therefore, following the method of Gribskov and Robinson (1995), we used normalized ROC50 curves plotted until 50 false positives are found and we then computed the areas under them (see the Methods section of the article for details). If one or both the ROC curves produced by a model had an area smaller than 0.25, we eliminated that model from the analysis.

Table 2 shows the results of this test on the resulting 386 filtered models. The first two columns show the model identifier and the corresponding transcription factor name. The third column shows the length of the HMMER and Match models used in the test (in some cases, the lengths of the two models are too different for the comparison to be meaningful). The next two columns show the area under the ROC50 curve for each method. Since each of these values is the average of 20 measurements, we used a Wilcoxon signed rank test to determine if there was a significant difference between the two areas, at a significance level of 0.05 (with a Bonferroni correction to account for the number of models we tested -- 491). The last column reports the p-value, and if its value is below the significance threshold, the largest area is highlighted in green.

The ROC curves presented above provide a "global" view of the performance of a model. However, one may also be interested in knowing whether a method performs well in the "early" or "late" phases of the search, as this could give an indication of whether a model is better suited for cases in which a small or a large number of hits is desired.

Table 3 reports the percentage of true positives found by HMMER and Match in the first 30, 50, 70, and 90 returned hits respectively. For example, a value of 85% in the 70 column means that out of the first 70 hits, 59.5 were, on average, true positives. In this case, a method is considered "better" than the other (and is highlighted in green) if it returns a strictly higher percentage in three out of four columns, and an equal or higher value in the remaining one.

Table 4 describes how many total hits were necessary for each method to reach 30, 50, 70 and 90 true hits, respectively, expressed as the ratio between the number of false positives and the number of true positives (in percentage). For example, a value of 86% in the 50 column means that the method produced, on average, 43 false positive hits before reaching 50 true positives. In this case, a method is considered better than the other (and is highlighted in green) if it has strictly smaller values in three out of four columns, and an equal of smaller value in the fourth one.

In all the tables, each model identifier is linked to a page containing general information about it and the results of the three tests on it.

The following table summarizes the results of the three tests described above (note: SND = Statistically Not Different). The percentages are computed with respect to the number of models for which a statistically significant difference was found.