BACKGROUND
the tfbs prediction problem can be defined as follows: given n hypothetically co-regulated genes and their promoter sequences s = {s <dig>  s <dig>  ..., sn} , search for motifs that are overrepresented in s compared to the set a of all promoter sequences in the genome.
ideally, the most overrepresented motif is the tfbs.
a recent review on both biological and computational aspects of tfbs prediction is  <cit> .
another review focusing more on the computational aspects is also available  <cit> .
many software tools exist for tfbs prediction, e.g.
consensus  <cit> , meme  <cit> , alignace  <cit> , bioprospector  <cit> , and mdscan  <cit> .
these tools can be classified according to three criteria:
<dig>  tfbs representation: how a putative tfbs is represented, e.g.
consensus sequence  <cit> , psfm   <cit> , bayesian network  <cit>  and hmm  <cit> .
<dig>  search method: how promoter sequences are searched for putative tfbss, e.g.
greedy search  <cit> , gibbs sampling  <cit>  and deterministic iterative search  <cit> .
<dig>  scoring function: how a newly found psfm  is scored to distinguish real binding sites from background noise.
in this paper we will focus on the scoring function, which is a crucial part of any tfbs prediction software.
many scoring functions for tfbs prediction have been proposed in the literature.
unfortunately, it is difficult to assess their relative performance because they are implemented in different software tools that:
<dig>  use different tfbs representations.
<dig>  use different search methods.
<dig>  are tested on different data sets in the original papers.
we compare how several scoring functions perform on both real and semi-simulated data sets in a common test environment.
we also develop two new scoring functions and include them in the comparison.
RESULTS
scoring function performance
six scoring functions  have been evaluated in this study.
the scoring functions were tested on eight different yeast data sets .
in order to compare the performance of the different scoring functions, the rank of the correct motif is shown.
lower rank is better, since the rank is the position of the correct motif in the list of all potential motifs, sorted according to the score from each scoring function.
map is performing quite well on most data sets, except for mac <dig>  the same holds for group specificity.
positional bias performs poorly for most data sets, except reb <dig>  abf <dig> and rap <dig>  local positional bias is clearly better than positional bias, but has problems with abf <dig> and mig <dig>  a closer look at the poor performance of local positional bias for abf <dig> reveals that the positions of the correct binding sites are not clearly localized to a certain region of the promoter sequences.
there is only a weak local positional bias , and many random motifs show a higher local positional bias.
llbg performs well for all data sets and is the best scoring function in this comparison.
the linear combination of llbg and local positional bias performs well in general, but has some problems with mac <dig>  where it interestingly performs worse than llbg alone.
the reason is that local positional bias performs significantly worse than llbg for this data set.
please note that ranks are shown in the graph, so the combined score is not a linear function of the bar heights of llbg and local positional bias, but a linear function of the actual score values  of the llbg and local positional bias.
in order to avoid overfitting, the value of the local positional bias weight a <dig> was estimated based on all data sets but the current one.
the value of a <dig> was around  <dig>  for all data sets .
addition of noise
generally, it is not realistic that all sequences in a data set contain the binding site of interest.
often, when the set of potentially co-regulated genes is defined by microarray experiments , there are false positives  in the data set.
in order to evaluate the scoring functions in the presence of this biologically relevant noise, between  <dig> and  <dig> promoter sequences were randomly selected from the genome and added to the reb <dig>  and mig <dig>  data sets .
the results shown are the average of ten independent runs, with different randomly selected promoter sequences added in each run.
table  <dig> contains a summary of the results.
reb1
in the reb <dig> data set  the map score performs well for reb1+ <dig> .
however, for reb1+ <dig> and reb1+ <dig>  performance decreases quickly.
group specificity shows a similar trend, but is clearly better than map for reb1+ <dig> and reb1+ <dig>  interestingly, positional bias performs extremely well on this data set.
however, because of its general bad performance , we should not put too much confidence into this scoring function.
local positional bias performs consistently poorly on this data set.
llbg does extremely well on reb1+ <dig> and reb1+ <dig>  and for reb1+ <dig> it also shows a good result.
the combined score performs quite well, but consistently worse than llbg alone.
the reason, as we can see, is that local positional bias does not perform well on this data set.
mig1
the mig <dig> data set  was more difficult.
the reason seems to be that the mig <dig> motif shows higher variability between the different promoter sequences than does the reb <dig> motif.
map performed quite poorly, especially on mig1+ <dig> and mig1+ <dig>  group specificity, positional bias and local positional bias failed already at mig1+ <dig>  llbg performed best in every case, slightly better than the combined scoring function on mig1+ <dig> and mig1+ <dig>  and significantly better on mig1+ <dig>
all in all, llbg seems to be the best scoring function in this study.
discussion
choice of search method
the iterative deterministic search method was used in this study because it has been shown  <cit>  to suffer less from local optima than e.g.
gibbs sampling.
however, the scoring functions tested here can score any arbitrary set of candidate words, no matter how these words are selected, so the relative performance of the different scoring functions should not depend on the choice of search method.
the only interaction between the search method and the scoring function is that the search method provides the scoring function with several sets of candidate motifs to score.
determination of parameters
most scoring functions have one parameter where the value is not directly determined by the data: map , group specificity , local positional bias  and llbg .
in this respect, these scoring functions are similar.
the exception is positional bias, which has two parameters .
we also note that the cardinality of the parameters are different.
for example, only a few discrete values are reasonable for the markov model order.
on the other hand, e.g.
the group specificity s <dig> parameter has a larger range of possible values.
we have not tried to find the optimal parameters of each scoring function, but used the values proposed in the original papers.
since yeast is often used as a model organism for tfbs prediction studies, we assumed that the default parameters are reasonable for the yeast data sets in this study.
also, to make the comparison as fair as possible, we used the same markov model order  in llbg as was used in map.
positional bias
because of the high variance in performance of the positional bias based scoring functions, it seems that positional bias is a feature of only a few of the data sets in this study.
for others, it seems that the positions of the tfbss do not deviate strongly from a random distribution.
this has also been observed previously  <cit> .
when a large number of long promoter sequences are searched for motifs, many candidate motifs have to be considered.
if a scoring function only deviates slightly from the random distribution, many false positives will be found, which is the case of positional bias and local positional bias.
advantages of llbg
robustness is an important property of tfbs scoring functions.
the tests performed on reb <dig> and mig <dig> with added noise indicate that llbg is quite robust against this form of biologically realistic noise, more robust than the other scoring functions in this test.
many software tools for tfbs prediction require the user to specify the motif width w as a parameter.
this is of course difficult when the motif is unknown and makes these tools impractical to use.
the map scoring function is normalized by the motif width, which should make it comparable for motifs of different widths  <cit> .
however, scaling the entropy part of map is problematic, as pointed out by  <cit> .
the llbg score does not have entropy as a part of its function, and hence should not suffer from this problem.
possible extensions
the llbg score, as it is currently defined, measures the probability of a motif occurring at least once in the promoter sequence.
it is possible to extend it to how many times a motif occurs in a sequence, which would increase its performance on data sets with several tfbss per sequence.
however, initial experiments have indicated that a multi-motif-per-sequence version of llbg did not improve the results for the yeast data sets that we have been working with so far.
even though we have here treated only the problem of finding a single motif, it is possible to generalize the llbg scoring function to clusters of different motifs.
this is of special interest in higher eukaryotes and will be subject to future work.
currently, the llbg is based on the discrete distance measure of number of mismatches between a candidate word and the psfm consensus.
future research will go into using a continuous distance between a candidate word and the psfm .
this should make the score more robust, especially for long motifs with many uninformative positions, and it should further improve the performance of this scoring function.
we have here focused on the problem of de novo prediction of tfbss.
the related problem of tfbs recognition, where a library of known tfbss is used to search for similar motifs in s, has not been considered here.
clearly, these libraries may improve tfbs prediction if the tfbs of interest happens to be similar to a tfbs already documented.
conceptually, this can easily be incorporated in the llbg scoring function by studying the likelihood ratio between the tfbs library model and the background model.
limitations of current models
it should be noted that although the best scoring functions perform reasonably on these yeast data sets , the problem becomes much more difficult when dealing with higher eukaryotes .
in that case, all of these scoring functions are likely to have problems , and it becomes more important to extend the models by including other sources of information, such as chip-chip and phylogenetic footprinting data.
since nature is able to find tfbss with higher precision than any of the scoring functions reviewed here, we believe that the current computational models are missing some fundamental part of the transcription regulation mechanism.
future research will go into investigating the structural properties of dna that enables transcription  <cit> .
interesting progress on work in this direction has been done recently for prokaryotes  <cit> , and the related histone code has been suggested for eukaryotes  <cit> .
CONCLUSIONS
the time requirements of the scoring functions in this study are very different.
llbg, map and local positional bias are relatively fast to evaluate.
group specificity and positional bias are significantly more time consuming, since they require a search of a psfm in all intergenic sequences.
since the two slower scoring functions do not perform better than three faster ones, their longer computation time does not seem to be justified.
the positional bias and local positional bias are scoring functions that perform quite poorly for several data sets , but quite well for others .
in other words, it seems that this feature is not relevant for some data sets , but that it clearly matters for other data sets.
this makes these scoring functions difficult to use for de novo tfbs prediction, since we cannot know beforehand whether an unknown tfbs is positionally biased.
llbg is the scoring function that performs best in this test.
the other scoring functions perform well on some data sets and poorly on others.
combining llbg and local positional bias results in a scoring function that on average performs slightly worse than llbg alone.
since there is no clear improvement in combining the scoring functions , the simpler solution of using only llbg should be preferred.
a software tool using the llbg scoring function is currently being developed.

 the tfbs prediction problem can be defined as follows: given n hypothetically co-regulated genes and their promoter sequences s = {s s..., sn}, search for motifs that are overrepresented in s compared to the set a of all promoter sequences in the genome. ideally, the most overrepresented motif is the tfbs. a recent review on both biological and computational aspects of tfbs prediction is. another review focusing more on the computational aspects is also available. many software tools exist for tfbs prediction, e.g. consensus, meme, alignace, bioprospector, and mdscan. these tools can be classified according to three criteria: tfbs representation: how a putative tfbs is represented, e.g. consensus sequence, psfm, bayesian network and hmm. search method: how promoter sequences are searched for putative tfbss, e.g. greedy search, gibbs sampling and deterministic iterative search. scoring function: how a newly found psfm is scored to distinguish real binding sites from background noise. in this paper we will focus on the scoring function, which is a crucial part of any tfbs prediction software. many scoring functions for tfbs prediction have been proposed in the literature. unfortunately, it is difficult to assess their relative performance because they are implemented in different software tools that: use different tfbs representations. use different search methods. are tested on different data sets in the original papers. we compare how several scoring functions perform on both real and semi-simulated data sets in a common test environment. we also develop two new scoring functions and include them in the comparison.  scoring function performance six scoring functions have been evaluated in this study. the scoring functions were tested on eight different yeast data sets. in order to compare the performance of the different scoring functions, the rank of the correct motif is shown. lower rank is better, since the rank is the position of the correct motif in the list of all potential motifs, sorted according to the score from each scoring function. map is performing quite well on most data sets, except for mac the same holds for group specificity. positional bias performs poorly for most data sets, except reb abf and rap local positional bias is clearly better than positional bias, but has problems with abf and mig a closer look at the poor performance of local positional bias for abf reveals that the positions of the correct binding sites are not clearly localized to a certain region of the promoter sequences. there is only a weak local positional bias, and many random motifs show a higher local positional bias. llbg performs well for all data sets and is the best scoring function in this comparison. the linear combination of llbg and local positional bias performs well in general, but has some problems with mac where it interestingly performs worse than llbg alone. the reason is that local positional bias performs significantly worse than llbg for this data set. please note that ranks are shown in the graph, so the combined score is not a linear function of the bar heights of llbg and local positional bias, but a linear function of the actual score values of the llbg and local positional bias. in order to avoid overfitting, the value of the local positional bias weight a was estimated based on all data sets but the current one. the value of a was around for all data sets. addition of noise generally, it is not realistic that all sequences in a data set contain the binding site of interest. often, when the set of potentially co-regulated genes is defined by microarray experiments, there are false positives in the data set. in order to evaluate the scoring functions in the presence of this biologically relevant noise, between and promoter sequences were randomly selected from the genome and added to the reb and mig data sets. the results shown are the average of ten independent runs, with different randomly selected promoter sequences added in each run. table contains a summary of the results. reb1 in the reb data set the map score performs well for reb1+. however, for reb1+ and reb1+ performance decreases quickly. group specificity shows a similar trend, but is clearly better than map for reb1+ and reb1+ interestingly, positional bias performs extremely well on this data set. however, because of its general bad performance, we should not put too much confidence into this scoring function. local positional bias performs consistently poorly on this data set. llbg does extremely well on reb1+ and reb1+ and for reb1+ it also shows a good result. the combined score performs quite well, but consistently worse than llbg alone. the reason, as we can see, is that local positional bias does not perform well on this data set. mig1 the mig data set was more difficult. the reason seems to be that the mig motif shows higher variability between the different promoter sequences than does the reb motif. map performed quite poorly, especially on mig1+ and mig1+ group specificity, positional bias and local positional bias failed already at mig1+ llbg performed best in every case, slightly better than the combined scoring function on mig1+ and mig1+ and significantly better on mig1+ all in all, llbg seems to be the best scoring function in this study. discussion choice of search method the iterative deterministic search method was used in this study because it has been shown to suffer less from local optima than e.g. gibbs sampling. however, the scoring functions tested here can score any arbitrary set of candidate words, no matter how these words are selected, so the relative performance of the different scoring functions should not depend on the choice of search method. the only interaction between the search method and the scoring function is that the search method provides the scoring function with several sets of candidate motifs to score. determination of parameters most scoring functions have one parameter where the value is not directly determined by the data: map, group specificity, local positional bias and llbg. in this respect, these scoring functions are similar. the exception is positional bias, which has two parameters. we also note that the cardinality of the parameters are different. for example, only a few discrete values are reasonable for the markov model order. on the other hand, e.g. the group specificity s parameter has a larger range of possible values. we have not tried to find the optimal parameters of each scoring function, but used the values proposed in the original papers. since yeast is often used as a model organism for tfbs prediction studies, we assumed that the default parameters are reasonable for the yeast data sets in this study. also, to make the comparison as fair as possible, we used the same markov model order in llbg as was used in map. positional bias because of the high variance in performance of the positional bias based scoring functions, it seems that positional bias is a feature of only a few of the data sets in this study. for others, it seems that the positions of the tfbss do not deviate strongly from a random distribution. this has also been observed previously. when a large number of long promoter sequences are searched for motifs, many candidate motifs have to be considered. if a scoring function only deviates slightly from the random distribution, many false positives will be found, which is the case of positional bias and local positional bias. advantages of llbg robustness is an important property of tfbs scoring functions. the tests performed on reb and mig with added noise indicate that llbg is quite robust against this form of biologically realistic noise, more robust than the other scoring functions in this test. many software tools for tfbs prediction require the user to specify the motif width w as a parameter. this is of course difficult when the motif is unknown and makes these tools impractical to use. the map scoring function is normalized by the motif width, which should make it comparable for motifs of different widths. however, scaling the entropy part of map is problematic, as pointed out by. the llbg score does not have entropy as a part of its function, and hence should not suffer from this problem. possible extensions the llbg score, as it is currently defined, measures the probability of a motif occurring at least once in the promoter sequence. it is possible to extend it to how many times a motif occurs in a sequence, which would increase its performance on data sets with several tfbss per sequence. however, initial experiments have indicated that a multi-motif-per-sequence version of llbg did not improve the results for the yeast data sets that we have been working with so far. even though we have here treated only the problem of finding a single motif, it is possible to generalize the llbg scoring function to clusters of different motifs. this is of special interest in higher eukaryotes and will be subject to future work. currently, the llbg is based on the discrete distance measure of number of mismatches between a candidate word and the psfm consensus. future research will go into using a continuous distance between a candidate word and the psfm. this should make the score more robust, especially for long motifs with many uninformative positions, and it should further improve the performance of this scoring function. we have here focused on the problem of de novo prediction of tfbss. the related problem of tfbs recognition, where a library of known tfbss is used to search for similar motifs in s, has not been considered here. clearly, these libraries may improve tfbs prediction if the tfbs of interest happens to be similar to a tfbs already documented. conceptually, this can easily be incorporated in the llbg scoring function by studying the likelihood ratio between the tfbs library model and the background model. limitations of current models it should be noted that although the best scoring functions perform reasonably on these yeast data sets, the problem becomes much more difficult when dealing with higher eukaryotes. in that case, all of these scoring functions are likely to have problems, and it becomes more important to extend the models by including other sources of information, such as chip-chip and phylogenetic footprinting data. since nature is able to find tfbss with higher precision than any of the scoring functions reviewed here, we believe that the current computational models are missing some fundamental part of the transcription regulation mechanism. future research will go into investigating the structural properties of dna that enables transcription. interesting progress on work in this direction has been done recently for prokaryotes, and the related histone code has been suggested for eukaryotes.  the time requirements of the scoring functions in this study are very different. llbg, map and local positional bias are relatively fast to evaluate. group specificity and positional bias are significantly more time consuming, since they require a search of a psfm in all intergenic sequences. since the two slower scoring functions do not perform better than three faster ones, their longer computation time does not seem to be justified. the positional bias and local positional bias are scoring functions that perform quite poorly for several data sets, but quite well for others. in other words, it seems that this feature is not relevant for some data sets, but that it clearly matters for other data sets. this makes these scoring functions difficult to use for de novo tfbs prediction, since we cannot know beforehand whether an unknown tfbs is positionally biased. llbg is the scoring function that performs best in this test. the other scoring functions perform well on some data sets and poorly on others. combining llbg and local positional bias results in a scoring function that on average performs slightly worse than llbg alone. since there is no clear improvement in combining the scoring functions, the simpler solution of using only llbg should be preferred. a software tool using the llbg scoring function is currently being developed. 
here we compare how several scoring functions perform on both real and semi-simulated data sets in a common test environment. transcription factor binding site prediction is a difficult problem, which requires a good scoring function to discriminate between real binding sites and background noise. many scoring functions have been proposed in the literature, but it is difficult to assess their relative performance, because they are implemented in different software tools using different search methods and different tfbs representations. llbg may provide an interesting alternative to current scoring functions for tfbs prediction. scoring functions based on positional bias performed quite poorly in this study.
 transcription factor binding site prediction is a difficult problem, which requires a good scoring function to discriminate between real binding sites and background noise. many scoring functions have been proposed in the literature, but it is difficult to assess their relative performance, because they are implemented in different software tools using different search methods and different tfbs representations.  here we compare how several scoring functions perform on both real and semi-simulated data sets in a common test environment. we have also developed two new scoring functions and included them in the comparison. the data sets are from the yeast genome. our new scoring function llbg performs best in this study. it achieves the best average rank for the correct motifs. scoring functions based on positional bias performed quite poorly in this study.  llbg may provide an interesting alternative to current scoring functions for tfbs prediction. 