BACKGROUND
the regulation of gene expression in the cell is controlled by regulatory proteins and functional rnas that interact specifically with binding locations on the dna.
in the past century, molecular biologists have developed many innovative techniques to identify sites on the dna that are bound and regulated by functional rna and proteins.
as the number of sequenced organisms increases, traditional techniques such as gel shift assays in combination with dnase foot-printing assays can not keep pace with the explosion of available sequences.
while accurate, traditional methods require a great deal of time and expertise.
traditional methods also require that the binding energy of the protein or rna is great enough to maintain contact though the course of the assay.
reductionist approaches can be problematic when faced with non-specific binding sites or with sites that require the formation of a complex with adjacent units in order to function.
it is for these reasons that complementary approaches on the computer have been developed in recent years to increase success in discovering and annotating cis-regulatory modules.
computational discovery of functional subsequences has been around for some time.
in  <dig>  galas, eggert, and waterman proposed a method for finding and characterizing binding positions for the σ  <dig> protein in e. coli promoter sequences  <cit> .
in its most basic form, the problem is identifying sequence signatures, or motifs, that exist in a set of sequences that share the same property , but does not exist in a set of similar sequences that does not have the same property .
computational approaches have the advantage that they can reduce the guess work and cost associated with pure biochemical approaches.
consequently, many computational methods such as gibbs  <cit> , meme  <cit> , consensus  <cit> , bioprospector  <cit> , alignace  <cit> , ann-spec  <cit> , mtap: the motif tool assessment platform.
glam  <cit> , and weeder  <cit>  have been developed in recent years.
each of these methods employs different algorithmic insights and scoring functions.
the scoring function and algorithm parameters impact the representation and rank of the motifs discovered by the algorithm.
in recent years, it has become clear that each of these computational methods has distinct advantages and that the best performance is achieved by trying multiple methods over the same data set.
the bioinformatics community is currently seeking to simplify this situation by providing approaches that integrate multiple methods into one tool such as best  <cit>  and emd  <cit> .
approaches that integrate additional sources of information have also emerged in recent years.
for example, approaches such as phyme  <cit> , phylogibbs  <cit> , and weederh  <cit>  integrate sequences from regulatory regions of related organisms.
other approaches, such as reduce  <cit> , integrate expression values from gene expression arrays.
in addition, the advent of high density arrays and chip-chip technology has necessitated methods that integrate genome wide binding data  <cit> .
while there are many advantages in integrating additional sources of information, the steps required also add additional complexity and cost.
each step along the integration pipeline opens a new question: what is the best way to represent and integrate this new data?
one has to wonder if additional data is always better in practice.
it could be that for some regulatory modules, the additional data also includes additional noise making it more difficult to recover the binding sites.
to make matters more confounding, there currently exist more than  <dig> methods with thousands of possible pre- and post-processing steps and alternative runtime procedures .
it is clear that benchmarking technology is needed to map cis-regulatory motif discovery methods to data where the method has the best performance.
in other words, given a method m and a set of co-regulated genes with regulatory sequences t = {t <dig>  t <dig> ..., tn}, find a mapping m → t with expected performance over some threshold.
a t that has no method over the threshold is particularly interesting in that such data can tell us more about the current limitations of regulatory motif discovery programs so that we can propose improvements.
in recent years, researchers have begun to solve this problem by creating benchmarking datasets.
in  <dig>  tompa et al.
published the first assessment of  <dig> regulatory motif discovery algorithms over fly, human, mouse and yeast  <cit> .
this work was seminal in that it provided methods for comparing regulatory motif detection software and that it benchmarked a large number of popular tools  <cit> .
in  <dig>  sandve et al.
improved benchmarking technology over the tompa dataset using a machine learning approach  <cit> .
while these advances opened the important debate on how to benchmark algorithm performance, it remains to be seen if a selection of so few regulatory binding sites is large enough to form a representative set .
in response, klepper et al.
proposed a larger test set and used it to evaluate several composite motif discovery tools  <cit> .
this is an important first step in making benchmarking datasets more comprehensive.
to date, the most comprehensive test set was over the entire e. coli genome  <cit>  using known transcription factors found in regulondb  <cit> .
while bacterial transcription regulation is very different than regulation in eukaryotes, the density of the regulondb annotation is greater than for any other organism and this coverage provides us with unique benchmarking opportunities.
unfortunately, this assessment only considered  <dig> tools and neglected to include the tool most successful in the tompa benchmark .
to date, there are no tools that can assess algorithms that incorporate additional sources of data such as sequences from phylogentically related species.
currently, cis-regulatory motif tools are assessed using the statistics and methods from gene prediction.
however, in silico gene annotation differs from cis-regulatory module annotation in that in gene prediction there exists an mrna library for reference.
unlike regulatory binding assays, mrna library sequencing is high throughput and thus provides a large and diverse benchmarking dataset for gene prediction tools.
consequently, gene prediction and cis-regulatory module prediction are very different problems.
we currently have very few completely annotated regulatory modules and therefore motif prediction tools have very few cases to train.
in addition, regulatory modules are thought to evolve at a much faster rate than the genes they regulate  <cit> .
if this theory is true, the diversity of regulatory regions is expected to be far greater than the coding regions they regulate.
this means that the parameters, data, transcription module representation and algorithm are all important factors in evaluating motif detection tools.
in this work, we expand upon our parallel architecture for regulatory motif prediction  <cit>  and propose a method for evaluation and discovery of data algorithm mappings.
mtap is a platform that allows one to vary the way scientists process data and algorithm parameters to fine tune the representation of a regulatory module in method m. the goal is to discover the best possible mapping of m → d. our platform also integrates phylogentically related regulatory sequences via computing downstream orthologs from other species.
it is clear that phylogentic footprinting has great potential, however assessing methods that incorporate sequence from closely related species is not practical or accurate without automation .
for these reasons, there is a place for adaptive and automatic cis-regulatory motif prediction and benchmarking.
problem description
a cis-regulatory motif discovery pipeline, mi, contains a series of steps to separate transcription factor binding sites from 'background noise'.
motif discovery pipelines require collecting the positive example sequences, collecting negative example sequences, collecting relevant supporting data, running a separation filter to rank relevant sites based on an objective function and finally evaluating or verifying putative sites within the context of each regulatory module.
several factors outside of the pipeline itself contribute to the potential success of the discovery process, mainly:  the length of the sequences in the positive and negative sets,  the number of sequences in the positive and negative sets,  the distribution of transcription factor binding sites in the positive set,  the relative entropy of the transcription factor binding motif, and  the fraction of null sequences  in the positive set  <cit> .
it is likely there are additional unknown variables that impact the accuracy of an approach.
for example, better background sequence models or sequences from closely related species  are known to affect performance.
our approach to finding the variables, parameters, and algorithms that are best suited to annotating regulatory regions is an adaptive data collection and analysis platform .
our hypothesis is that a platform that automates each operation in cis-regulatory motif discovery enables discovery of better methods for cis-regulatory motif prediction.
such a platform enables practitioners and users the necessary flexibility to change characteristics of the data and algorithm parameters, and to isolate and understand known challenge cases.
in addition, known methods with many manual steps can be made more explicit.
presently, it is difficult to benchmark existing approaches because they have a great variety of algorithmic parameters that allow the user to interactively optimize the discovery process.
while this approach is advantageous because it provides flexibility in the discovery process, it also presents a challenge in algorithm benchmarking: how to formalize data collection, parameter fine tuning, and other intuitive steps taken by the most experienced users of these methods.
from a more practical perspective, one has to wonder what evidence experienced practitioners use to determine a set of algorithm refinement steps that will result in better performance over the new dataset .
our hypothesis is that the motif discovery process can be greatly improved if tool parameters are fine tuned based on previous performance benchmarks.
we present algorithm benchmarking over a set of known and related transcription factor binding sites  as a method to uncover the likely performance on the current dataset.
this approach allows the refinement and modification of motif prediction pipelines.
in particular, such a benchmarking approach allows for interactive modification of known tfbs in incomplete datasets, modification of the procedures used in collecting positive, negative, and phylogenatically related sequence samples, modification of methods for finding tfbs within the samples, and even modification of the methods used to score motif discovery pipelines.
our central hypothesis is that by looking at all components of data and software along the cis-regulatory motif discovery process, we can refine our understanding of regulation and discover pipelines with high accuracy.
the way we look at this complex problem is a result of how we collect the data, how we build algorithms for discovering regulatory motifs, the biological and manual processes and data structures used to create comprehensive annotations of cis-regulatory regions, and the methods we choose to use in grading these motif discovery tools.
we view each of these components as parts that can and should be modified as the specifics of the biological problem at hand become clear.
in this paper, we present a open source prototype for cis-regulatory motif discovery algorithm evaluation.
implementation
mtap provides an automated method for ranking regulatory motif detection algorithms.
the underlying principle is to create a 'test', t, and an 'answer key', k = {k <dig>  k <dig> ...}.
k is generated by parsing the raw database management systems  of regulondb  <cit> , dbtbs  <cit> , prodoric  <cit> , regtransbase  <cit>  and transfac  <cit> .
the annotated genome, gj, is then parsed for each regulatory binding site annotated in k. tk is a collection of sequences corresponding to the surrounding regions of known binding sites for transcription factor k in gj.
tk is composed of l instances of binding positions t <dig>  t <dig> ..., tl in gj as annotated by the database.
to score a method, mi, we construct an automated pipeline via a scripting language  that runs the method.
each method has a different algorithmic approach and has different requirements of pre- and post-processing.
for each method, we construct background probability models, standardize input datasets, install program dependencies, and provide conversion and utility scripts so that each method can be graded fairly.
we consider a fair test to be a test where each program has access to the same information and must mark the transcription factor binding positions in a standard way.
this standard marking is then assessed by comparing the annotation of regulatory sites provided by the algorithm with the known annotation in the database.
a schematic overview of our assessment method is presented in figure  <dig>  because databases contain many types of binding positions  these evaluations are an indication of how well each algorithm can recover the binding positions for each element in the regulatory network and not just transcription factor binding positions.
generating upstream sequences
varying upstream length allows us to explore the trade off between detecting long range interactions  and high prediction accuracy .
mtap contains two genome substringing methods for generating upstream sequences as shown in figure  <dig>  'completely-realistic'  data generation is best suited to problems that convert gene lists to binding locations .
'semi-realistic'  data generation is best suited to problems that generate a set of sequences .
in most cases 'sr' constructed data produces a more fair comparison between pattern finding methods, but is not realistic when the tools are applied to a set of co-regulated loci.
completely-realistic data generation is most often the natural choice, but is limited because the upstream file may not contain the motif for long range interactions.
also, the 'cr' method may select a different downstream gene as part of the data construction procedure.
these two issues are realistic in the cis-regulatory motif discovery process and are representative of current problems in cis-regulatory motif discovery.
this method is therefore representative of current methods used in constructing co-regulated upstream sequences.
future work could be done to make automated upstream data generation more sensitive to these types of issues.
the transformation function t applies one of the substring operations  to the reference genome gj to produce tk.
tk is generated by selecting regulator k and generating an upstream sequence uk, n for all instances of k in gj.
figure  <dig> provides a diagram of several of the stages used to construct t = t <dig>  t <dig> ... for all instances of k in gj.
despite the fact that tk is constructed by considering only tf k, all of the other transcription factors in the database are marked and scored if they fall within sequence indices for any sequence in tk.
generating orthologous upstreams
after the upstream file, uk, n, is constructed, mtap collects regulatory sequences from closely related genomes gj+ <dig>  gj+ <dig> ..., by using downstream orthologs.
to do this, mtap constructs a list of all proteins in each genome gj+ <dig>  gj+ <dig> .... before the upstream is created, mtap uses as orthalog detection method to create an orthalog table, o .
o contains a list of protein products from gj and gj+ <dig> and a confidence score oc corresponding to the confidence in the orthology relationship as determined by the ortholog detection method.
for each sequence in uk, we select the nearest downstream gene, gi, j ∈ gj.
mtap then looks up any entries for gi, j ∈ o. if oc > τ for some constant τ, mtap appends a region n bp upstream of gj+ <dig>  if multiple entries exist for gi, j, mtap appends the region upstream gj+ <dig>  i such that oc is greatest.
mtap continues this procedure for all genomes gj, gj+ <dig> .... this procedure is then repeated to construct t <dig>  t <dig> .... an example result is found in figure 4d.
several important points should be made about phylogentic foot-printing.
first, the existence of a set of regulatory binding sites exists in gj does not imply the existence of the same set of regulatory binding positions in gj+ <dig> in the same positions.
in our example in figure  <dig>  tk does not contain a binding position for k <dig> ∈ gj+ <dig>  it is possible that our criteria to classify orthologs is too stringent to find an actual ortholog in gj+ <dig>  notice that in our example tl contains no upstream corresponding to g <dig> in gj+ <dig>  in our example, this occurred because the homology threshold criteria excluded g <dig> from gj+ <dig>  again, these problems will exist in any current automated pipeline used for regulatory motif detection.
some of these issues can be resolved within the algorithms themselves: many algorithms incorporate the hypothesis that zero or many instances of the cis-regulatory binding motif exists within the upstream sequence.
however, the prospect is very real that we could integrate sequences that are related but do not contain binding sites for transcription factor k. currently, we have very little understanding of the relationship between the evolution of regulatory sequences and coding sequences.
it is quite possible that phylogenetically related sequences introduce additional 'noise' with very little signal in regulatory sequences for genes that do not provide critical functions.
these complex relationships warrant an in-depth study of regulatory evolution as it relates to coding sequence evolution – which is the subject of future work.
for now, we wish to use this approach to benchmark single genome methods as they compare to multiple genome based methods.
to our knowledge, mtap is the first method that allows additional sources of information  to be automatically integrated as part of the evaluation process.
constructing background sequences
once tk has been constructed for all k, we present three possible background sequence files to motif discovery pipelines:  all upstream sequences of length n in gj,  all upstream sequences of length n that exist in some tk, and  a fasta formated sequence of gj.
programs that incorporate phylogeny have different background sequence requirements.
such programs require a background phylogenetic tree constructed from extracting 16s rrna from each genome in the study.
some programs require pre-processing steps to calculate an hmm or gc content of the test sequences.
other programs require a background probability distribution of all upstream sequences in gj.
we compute each of these requirements for each pipeline in our pre-processing stage and provide the files to each pipeline.
compensating for unknown tfbs
unknown tfbs that exist in tk complicate the assessment process.
tools could predict true sites that are currently unknown or un-annotated.
to exclude unknown sites from tk, we construct a markov chain, mcm, .
for each sequence, si, in tk, si is sampled with mcm.
we then generate an alternative sequence, s'i, through a random walk through the sates in mcm.
for all tfbs in k that overlap si, we insert the true tfbs sequence from si into s'i.
in this way, we use mcm to 'scramble' the upstream sequences in the test and then re-insert the known motifs back into the sequences at the same positions found in the source genome.
it is also informative to have instances of true negative sequences produced via mcm, so we produce instances of tk with no inserted tfbs.
orthologous upstream sequences need not be scrambled if they are not scored.
these synthetic sequences serve to make a ' more fair' test in those cases where very few of the known motifs are marked.
however, such sequences may not correctly incorporate the biological process that generates true sequences.
to accommodate this, we also insert tfbs into a random sequence from the set of all upstream sequences in gj.
constructing motif discovery pipelines
in constructing motif discovery pipelines, our intention is to include pipelines for as many tools as possible.
however, building parsers, installing scripts, and optimizing a pre-processing, post-processing, and runtime pipeline for each of over  <dig> programs is extremely labor intensive.
our main obstacle is in finding executables that can run on a variety of architectures in a linux cluster.
in many cases, we attempted to contact authors to arrange a port of their tool to a linux cluster.
many authors are extremely helpful and we would like to thank them for the advice and guidance of how to use and port their tool.
however, we realized that even if we have a stand-alone version of a method working on our architecture, mtap users will still need to install many of the tools directly from the authors .
our strategy for including a tool is as follows:
• include tools that are the most popular.
• include tools that present different and novel scoring functions for differentiating background sequences from transcription factor binding sites.
• include tools that integrate diverse types of information from public sources.
• do not include tools that do not have a downloadable executable or can not be compiled locally, as such tools can not easily be run thousands of times for assessment purposes.
• do not include tools that do not have support for different architectures and operating systems .
• as we can not redistribute tools with strict licensing agreements or 'abandonware', inclusion of such tools is left to the user community.
our platform is provided open-source for practitioners who would like to develop their own pipelines to integrate their tool into mtap.
this approach has an advantage in that the developer of the tool is also the developer of the pipeline for evaluating the tool.
this could provide an edge as the tool developer will understand the limitations and usage procedures best.
we provide our assessment pipelines within our framework for open access review and improvement.
in this work, we developed pipelines for alignace  <cit> , ann-spec  <cit> , elph  <cit> , gibbs  <cit> , glam  <cit> , meme  <cit> , phylogibbs  <cit> , phyme  <cit> , and weeder  <cit> .
for each of these tools in the tompa et.
al benchmark, we developed an automated system that was as close to the spirit of the procedure used by the algorithm practitioners as practical.
for example, our alignace pipeline contains a pre-processing script for calculating gc content of the upstream file and a postprocessing script to mask low complexity repeats using repeatmasker.
the pipeline then parses the raw alignace output which results in a ranked list of predicted transcription factor binding sites sorted via the alignace map score.
the pipeline accepts the highest c scoring motifs by map score and then determines confidence by calculating the group specificity score as provided by compareace.
a high group specificity score and map score indicates a high degree of confidence in the prediction provided by the alignace pipeline.
for those tools that are not in the tompa assessment, we carefully followed the usage guides and refined our pipelines using mtap to produce the best results possible.
for some methods, the code is not available and the method paper does not make it clear if certain data preparation procedures can be accommodated by the method.
for example, some methods account for upstream sequences that are reverse complemented while others do not.
some methods account for zero, one, or many motif instances on one strand while others do not.
some methods allow for variable motif widths, while others require an explicit window .
we assume that motif discovery pipelines are sufficiently robust to account for these technical details and we attempted to make our pipelines robust in this way.
however, in constructing these pipelines in this way, we may have overlooked some aspects of the algorithmic approach that would make our pipelines not representative of the original author intent .
we addressed this issue in two ways.
first, we built pipelines for multiple implementations of similar approaches .
second, we refined each pipeline based on the objective function found in the literature and the benchmarks obtained via mtap.
to guard against over-fitting of a pipeline to a certain dataset, we did not allow modification of the code or implementation of any procedures not recommended explicitly by the authors.
we performed benchmarks over the tompa assessment datasets, regulondb  <cit> , and dbtbs  <cit>  and selected transcription factors at random to validate if the proposed change improved results.
as the search space is large, there may exist a set of pre-processing, post-processing, and runtime steps that may improve the performance of our current pipelines.
if used in this way, mtap provides the framework for method developers and method users to formalize and improve motif discovery pipelines.
pipeline evaluation
three levels of specificity can be considered when evaluating the accuracy of mi:  mi correctly predicts the region bound by some transcription factor k,  mi correctly predicts the binding site of k, and  mi correctly predicts the amino acids in tf that interact with specific nucleotides within the regulatory region.
mi may also correctly predict the type and strength of the interactions.
predictions of type  <dig> are analogous to a gel shift assay in that we can identify a part of the regulatory region bound by a protein.
predictions of type  <dig> are analogous to a dna foot-printing assay.
predictions of type  <dig> are more specific in that each region of interaction between k and the dna is identified.
for example, if a transcription factor is a dimer, two interaction sites are identified by predictions of type  <dig> whereas only one interaction site is identified by a prediction of type  <dig> .
the third type of prediction is analogous to determining the crystal structure interaction points of the transcription factor – dna complex.
while the specificity and information provided by the third type of prediction is far greater than annotations of type  <dig> or type  <dig>  such data is difficult to obtain and few methods make predictions at this level.
we therefore generate two annotation files: a 'redfile' and a 'blackfile' corresponding to the site level and region level respectively.
to generate an upstream file, we use the blackfile annotation.
to assess the performance of an algorithm we evaluate the predictions versus the redfile annotation.
the redfile annotation red = i <dig>  i <dig> ... contains a set of intervals ik = , ,... that correspond to the start  and stop  positions in gj corresponding to binding locations for transcription factor k. to compare the redfile annotation to the motif tool predictions, ui  is used as a scaffold to place annotation elements.
to annotate the known sites at the nucleotide level, we mark each base, j, in ui if uh ≤ j ≤ vh ∀ k.  the predicted binding locations, bk,u,vu, predicted by mi are parsed and translated into a ranked list of predicted binding sites, each of the form bk <dig> u <dig> v1u,bk <dig> u <dig> v <dig> ...u. the ranked list contains elements tfl <dig>  tfl <dig> ... sorted according to the confidence that mi has in the prediction accuracy.
mtap accepts the top c elements from the rank list for evaluation and inserts them onto the upstream scaffold.
mtap then marks each position, j, as a predicted nucleotide if there exists some predicted binding site, b, that overlaps it.
at the nucleotide level, we collect the overlap statistics shown in table  <dig>
the first four core statistics  are collected by summing the number of each of the occurrences shown in table  <dig> in tk.
the site level statistics  are the final three core statistics provided by mtap.
a site level statistic encompasses the idea that a group of adjacent nucleotides marked as binding positions for transcription factor k by mi is representative of a binding site annotation.
a site is annotated as a true positive if bk,u,vui overlaps ix ∀ x by more than τ percent of ix.
for example, consider two overlapping sites, a known site ix of  <dig> consecutive nucleotides and a predicted site b of  <dig> consecutive nucleotides.
given τ = .
<dig> if ix shares  <dig> nucleotides with b it is annotated as a stp.
if ix shares only  <dig> nucleotides with b it is annotated as a sfp.
once a site, ix, overlaps a prediction, it can not be annotated as a sfn.
all remaining sites, i <dig>  i <dig> ..., ix, that do not have an overlapping prediction for tool mi are annotated as sfn.
the site level statistics are in table  <dig>
tompa et.
al set τ to 25%.
the logic was that such an overlap makes discovery and refinement of the tfbs possible in the lab.
in large scale genome annotations, we find such a threshold to be too strict.
for example, many tfbs are not annotated specific enough in databases such as regulondb.
this results in tfbs that exist in k that can be large.
such annotations are actually representative of the region of binding of the transcription factor  and not the binding sites .
because many motif discovery programs have fixed motif widths , a threshold of 25\% would not be sufficient to mark a stp .
we could choose to rank site level motifs based on a percentage of the prediction width instead of the regulatory motif width, but this would give an unfair advantage to methods that predict larger sites.
our current approach is to set τ equal to the maximum annotated site width in the dataset divided by the minimum expected motif width predicted by our suite of programs  times 25%.
our logic is that a degree of overlap indicates that computational and biological refinement of site predictions can still find the site.
that said, manual curation of datasets to ensure binding site annotations rather than region annotations is necessary.
standards across regulatory binding site databases to delineate each of the three levels of biological data would greatly increase evaluation accuracy of motif discovery tools.
also, as not all tools provide a mapping for a set of sites to a putative regulator, these statistics are currently not reflective of which regulator is annotated by a site level prediction.
following tompa et.
al we define the statistics in figure  <dig> to perform the assessment.
these statistics enable us to determine the quality of algorithm predictions and therefore infer which tools may be best suited to discover unknown motifs under similar situations.
mtap evaluates each of these statistics by comparing the predictions found in the program output with a set of known binding positions of the same type.
for each instance found in the known dataset, a motif prediction tool is run and then parsed.
the prediction is compared to the known binding site via the seven key statistics in table  <dig> and table  <dig>  these statistics will then be used to assess the overall performance of the algorithm.
mtap produces an output file for each regulatory binding motif in k. users can sum the raw statistics in these files as they see fit.
for this paper, we collect the seven raw performance statistics for each motif in the assessment and then sum these values as if the collection of runs was actually one run.
in some cases, such sums do not graphically represent the contribution of each element in the set to the total performance score.
to address this, we also developed a graph that iterates over all runs in the test  the graph produced is a modified receiver operating characteristic  curve that combines statistics from multiple runs  <cit> .
we use the following algorithm to produce our roc graphs:
for each motif in the dataset:
input xtp, xfp, nfn, ntn, stp, sfp, sfn
p < -calculate xsp and xsn for this motif
for all motifs in the dataset:
totalsp = sum
totalsn = sum
sort
for all ties in p.xsn; sort
for i in p:
plot
this produces a curve that travels straight up and then to the right if all motifs in the dataset are predicted correctly.
the curve will travel straight to the right and then up if very few of the motifs are predicted correctly.
finally, if the tool predicts sites correctly as often as it predicts sites incorrectly, a line along the diagonal of the roc graph will be plotted.
however, unlike machine learning algorithms where such a graph is often no better than a random classification of sites, using this method there is some value in graphs along the diagonal because we only allow  <dig> site predictions to be placed on the scaffold.
known motif databases
in mtap, we have implemented interfaces to each of the following databases: regulondb  <cit> , dbtbs  <cit> , prodoric  <cit> , regtransbase  <cit>  and transfac  <cit>  .
each of these databases was constructed with different goals and none were built explicitly to evaluate motif prediction tools.
therefore, some database cleaning is required to make these datasets more appropriate for algorithm assessment.
we provide two procedures:  we require that the known binding site occur in at least nl locations in gj .
mtap will not create upstream files for tfbs that do not meet this threshold.
we provide a script to analyze multiple sequence alignments and information content of a set of known motifs.
we do not require that the tfbs have a consensus sequence as annotated by the database – our logic being that users can eliminate sites without a strong consensus from their analysis by using our information content script and keeping only those sites that exceed a set threshold.
duplicate instances of the same upstream file are eliminated to prevent bias before they are processed by the programs .
mtap does not accept tfbs that do not contain a start and end position in gj.
for tfbs that are inconsistent, users can eliminate the sites and re-score the tfbs.
our primary goal in collecting data is to provide automated methods that can improve as the datasets become more comprehensive.
at this time, both prodoric  <cit>  and regtransbase  <cit>  have very few tfbs with enough binding positions in the same genome gj for us to provide a comprehensive benchmark .
though labor intensive, high annotation density in datasets such as these provides the greatest insight into evaluating computational methods that predict transcription factor binding sites.
RESULTS
in this section we will provide illustrative examples of how our benchmarking technology can be used to evaluate several important parameters in cis-regulatory motif discovery.
to construct a series of tests for evaluation, we extracted  <dig> known transcription factor binding positions from regulondb  <cit>  corresponding to known positions from escherichia coli k <dig>  and  <dig> known motifs from dbtbs  <cit>  corresponding to positions from bacillus subtilis.
then, we extracted  <dig> positions from eukaryote dataset developed by tompa et al.
<cit> .
because regulondb has the most comprehensive coverage, we used regulondb to assess the impact of including two additional genomes .
we used our approach to include regulatory regions from these strains in evaluating phyme and phylogibbs.
our primary goal is to show how mtap can be used to evaluate each of the central questions in cis-regulatory motif discovery.
to illustrate the capabilities of mtap we will use it to evaluate the impact of four of the key factors for regulatory motif discovery introduced earlier in this paper, mainly:  the length of the sequences in the positive and negative sets,  the number of sequences in the positive and negative sets,  the distribution of transcription factor binding sites in the positive set,  the relative entropy of the transcription factor binding motif.
through these illustrative examples we intend to show the exploratory power of mtap towards discovering m → t mappings.
benchmark automation
our first goal was to illustrate that our system of automation can provide similar results to manual runs.
to do this, we downloaded the benchmark results from the tompa assessment and compared these results to results obtained from our pipelines for alignace, ann-spec, glam, meme, and weeder.
results for nsn, nsp, and ssn for our platform versus the tompa benchmarks are shown in figure  <dig>  overall, sensitivity over our dataset is higher, and specificity suffers slightly.
there are a few reasons for this.
first, occasionally experts in the tompa assessment pick a tfbs that is not the highest scoring motif.
we think they do this because of their experience with known tfbs in transfac.
also, mtap allows the top c  predictions to be scored as suggested as an improvement by tompa to increase sensitivity.
the original assessment only allowed the top prediction to be scored.
in many cases, high specificity is obtained by the tool not making a prediction.
consequently, we feel pipelines that increase sensitivity at a low cost to specificity provide a good trade-off.
overall performance is similar over this dataset.
this provides evidence that our automation pipelines work well relative to manual runs by experts.
however, there are still many things better understood by the experts and we continue to refine our pipelines as more information becomes available.
automated assessment
we next used mtap to produce a benchmark over the sites annotated in regulondb.
we chose to run mtap in 'cr' mode over upstream sequences of  <dig> bp .
overall specificity over this dataset is quite high.
this data indicates that tools such as meme and weeder achieve higher sensitivity  without substantial losses to specificity on e. coli tfbs.
summed over all tfbs, ncc ranged from - <dig>  for phylogibbs to  <dig>  for meme.
elph and ann-spec showed the least correlation in this test with a ncc value of  <dig>  each.
overall correlation is extremely weak for any tool in the test.
positive predictive value ranged from  <dig>   to  <dig>   at the nucleotide level and  <dig>   to  <dig>   at the site level.
the low values for nppv and sppv for phyme can be attributed to the large number of sites that phyme did not predict any binding positions.
this behaviour is most likely explained by the large amount of sequence conservation found between the upstream regions in these different strains of e. coli.
it is likely that the multiple sequence alignment step employed by phyme did not encounter enough sequence divergence in this test set to distinguish between regulatory binding positions and background sequence conservation.
the phylogibbs algorithm did not appear to encounter the same difficulties.
however, phylogibbs did not appear to gain a substantial performance gain over weeder even though it had regulatory sequences from related strains and weeder did not.
alignace and ann-spec differ from the other programs in that they sacrifice specificity slightly for increased sensitivity.
over many of the regulatory regions both alignace and ann-spec provided correct predictions somewhere in the list of predicted sites when other tools did not.
in the original tompa assessment, weeder had more discrimination power than other approaches.
while still quite good, weeder does not appear to have the same advantages in this test.
we feel that this gives further evidence that the organism and type of regulatory mechanism greatly impact the expected performance of a tool.
number of upstream sequences
as the upstream size increases relative to the size of the transcription factor binding sites, the background signals found in the dataset also increase.
this makes discrimination of true transcription factor binding positions more default as the number of regulatory regions and length of each region increases.
we wanted to explore the relationship over known transcription factor binding sites.
to discover the relationship between |tl, i| and |Σi tl, i| we set |tl, i| =  <dig> bp and ran pipelines for alignace, annspec, elph, glam, gibbs, meme, phyme, phylogibbs, and weeder .
figure  <dig> shows ncc versus |Σi tl, i|.
as the number of sequences increases, we expect the absolute value of ncc for a tool to increase once the number of co-regulated sequences containing the same signal surpasses some threshold.
once the signal is detected and we continue to increase the number of sequences in the upstream dataset, the absolute value of ncc should decrease as the 'noise' introduced for each added sequence far exceeds the signals.
if this is the case for the regulatory regions in e. coli k <dig>  then the data indicates that  <dig> co-regulated sequences provides enough signal to be detected by many of the tools tested in this assessment.
while ncc is quite low; the performance over this test set does not indicate that regulatory binding sites are more easily detected if we have more instances of them .
it could be that global regulators that have more binding positions over the genome also have more variability in their binding sites.
this makes sense if one considers that each instance of a global regulatory binding site must have a different binding energy to control each of the many genes regulated at different rates.
the regulatory binding positions with the most occurrences indicate a higher ncc averaged over the motif detection tools.
this could be explained by a superior ability of the algorithms to recognize transcription factor binding sites once the number of binding instances is large relative to the length of gj.
figures  <dig> and  <dig> show the site level sensitivity and nucleotide specificity for alignace, annspec, elph, glam, gibbs, meme, phyme, phylogibbs, and weeder with |tk, i| =  <dig> bp.
overall, specificity of these tools maintains a consistent level or increases as the number of sequences in tk increase.
the inverse is true for sensitivity.
as the number of sequences increase, increased instances of regulatory signal does not lead to increased tool sensitivity.
this data indicates that as the number of regulatory signals in the foreground increases linearly, the background 'noise' increases quadratically.
high specificity is most likely the result of increased reluctance on the part of tools to make predictions as the number of sequences increases.
as the number of sequences increases, the number of co-occuring motif instances also increases.
this makes it more likely that multiple occurrences of motif for a related transcription factor may occur in the same upstream set.
this motif cross-talk may play a significant roll in defeating current detection methods.
length of upstream sequences
to further explore the impact of the size of tk, we used mtap to extract  <dig> bp and  <dig> bp upstream regions from motifs found in regulondb and ran pipelines for each of the tools.
most all of the tools did not show any significant correlation between size of tk and prediction performance .
we believe that this indicates a problem with these classification algorithms over the datasets and not to variation in the size of tk.
it could be that these algorithms only classify certain subclasses of regulatory binding profiles accurately.
here we present the results from weeder to demonstrate the impact of varying length of the upstream file.
for weeder, there is a slight impact on performance if the size of tk is varied.
to demonstrate this point, we calculated sensitivity and specificity over the  <dig> largest and smallest upstream files at  <dig> bp and  <dig> bp, respectively .
this data shows that weeder nucleotide specificity is not greatly impaired by the size of the dataset in these tests.
however, we do see a marked decrease in sensitivity both at the nucleotide and site level given larger datasets.
the largest dataset has an average ssp of  <dig>  while the smallest dataset has a average ssp  <dig>  – a substantial difference.
while nsn increases as a trend from smaller to larger tests, the predicted window size is on average much smaller than the motif size resulting in many missed predicted nucleotides.
weeder predicts individual transcription factor binding locations can be detected fairly well up to  <dig> bp over this dataset.
increasing the dataset size further precipitates a steady drop in sensitivity until predictions are no longer useful.
to further understand the impact of upstream length on motif detection performance.
for each tool we ran mtap and generated roc graphs for lengths  <dig> bp,  <dig> bp,  <dig> bp,  <dig> bp,  <dig> bp,  <dig> bp,  <dig> bp, and  <dig> bp upstream of the gene for dbtbs and regulondb.
to understand the roll of data generation methods, we generated both completely-realistic  and semi-realistic  data.
here we provide the results for ann-spec in figure  <dig> which is illustrative of these results.
the most important characteristic of note is between the performance curves of dbtbs  and regulondb .
figure 11c and 11d are more smooth than figures 11a and 11b.
this is because the number of sites in the regulondb dataset is much greater than the number of sites annotated in dbtbs.
commonly, researchers would like to know what motif discovery program is best suited to a particular organism.
these findings suggest that this question can not be addressed currently because of the different amounts of coverage found in each dataset.
if the coverage of tfbs over the genome were greater in dbtbs, the curves in figure  <dig> would show an accurate comparison of the sensitivity-specificity tradeoff in running the ann-spec pipeline on each organism.
figure 11a and 11c refer to semi-realistic data generation .
as the window size increases, there is a precipitous drop in ann-spec's ability to correctly recover the site.
high nsn and nsp are expected at  <dig> bp 'sr' as most any prediction will overlap the true tfbs.
as the window size increases, we expect the performance to remain the same for tools with high recovery rate, but performance should decrease for tools that have poor accuracy.
figure 11c shows a performance drop in nsn and nsp as the length of the upstream sequence increases.
ann-spec does appear to recover many sites regardless of the upstream length as noted by the close cluster of performance graphs on the right hand side of figure 11c.
although similar, 'cr' generated data appears to have higher recovery rates for short windows.
we believe that these recovery rates are most likely related to the relationship between the location of the signal for the tfbs and the location of the signal for the σ <dig> binding site – but this requires more exploration.
site distribution
algorithm practitioners commonly work from the assumption that tfbs have more information than the surrounding sequence.
if this is so, the total number of tfbs in tl  should impact the performance of a tool.
one would expect that a low density of sites would result in higher recovery rates .
to test this, we computed the total number of sites in tl ∀ l as annotated by red.
the site density for tl is the number of sites from red that exist in tl over the number of sequences in tl.
we graphed ssn, nsp and ncc versus density for each of the tools.
for all of the tools, site density did not appear to have any effect on ssn, nsp and ncc over  <dig> bp upstream sequences from regulondb.
figure  <dig> shows no apparent decrease in ncc as the site density increases.
it could be that there does not exist enough complex regulatory regions in e. coli to notice an impact on performance.
it is likely that we would see a different result for organisms with more complex regulatory mechanisms, so we can not rule out site density as a factor in accurate regulatory motif prediction.
these results do indicate that the 'background' signal is far more complex than originally thought and every program has difficulty distinguishing the foreground tfbs from interfering background signals.
site entropy
if the background signals are simple and the binding sites are complex because they must be conserved by evolution, the relative information content of the tfbs should be greater than the information content found in the background signal.
if this is the case, there should be a relationship between the information content of the binding site and prediction accuracy.
to test this, we calculated information content for each site in regulondb using biopython and plotted it against nsn, nsp, ssn,  and ncc .
information content of the site alone does not appear to be a determinative factor in how well these programs can recover the site.
perplexed by this result, we plotted nsn, nsp, ssn, and ncc versus information content divided by the number of upstream sequences in tk .
the result for ssn is shown in figure  <dig>
discussion
the most practical outcome of this work is an ability to rank motif prediction tools based on a known tfbs dataset.
tools with favourable performance characteristics can then be used to discover additional binding sites in closely related genomes or used in conjunction with experimental validation to improve the quality and comprehensiveness of existing tfbs databases.
in regulondb, for example, of the methods tested weeder, meme and alignace present advantages over the other tools.
alignace presents a more diverse list with more false positives whereas weeder and meme present true motif instances more often than the other tools.
motif prediction tools are composed of both a motif scoring function and a discrimination algorithm.
the scoring function accepts a motif representation  and then calculates the motif prediction candidates based on a discrimination function .
discrimination algorithms present a computational strategy to approximate the multiple sequence alignment of predicted binding positions relative to all multiple sequence alignments found in the background signal.
both weeder and alignace have original scoring functions that could explain their utility on regulondb.
meme on the other hand uses expectation maximization as its discrimination algorithm.
it could be that meme benefits from this strategy over programs utilizing gibbs sampling.
on the other hand, it is also likely that the predictions provided by these programs happen to be better over regulondb by random chance.
CONCLUSIONS
in this paper we have presented a general method, mtap, for evaluating cis-regulatory motif discovery tools.
mtap is novel and completely different from other approaches in that it allows both algorithm practitioners and users the flexibility to dynamically change attributes of data collection, algorithm parameters, and assessment.
our results indicate a clear need toward improvements in each of these areas.
in our results, we explored four of the most commonly attributed factors to prediction accuracy: upstream file size, length of upstream sequences, tfbs density, and tfbs information content.
the results obtained by mtap in this assessment do not point toward any of these individual factors as playing a critical roll in finding tfbs.
the results do indicate that the ratio of information content over upstream file size may have an influence on performance for some tools.
the primary innovation in mtap is not that we produce additional tools or additional benchmarks, but it is that we produce a platform that can be used to improve tools and the benchmarking process.
the results presented in this paper indicate that the methods used to prepare upstream data, the algorithm, the parameters, and the method used in evaluation all play important rolls in how we look at the cis-regulatory motif discovery problem.
in the past, many authors have dismissed bacterial regulatory motif detection as a far simpler problem than eukaryote regulatory motif detection .
while it is true that the annotated bacteria regulatory modules do not have the same level of complexity and combinatorial control, our results indicate that even for this 'simple' problem, regulatory motif detection methods have substantial room for improvement.
unlike other approaches, mtap allows for the integration of regulatory regions from other species through an automated procedure.
it remains to be seen which integration procedure and what combination of closely related and distantly related species improves performance for tools that incorporate regulatory regions from phylogentically related species.
this is the subject of future work.
at the moment, it does not appear that two closely related strains are enough to improve performance over conventional single sequence approaches.
it would be interesting to extend our current implementation of mtap and assess tools that integrate data from expression arrays and chip-chip arrays.
such approaches should lead to an increase in performance, but the parameters and procedures for this are not currently clear.
it is not currently understood what features of the data make the problem of finding tfbs so difficult.
the key advantage of mtap is that it allows us to explore these features and propose new models that are more accurate and robust.
it is important to understand the performance characteristics of the models that have been proposed in the past before we integrate additional information.
in this way, we can understand more completely if the relationships found by more sophisticated techniques are real or if they could have occurred by random chance.
further exploration into motif representation, motif scoring, and the relationship between binding sites is still necessary if we are to accurately predict regulatory binding sites on the computer.
competing interests
the authors declare that they have no competing interests.
authors' contributions
dq, ha, and db proposed the design of the system.
kd implemented the prediction pipelines and parsers for each tool.
dq and kd integrated the databases.
dq and ms implemented the system and migrated the system to a clustered environment.
dq, kd and ms tested the system.
dq conducted the computational experiments and wrote the manuscript.
all authors approved the final manuscript.

 the regulation of gene expression in the cell is controlled by regulatory proteins and functional rnas that interact specifically with binding locations on the dna. in the past century, molecular biologists have developed many innovative techniques to identify sites on the dna that are bound and regulated by functional rna and proteins. as the number of sequenced organisms increases, traditional techniques such as gel shift assays in combination with dnase foot-printing assays can not keep pace with the explosion of available sequences. while accurate, traditional methods require a great deal of time and expertise. traditional methods also require that the binding energy of the protein or rna is great enough to maintain contact though the course of the assay. reductionist approaches can be problematic when faced with non-specific binding sites or with sites that require the formation of a complex with adjacent units in order to function. it is for these reasons that complementary approaches on the computer have been developed in recent years to increase success in discovering and annotating cis-regulatory modules. computational discovery of functional subsequences has been around for some time. in galas, eggert, and waterman proposed a method for finding and characterizing binding positions for the σ protein in e. coli promoter sequences. in its most basic form, the problem is identifying sequence signatures, or motifs, that exist in a set of sequences that share the same property, but does not exist in a set of similar sequences that does not have the same property. computational approaches have the advantage that they can reduce the guess work and cost associated with pure biochemical approaches. consequently, many computational methods such as gibbs, meme, consensus, bioprospector, alignace, ann-spec, mtap: the motif tool assessment platform. glam, and weeder have been developed in recent years. each of these methods employs different algorithmic insights and scoring functions. the scoring function and algorithm parameters impact the representation and rank of the motifs discovered by the algorithm. in recent years, it has become clear that each of these computational methods has distinct advantages and that the best performance is achieved by trying multiple methods over the same data set. the bioinformatics community is currently seeking to simplify this situation by providing approaches that integrate multiple methods into one tool such as best and emd. approaches that integrate additional sources of information have also emerged in recent years. for example, approaches such as phyme, phylogibbs, and weederh integrate sequences from regulatory regions of related organisms. other approaches, such as reduce, integrate expression values from gene expression arrays. in addition, the advent of high density arrays and chip-chip technology has necessitated methods that integrate genome wide binding data. while there are many advantages in integrating additional sources of information, the steps required also add additional complexity and cost. each step along the integration pipeline opens a new question: what is the best way to represent and integrate this new data? one has to wonder if additional data is always better in practice. it could be that for some regulatory modules, the additional data also includes additional noise making it more difficult to recover the binding sites. to make matters more confounding, there currently exist more than methods with thousands of possible pre- and post-processing steps and alternative runtime procedures. it is clear that benchmarking technology is needed to map cis-regulatory motif discovery methods to data where the method has the best performance. in other words, given a method m and a set of co-regulated genes with regulatory sequences t = {t t..., tn}, find a mapping m → t with expected performance over some threshold. a t that has no method over the threshold is particularly interesting in that such data can tell us more about the current limitations of regulatory motif discovery programs so that we can propose improvements. in recent years, researchers have begun to solve this problem by creating benchmarking datasets. in tompa et al. published the first assessment of regulatory motif discovery algorithms over fly, human, mouse and yeast. this work was seminal in that it provided methods for comparing regulatory motif detection software and that it benchmarked a large number of popular tools. in sandve et al. improved benchmarking technology over the tompa dataset using a machine learning approach. while these advances opened the important debate on how to benchmark algorithm performance, it remains to be seen if a selection of so few regulatory binding sites is large enough to form a representative set. in response, klepper et al. proposed a larger test set and used it to evaluate several composite motif discovery tools. this is an important first step in making benchmarking datasets more comprehensive. to date, the most comprehensive test set was over the entire e. coli genome using known transcription factors found in regulondb. while bacterial transcription regulation is very different than regulation in eukaryotes, the density of the regulondb annotation is greater than for any other organism and this coverage provides us with unique benchmarking opportunities. unfortunately, this assessment only considered tools and neglected to include the tool most successful in the tompa benchmark. to date, there are no tools that can assess algorithms that incorporate additional sources of data such as sequences from phylogentically related species. currently, cis-regulatory motif tools are assessed using the statistics and methods from gene prediction. however, in silico gene annotation differs from cis-regulatory module annotation in that in gene prediction there exists an mrna library for reference. unlike regulatory binding assays, mrna library sequencing is high throughput and thus provides a large and diverse benchmarking dataset for gene prediction tools. consequently, gene prediction and cis-regulatory module prediction are very different problems. we currently have very few completely annotated regulatory modules and therefore motif prediction tools have very few cases to train. in addition, regulatory modules are thought to evolve at a much faster rate than the genes they regulate. if this theory is true, the diversity of regulatory regions is expected to be far greater than the coding regions they regulate. this means that the parameters, data, transcription module representation and algorithm are all important factors in evaluating motif detection tools. in this work, we expand upon our parallel architecture for regulatory motif prediction and propose a method for evaluation and discovery of data algorithm mappings. mtap is a platform that allows one to vary the way scientists process data and algorithm parameters to fine tune the representation of a regulatory module in method m. the goal is to discover the best possible mapping of m → d. our platform also integrates phylogentically related regulatory sequences via computing downstream orthologs from other species. it is clear that phylogentic footprinting has great potential, however assessing methods that incorporate sequence from closely related species is not practical or accurate without automation. for these reasons, there is a place for adaptive and automatic cis-regulatory motif prediction and benchmarking. problem description a cis-regulatory motif discovery pipeline, mi, contains a series of steps to separate transcription factor binding sites from'background noise'. motif discovery pipelines require collecting the positive example sequences, collecting negative example sequences, collecting relevant supporting data, running a separation filter to rank relevant sites based on an objective function and finally evaluating or verifying putative sites within the context of each regulatory module. several factors outside of the pipeline itself contribute to the potential success of the discovery process, mainly: the length of the sequences in the positive and negative sets, the number of sequences in the positive and negative sets, the distribution of transcription factor binding sites in the positive set, the relative entropy of the transcription factor binding motif, and the fraction of null sequences in the positive set. it is likely there are additional unknown variables that impact the accuracy of an approach. for example, better background sequence models or sequences from closely related species are known to affect performance. our approach to finding the variables, parameters, and algorithms that are best suited to annotating regulatory regions is an adaptive data collection and analysis platform. our hypothesis is that a platform that automates each operation in cis-regulatory motif discovery enables discovery of better methods for cis-regulatory motif prediction. such a platform enables practitioners and users the necessary flexibility to change characteristics of the data and algorithm parameters, and to isolate and understand known challenge cases. in addition, known methods with many manual steps can be made more explicit. presently, it is difficult to benchmark existing approaches because they have a great variety of algorithmic parameters that allow the user to interactively optimize the discovery process. while this approach is advantageous because it provides flexibility in the discovery process, it also presents a challenge in algorithm benchmarking: how to formalize data collection, parameter fine tuning, and other intuitive steps taken by the most experienced users of these methods. from a more practical perspective, one has to wonder what evidence experienced practitioners use to determine a set of algorithm refinement steps that will result in better performance over the new dataset. our hypothesis is that the motif discovery process can be greatly improved if tool parameters are fine tuned based on previous performance benchmarks. we present algorithm benchmarking over a set of known and related transcription factor binding sites as a method to uncover the likely performance on the current dataset. this approach allows the refinement and modification of motif prediction pipelines. in particular, such a benchmarking approach allows for interactive modification of known tfbs in incomplete datasets, modification of the procedures used in collecting positive, negative, and phylogenatically related sequence samples, modification of methods for finding tfbs within the samples, and even modification of the methods used to score motif discovery pipelines. our central hypothesis is that by looking at all components of data and software along the cis-regulatory motif discovery process, we can refine our understanding of regulation and discover pipelines with high accuracy. the way we look at this complex problem is a result of how we collect the data, how we build algorithms for discovering regulatory motifs, the biological and manual processes and data structures used to create comprehensive annotations of cis-regulatory regions, and the methods we choose to use in grading these motif discovery tools. we view each of these components as parts that can and should be modified as the specifics of the biological problem at hand become clear. in this paper, we present a open source prototype for cis-regulatory motif discovery algorithm evaluation. implementation mtap provides an automated method for ranking regulatory motif detection algorithms. the underlying principle is to create a'test', t, and an'answer key', k = {k k...}. k is generated by parsing the raw database management systems of regulondb, dbtbs, prodoric, regtransbase and transfac. the annotated genome, gj, is then parsed for each regulatory binding site annotated in k. tk is a collection of sequences corresponding to the surrounding regions of known binding sites for transcription factor k in gj. tk is composed of l instances of binding positions t t..., tl in gj as annotated by the database. to score a method, mi, we construct an automated pipeline via a scripting language that runs the method. each method has a different algorithmic approach and has different requirements of pre- and post-processing. for each method, we construct background probability models, standardize input datasets, install program dependencies, and provide conversion and utility scripts so that each method can be graded fairly. we consider a fair test to be a test where each program has access to the same information and must mark the transcription factor binding positions in a standard way. this standard marking is then assessed by comparing the annotation of regulatory sites provided by the algorithm with the known annotation in the database. a schematic overview of our assessment method is presented in figure because databases contain many types of binding positions these evaluations are an indication of how well each algorithm can recover the binding positions for each element in the regulatory network and not just transcription factor binding positions. generating upstream sequences varying upstream length allows us to explore the trade off between detecting long range interactions and high prediction accuracy. mtap contains two genome substringing methods for generating upstream sequences as shown in figure'completely-realistic' data generation is best suited to problems that convert gene lists to binding locations.'semi-realistic' data generation is best suited to problems that generate a set of sequences. in most cases'sr' constructed data produces a more fair comparison between pattern finding methods, but is not realistic when the tools are applied to a set of co-regulated loci. completely-realistic data generation is most often the natural choice, but is limited because the upstream file may not contain the motif for long range interactions. also, the'cr' method may select a different downstream gene as part of the data construction procedure. these two issues are realistic in the cis-regulatory motif discovery process and are representative of current problems in cis-regulatory motif discovery. this method is therefore representative of current methods used in constructing co-regulated upstream sequences. future work could be done to make automated upstream data generation more sensitive to these types of issues. the transformation function t applies one of the substring operations to the reference genome gj to produce tk. tk is generated by selecting regulator k and generating an upstream sequence uk, n for all instances of k in gj. figure provides a diagram of several of the stages used to construct t = t t... for all instances of k in gj. despite the fact that tk is constructed by considering only tf k, all of the other transcription factors in the database are marked and scored if they fall within sequence indices for any sequence in tk. generating orthologous upstreams after the upstream file, uk, n, is constructed, mtap collects regulatory sequences from closely related genomes gj+ gj+..., by using downstream orthologs. to do this, mtap constructs a list of all proteins in each genome gj+ gj+.... before the upstream is created, mtap uses as orthalog detection method to create an orthalog table, o. o contains a list of protein products from gj and gj+ and a confidence score oc corresponding to the confidence in the orthology relationship as determined by the ortholog detection method. for each sequence in uk, we select the nearest downstream gene, gi, j ∈ gj. mtap then looks up any entries for gi, j ∈ o. if oc > τ for some constant τ, mtap appends a region n bp upstream of gj+ if multiple entries exist for gi, j, mtap appends the region upstream gj+ i such that oc is greatest. mtap continues this procedure for all genomes gj, gj+.... this procedure is then repeated to construct t t.... an example result is found in figure 4d. several important points should be made about phylogentic foot-printing. first, the existence of a set of regulatory binding sites exists in gj does not imply the existence of the same set of regulatory binding positions in gj+ in the same positions. in our example in figure tk does not contain a binding position for k ∈ gj+ it is possible that our criteria to classify orthologs is too stringent to find an actual ortholog in gj+ notice that in our example tl contains no upstream corresponding to g in gj+ in our example, this occurred because the homology threshold criteria excluded g from gj+ again, these problems will exist in any current automated pipeline used for regulatory motif detection. some of these issues can be resolved within the algorithms themselves: many algorithms incorporate the hypothesis that zero or many instances of the cis-regulatory binding motif exists within the upstream sequence. however, the prospect is very real that we could integrate sequences that are related but do not contain binding sites for transcription factor k. currently, we have very little understanding of the relationship between the evolution of regulatory sequences and coding sequences. it is quite possible that phylogenetically related sequences introduce additional'noise' with very little signal in regulatory sequences for genes that do not provide critical functions. these complex relationships warrant an in-depth study of regulatory evolution as it relates to coding sequence evolution – which is the subject of future work. for now, we wish to use this approach to benchmark single genome methods as they compare to multiple genome based methods. to our knowledge, mtap is the first method that allows additional sources of information to be automatically integrated as part of the evaluation process. constructing background sequences once tk has been constructed for all k, we present three possible background sequence files to motif discovery pipelines: all upstream sequences of length n in gj, all upstream sequences of length n that exist in some tk, and a fasta formated sequence of gj. programs that incorporate phylogeny have different background sequence requirements. such programs require a background phylogenetic tree constructed from extracting 16s rrna from each genome in the study. some programs require pre-processing steps to calculate an hmm or gc content of the test sequences. other programs require a background probability distribution of all upstream sequences in gj. we compute each of these requirements for each pipeline in our pre-processing stage and provide the files to each pipeline. compensating for unknown tfbs unknown tfbs that exist in tk complicate the assessment process. tools could predict true sites that are currently unknown or un-annotated. to exclude unknown sites from tk, we construct a markov chain, mcm,. for each sequence, si, in tk, si is sampled with mcm. we then generate an alternative sequence, s'i, through a random walk through the sates in mcm. for all tfbs in k that overlap si, we insert the true tfbs sequence from si into s'i. in this way, we use mcm to'scramble' the upstream sequences in the test and then re-insert the known motifs back into the sequences at the same positions found in the source genome. it is also informative to have instances of true negative sequences produced via mcm, so we produce instances of tk with no inserted tfbs. orthologous upstream sequences need not be scrambled if they are not scored. these synthetic sequences serve to make a' more fair' test in those cases where very few of the known motifs are marked. however, such sequences may not correctly incorporate the biological process that generates true sequences. to accommodate this, we also insert tfbs into a random sequence from the set of all upstream sequences in gj. constructing motif discovery pipelines in constructing motif discovery pipelines, our intention is to include pipelines for as many tools as possible. however, building parsers, installing scripts, and optimizing a pre-processing, post-processing, and runtime pipeline for each of over programs is extremely labor intensive. our main obstacle is in finding executables that can run on a variety of architectures in a linux cluster. in many cases, we attempted to contact authors to arrange a port of their tool to a linux cluster. many authors are extremely helpful and we would like to thank them for the advice and guidance of how to use and port their tool. however, we realized that even if we have a stand-alone version of a method working on our architecture, mtap users will still need to install many of the tools directly from the authors. our strategy for including a tool is as follows: • include tools that are the most popular. • include tools that present different and novel scoring functions for differentiating background sequences from transcription factor binding sites. • include tools that integrate diverse types of information from public sources. • do not include tools that do not have a downloadable executable or can not be compiled locally, as such tools can not easily be run thousands of times for assessment purposes. • do not include tools that do not have support for different architectures and operating systems. • as we can not redistribute tools with strict licensing agreements or'abandonware', inclusion of such tools is left to the user community. our platform is provided open-source for practitioners who would like to develop their own pipelines to integrate their tool into mtap. this approach has an advantage in that the developer of the tool is also the developer of the pipeline for evaluating the tool. this could provide an edge as the tool developer will understand the limitations and usage procedures best. we provide our assessment pipelines within our framework for open access review and improvement. in this work, we developed pipelines for alignace, ann-spec, elph, gibbs, glam, meme, phylogibbs, phyme, and weeder. for each of these tools in the tompa et. al benchmark, we developed an automated system that was as close to the spirit of the procedure used by the algorithm practitioners as practical. for example, our alignace pipeline contains a pre-processing script for calculating gc content of the upstream file and a postprocessing script to mask low complexity repeats using repeatmasker. the pipeline then parses the raw alignace output which results in a ranked list of predicted transcription factor binding sites sorted via the alignace map score. the pipeline accepts the highest c scoring motifs by map score and then determines confidence by calculating the group specificity score as provided by compareace. a high group specificity score and map score indicates a high degree of confidence in the prediction provided by the alignace pipeline. for those tools that are not in the tompa assessment, we carefully followed the usage guides and refined our pipelines using mtap to produce the best results possible. for some methods, the code is not available and the method paper does not make it clear if certain data preparation procedures can be accommodated by the method. for example, some methods account for upstream sequences that are reverse complemented while others do not. some methods account for zero, one, or many motif instances on one strand while others do not. some methods allow for variable motif widths, while others require an explicit window. we assume that motif discovery pipelines are sufficiently robust to account for these technical details and we attempted to make our pipelines robust in this way. however, in constructing these pipelines in this way, we may have overlooked some aspects of the algorithmic approach that would make our pipelines not representative of the original author intent. we addressed this issue in two ways. first, we built pipelines for multiple implementations of similar approaches. second, we refined each pipeline based on the objective function found in the literature and the benchmarks obtained via mtap. to guard against over-fitting of a pipeline to a certain dataset, we did not allow modification of the code or implementation of any procedures not recommended explicitly by the authors. we performed benchmarks over the tompa assessment datasets, regulondb, and dbtbs and selected transcription factors at random to validate if the proposed change improved results. as the search space is large, there may exist a set of pre-processing, post-processing, and runtime steps that may improve the performance of our current pipelines. if used in this way, mtap provides the framework for method developers and method users to formalize and improve motif discovery pipelines. pipeline evaluation three levels of specificity can be considered when evaluating the accuracy of mi: mi correctly predicts the region bound by some transcription factor k, mi correctly predicts the binding site of k, and mi correctly predicts the amino acids in tf that interact with specific nucleotides within the regulatory region. mi may also correctly predict the type and strength of the interactions. predictions of type are analogous to a gel shift assay in that we can identify a part of the regulatory region bound by a protein. predictions of type are analogous to a dna foot-printing assay. predictions of type are more specific in that each region of interaction between k and the dna is identified. for example, if a transcription factor is a dimer, two interaction sites are identified by predictions of type whereas only one interaction site is identified by a prediction of type. the third type of prediction is analogous to determining the crystal structure interaction points of the transcription factor – dna complex. while the specificity and information provided by the third type of prediction is far greater than annotations of type or type such data is difficult to obtain and few methods make predictions at this level. we therefore generate two annotation files: a'redfile' and a'blackfile' corresponding to the site level and region level respectively. to generate an upstream file, we use the blackfile annotation. to assess the performance of an algorithm we evaluate the predictions versus the redfile annotation. the redfile annotation red = i i... contains a set of intervals ik =,,... that correspond to the start and stop positions in gj corresponding to binding locations for transcription factor k. to compare the redfile annotation to the motif tool predictions, ui is used as a scaffold to place annotation elements. to annotate the known sites at the nucleotide level, we mark each base, j, in ui if uh ≤ j ≤ vh ∀ k. the predicted binding locations, bk,u,vu, predicted by mi are parsed and translated into a ranked list of predicted binding sites, each of the form bk u v1u,bk u v...u. the ranked list contains elements tfl tfl... sorted according to the confidence that mi has in the prediction accuracy. mtap accepts the top c elements from the rank list for evaluation and inserts them onto the upstream scaffold. mtap then marks each position, j, as a predicted nucleotide if there exists some predicted binding site, b, that overlaps it. at the nucleotide level, we collect the overlap statistics shown in table the first four core statistics are collected by summing the number of each of the occurrences shown in table in tk. the site level statistics are the final three core statistics provided by mtap. a site level statistic encompasses the idea that a group of adjacent nucleotides marked as binding positions for transcription factor k by mi is representative of a binding site annotation. a site is annotated as a true positive if bk,u,vui overlaps ix ∀ x by more than τ percent of ix. for example, consider two overlapping sites, a known site ix of consecutive nucleotides and a predicted site b of consecutive nucleotides. given τ =. if ix shares nucleotides with b it is annotated as a stp. if ix shares only nucleotides with b it is annotated as a sfp. once a site, ix, overlaps a prediction, it can not be annotated as a sfn. all remaining sites, i i..., ix, that do not have an overlapping prediction for tool mi are annotated as sfn. the site level statistics are in table tompa et. al set τ to 25%. the logic was that such an overlap makes discovery and refinement of the tfbs possible in the lab. in large scale genome annotations, we find such a threshold to be too strict. for example, many tfbs are not annotated specific enough in databases such as regulondb. this results in tfbs that exist in k that can be large. such annotations are actually representative of the region of binding of the transcription factor and not the binding sites. because many motif discovery programs have fixed motif widths, a threshold of 25\% would not be sufficient to mark a stp. we could choose to rank site level motifs based on a percentage of the prediction width instead of the regulatory motif width, but this would give an unfair advantage to methods that predict larger sites. our current approach is to set τ equal to the maximum annotated site width in the dataset divided by the minimum expected motif width predicted by our suite of programs times 25%. our logic is that a degree of overlap indicates that computational and biological refinement of site predictions can still find the site. that said, manual curation of datasets to ensure binding site annotations rather than region annotations is necessary. standards across regulatory binding site databases to delineate each of the three levels of biological data would greatly increase evaluation accuracy of motif discovery tools. also, as not all tools provide a mapping for a set of sites to a putative regulator, these statistics are currently not reflective of which regulator is annotated by a site level prediction. following tompa et. al we define the statistics in figure to perform the assessment. these statistics enable us to determine the quality of algorithm predictions and therefore infer which tools may be best suited to discover unknown motifs under similar situations. mtap evaluates each of these statistics by comparing the predictions found in the program output with a set of known binding positions of the same type. for each instance found in the known dataset, a motif prediction tool is run and then parsed. the prediction is compared to the known binding site via the seven key statistics in table and table these statistics will then be used to assess the overall performance of the algorithm. mtap produces an output file for each regulatory binding motif in k. users can sum the raw statistics in these files as they see fit. for this paper, we collect the seven raw performance statistics for each motif in the assessment and then sum these values as if the collection of runs was actually one run. in some cases, such sums do not graphically represent the contribution of each element in the set to the total performance score. to address this, we also developed a graph that iterates over all runs in the test the graph produced is a modified receiver operating characteristic curve that combines statistics from multiple runs. we use the following algorithm to produce our roc graphs:    for each motif in the dataset:       input xtp, xfp, nfn, ntn, stp, sfp, sfn       p < -calculate xsp and xsn for this motif    for all motifs in the dataset:       totalsp = sum       totalsn = sum    sort    for all ties in p.xsn; sort    for i in p:       plot this produces a curve that travels straight up and then to the right if all motifs in the dataset are predicted correctly. the curve will travel straight to the right and then up if very few of the motifs are predicted correctly. finally, if the tool predicts sites correctly as often as it predicts sites incorrectly, a line along the diagonal of the roc graph will be plotted. however, unlike machine learning algorithms where such a graph is often no better than a random classification of sites, using this method there is some value in graphs along the diagonal because we only allow site predictions to be placed on the scaffold. known motif databases in mtap, we have implemented interfaces to each of the following databases: regulondb, dbtbs, prodoric, regtransbase and transfac. each of these databases was constructed with different goals and none were built explicitly to evaluate motif prediction tools. therefore, some database cleaning is required to make these datasets more appropriate for algorithm assessment. we provide two procedures: we require that the known binding site occur in at least nl locations in gj. mtap will not create upstream files for tfbs that do not meet this threshold. we provide a script to analyze multiple sequence alignments and information content of a set of known motifs. we do not require that the tfbs have a consensus sequence as annotated by the database – our logic being that users can eliminate sites without a strong consensus from their analysis by using our information content script and keeping only those sites that exceed a set threshold. duplicate instances of the same upstream file are eliminated to prevent bias before they are processed by the programs. mtap does not accept tfbs that do not contain a start and end position in gj. for tfbs that are inconsistent, users can eliminate the sites and re-score the tfbs. our primary goal in collecting data is to provide automated methods that can improve as the datasets become more comprehensive. at this time, both prodoric and regtransbase have very few tfbs with enough binding positions in the same genome gj for us to provide a comprehensive benchmark. though labor intensive, high annotation density in datasets such as these provides the greatest insight into evaluating computational methods that predict transcription factor binding sites.  in this section we will provide illustrative examples of how our benchmarking technology can be used to evaluate several important parameters in cis-regulatory motif discovery. to construct a series of tests for evaluation, we extracted known transcription factor binding positions from regulondb corresponding to known positions from escherichia coli k and known motifs from dbtbs corresponding to positions from bacillus subtilis. then, we extracted positions from eukaryote dataset developed by tompa et al.. because regulondb has the most comprehensive coverage, we used regulondb to assess the impact of including two additional genomes. we used our approach to include regulatory regions from these strains in evaluating phyme and phylogibbs. our primary goal is to show how mtap can be used to evaluate each of the central questions in cis-regulatory motif discovery. to illustrate the capabilities of mtap we will use it to evaluate the impact of four of the key factors for regulatory motif discovery introduced earlier in this paper, mainly: the length of the sequences in the positive and negative sets, the number of sequences in the positive and negative sets, the distribution of transcription factor binding sites in the positive set, the relative entropy of the transcription factor binding motif. through these illustrative examples we intend to show the exploratory power of mtap towards discovering m → t mappings. benchmark automation our first goal was to illustrate that our system of automation can provide similar results to manual runs. to do this, we downloaded the benchmark results from the tompa assessment and compared these results to results obtained from our pipelines for alignace, ann-spec, glam, meme, and weeder. results for nsn, nsp, and ssn for our platform versus the tompa benchmarks are shown in figure overall, sensitivity over our dataset is higher, and specificity suffers slightly. there are a few reasons for this. first, occasionally experts in the tompa assessment pick a tfbs that is not the highest scoring motif. we think they do this because of their experience with known tfbs in transfac. also, mtap allows the top c predictions to be scored as suggested as an improvement by tompa to increase sensitivity. the original assessment only allowed the top prediction to be scored. in many cases, high specificity is obtained by the tool not making a prediction. consequently, we feel pipelines that increase sensitivity at a low cost to specificity provide a good trade-off. overall performance is similar over this dataset. this provides evidence that our automation pipelines work well relative to manual runs by experts. however, there are still many things better understood by the experts and we continue to refine our pipelines as more information becomes available. automated assessment we next used mtap to produce a benchmark over the sites annotated in regulondb. we chose to run mtap in'cr' mode over upstream sequences of bp. overall specificity over this dataset is quite high. this data indicates that tools such as meme and weeder achieve higher sensitivity without substantial losses to specificity on e. coli tfbs. summed over all tfbs, ncc ranged from - for phylogibbs to for meme. elph and ann-spec showed the least correlation in this test with a ncc value of each. overall correlation is extremely weak for any tool in the test. positive predictive value ranged from to at the nucleotide level and to at the site level. the low values for nppv and sppv for phyme can be attributed to the large number of sites that phyme did not predict any binding positions. this behaviour is most likely explained by the large amount of sequence conservation found between the upstream regions in these different strains of e. coli. it is likely that the multiple sequence alignment step employed by phyme did not encounter enough sequence divergence in this test set to distinguish between regulatory binding positions and background sequence conservation. the phylogibbs algorithm did not appear to encounter the same difficulties. however, phylogibbs did not appear to gain a substantial performance gain over weeder even though it had regulatory sequences from related strains and weeder did not. alignace and ann-spec differ from the other programs in that they sacrifice specificity slightly for increased sensitivity. over many of the regulatory regions both alignace and ann-spec provided correct predictions somewhere in the list of predicted sites when other tools did not. in the original tompa assessment, weeder had more discrimination power than other approaches. while still quite good, weeder does not appear to have the same advantages in this test. we feel that this gives further evidence that the organism and type of regulatory mechanism greatly impact the expected performance of a tool. number of upstream sequences as the upstream size increases relative to the size of the transcription factor binding sites, the background signals found in the dataset also increase. this makes discrimination of true transcription factor binding positions more default as the number of regulatory regions and length of each region increases. we wanted to explore the relationship over known transcription factor binding sites. to discover the relationship between |tl, i| and |Σi tl, i| we set |tl, i| = bp and ran pipelines for alignace, annspec, elph, glam, gibbs, meme, phyme, phylogibbs, and weeder. figure shows ncc versus |Σi tl, i|. as the number of sequences increases, we expect the absolute value of ncc for a tool to increase once the number of co-regulated sequences containing the same signal surpasses some threshold. once the signal is detected and we continue to increase the number of sequences in the upstream dataset, the absolute value of ncc should decrease as the'noise' introduced for each added sequence far exceeds the signals. if this is the case for the regulatory regions in e. coli k then the data indicates that co-regulated sequences provides enough signal to be detected by many of the tools tested in this assessment. while ncc is quite low; the performance over this test set does not indicate that regulatory binding sites are more easily detected if we have more instances of them. it could be that global regulators that have more binding positions over the genome also have more variability in their binding sites. this makes sense if one considers that each instance of a global regulatory binding site must have a different binding energy to control each of the many genes regulated at different rates. the regulatory binding positions with the most occurrences indicate a higher ncc averaged over the motif detection tools. this could be explained by a superior ability of the algorithms to recognize transcription factor binding sites once the number of binding instances is large relative to the length of gj. figures and show the site level sensitivity and nucleotide specificity for alignace, annspec, elph, glam, gibbs, meme, phyme, phylogibbs, and weeder with |tk, i| = bp. overall, specificity of these tools maintains a consistent level or increases as the number of sequences in tk increase. the inverse is true for sensitivity. as the number of sequences increase, increased instances of regulatory signal does not lead to increased tool sensitivity. this data indicates that as the number of regulatory signals in the foreground increases linearly, the background'noise' increases quadratically. high specificity is most likely the result of increased reluctance on the part of tools to make predictions as the number of sequences increases. as the number of sequences increases, the number of co-occuring motif instances also increases. this makes it more likely that multiple occurrences of motif for a related transcription factor may occur in the same upstream set. this motif cross-talk may play a significant roll in defeating current detection methods. length of upstream sequences to further explore the impact of the size of tk, we used mtap to extract bp and bp upstream regions from motifs found in regulondb and ran pipelines for each of the tools. most all of the tools did not show any significant correlation between size of tk and prediction performance. we believe that this indicates a problem with these classification algorithms over the datasets and not to variation in the size of tk. it could be that these algorithms only classify certain subclasses of regulatory binding profiles accurately. here we present the results from weeder to demonstrate the impact of varying length of the upstream file. for weeder, there is a slight impact on performance if the size of tk is varied. to demonstrate this point, we calculated sensitivity and specificity over the largest and smallest upstream files at bp and bp, respectively. this data shows that weeder nucleotide specificity is not greatly impaired by the size of the dataset in these tests. however, we do see a marked decrease in sensitivity both at the nucleotide and site level given larger datasets. the largest dataset has an average ssp of while the smallest dataset has a average ssp – a substantial difference. while nsn increases as a trend from smaller to larger tests, the predicted window size is on average much smaller than the motif size resulting in many missed predicted nucleotides. weeder predicts individual transcription factor binding locations can be detected fairly well up to bp over this dataset. increasing the dataset size further precipitates a steady drop in sensitivity until predictions are no longer useful. to further understand the impact of upstream length on motif detection performance. for each tool we ran mtap and generated roc graphs for lengths bp, bp, bp, bp, bp, bp, bp, and bp upstream of the gene for dbtbs and regulondb. to understand the roll of data generation methods, we generated both completely-realistic and semi-realistic data. here we provide the results for ann-spec in figure which is illustrative of these results. the most important characteristic of note is between the performance curves of dbtbs and regulondb. figure 11c and 11d are more smooth than figures 11a and 11b. this is because the number of sites in the regulondb dataset is much greater than the number of sites annotated in dbtbs. commonly, researchers would like to know what motif discovery program is best suited to a particular organism. these findings suggest that this question can not be addressed currently because of the different amounts of coverage found in each dataset. if the coverage of tfbs over the genome were greater in dbtbs, the curves in figure would show an accurate comparison of the sensitivity-specificity tradeoff in running the ann-spec pipeline on each organism. figure 11a and 11c refer to semi-realistic data generation. as the window size increases, there is a precipitous drop in ann-spec's ability to correctly recover the site. high nsn and nsp are expected at bp'sr' as most any prediction will overlap the true tfbs. as the window size increases, we expect the performance to remain the same for tools with high recovery rate, but performance should decrease for tools that have poor accuracy. figure 11c shows a performance drop in nsn and nsp as the length of the upstream sequence increases. ann-spec does appear to recover many sites regardless of the upstream length as noted by the close cluster of performance graphs on the right hand side of figure 11c. although similar,'cr' generated data appears to have higher recovery rates for short windows. we believe that these recovery rates are most likely related to the relationship between the location of the signal for the tfbs and the location of the signal for the σ binding site – but this requires more exploration. site distribution algorithm practitioners commonly work from the assumption that tfbs have more information than the surrounding sequence. if this is so, the total number of tfbs in tl should impact the performance of a tool. one would expect that a low density of sites would result in higher recovery rates. to test this, we computed the total number of sites in tl ∀ l as annotated by red. the site density for tl is the number of sites from red that exist in tl over the number of sequences in tl. we graphed ssn, nsp and ncc versus density for each of the tools. for all of the tools, site density did not appear to have any effect on ssn, nsp and ncc over bp upstream sequences from regulondb. figure shows no apparent decrease in ncc as the site density increases. it could be that there does not exist enough complex regulatory regions in e. coli to notice an impact on performance. it is likely that we would see a different result for organisms with more complex regulatory mechanisms, so we can not rule out site density as a factor in accurate regulatory motif prediction. these results do indicate that the'background' signal is far more complex than originally thought and every program has difficulty distinguishing the foreground tfbs from interfering background signals. site entropy if the background signals are simple and the binding sites are complex because they must be conserved by evolution, the relative information content of the tfbs should be greater than the information content found in the background signal. if this is the case, there should be a relationship between the information content of the binding site and prediction accuracy. to test this, we calculated information content for each site in regulondb using biopython and plotted it against nsn, nsp, ssn, and ncc. information content of the site alone does not appear to be a determinative factor in how well these programs can recover the site. perplexed by this result, we plotted nsn, nsp, ssn, and ncc versus information content divided by the number of upstream sequences in tk. the result for ssn is shown in figure discussion the most practical outcome of this work is an ability to rank motif prediction tools based on a known tfbs dataset. tools with favourable performance characteristics can then be used to discover additional binding sites in closely related genomes or used in conjunction with experimental validation to improve the quality and comprehensiveness of existing tfbs databases. in regulondb, for example, of the methods tested weeder, meme and alignace present advantages over the other tools. alignace presents a more diverse list with more false positives whereas weeder and meme present true motif instances more often than the other tools. motif prediction tools are composed of both a motif scoring function and a discrimination algorithm. the scoring function accepts a motif representation and then calculates the motif prediction candidates based on a discrimination function. discrimination algorithms present a computational strategy to approximate the multiple sequence alignment of predicted binding positions relative to all multiple sequence alignments found in the background signal. both weeder and alignace have original scoring functions that could explain their utility on regulondb. meme on the other hand uses expectation maximization as its discrimination algorithm. it could be that meme benefits from this strategy over programs utilizing gibbs sampling. on the other hand, it is also likely that the predictions provided by these programs happen to be better over regulondb by random chance.  in this paper we have presented a general method, mtap, for evaluating cis-regulatory motif discovery tools. mtap is novel and completely different from other approaches in that it allows both algorithm practitioners and users the flexibility to dynamically change attributes of data collection, algorithm parameters, and assessment. our results indicate a clear need toward improvements in each of these areas. in our results, we explored four of the most commonly attributed factors to prediction accuracy: upstream file size, length of upstream sequences, tfbs density, and tfbs information content. the results obtained by mtap in this assessment do not point toward any of these individual factors as playing a critical roll in finding tfbs. the results do indicate that the ratio of information content over upstream file size may have an influence on performance for some tools. the primary innovation in mtap is not that we produce additional tools or additional benchmarks, but it is that we produce a platform that can be used to improve tools and the benchmarking process. the results presented in this paper indicate that the methods used to prepare upstream data, the algorithm, the parameters, and the method used in evaluation all play important rolls in how we look at the cis-regulatory motif discovery problem. in the past, many authors have dismissed bacterial regulatory motif detection as a far simpler problem than eukaryote regulatory motif detection. while it is true that the annotated bacteria regulatory modules do not have the same level of complexity and combinatorial control, our results indicate that even for this'simple' problem, regulatory motif detection methods have substantial room for improvement. unlike other approaches, mtap allows for the integration of regulatory regions from other species through an automated procedure. it remains to be seen which integration procedure and what combination of closely related and distantly related species improves performance for tools that incorporate regulatory regions from phylogentically related species. this is the subject of future work. at the moment, it does not appear that two closely related strains are enough to improve performance over conventional single sequence approaches. it would be interesting to extend our current implementation of mtap and assess tools that integrate data from expression arrays and chip-chip arrays. such approaches should lead to an increase in performance, but the parameters and procedures for this are not currently clear. it is not currently understood what features of the data make the problem of finding tfbs so difficult. the key advantage of mtap is that it allows us to explore these features and propose new models that are more accurate and robust. it is important to understand the performance characteristics of the models that have been proposed in the past before we integrate additional information. in this way, we can understand more completely if the relationships found by more sophisticated techniques are real or if they could have occurred by random chance. further exploration into motif representation, motif scoring, and the relationship between binding sites is still necessary if we are to accurately predict regulatory binding sites on the computer. competing interests the authors declare that they have no competing interests. authors' contributions dq, ha, and db proposed the design of the system. kd implemented the prediction pipelines and parsers for each tool. dq and kd integrated the databases. dq and ms implemented the system and migrated the system to a clustered environment. dq, kd and ms tested the system. dq conducted the computational experiments and wrote the manuscript. all authors approved the final manuscript. 
as the number of software packages increases, it becomes more important to identify the tools with the best performance characteristics for specific problem domains. as a proof of concept, we have run benchmarks over human, mouse, fly, yeast, e. coli and b. subtilis. in recent years, substantial effort has been applied to de novo regulatory motif discovery.
 in recent years, substantial effort has been applied to de novo regulatory motif discovery. at this time, more than software tools exist to detect regulatory binding sites given a set of genomic sequences. as the number of software packages increases, it becomes more important to identify the tools with the best performance characteristics for specific problem domains. identifying the correct tool is difficult because of the great variability in motif detection software. consequently, many labs spend considerable effort testing methods to find one that works well in their problem of interest.  in this work, we propose a method that substantially reduces the effort required to assess de novo regulatory motif discovery software. mtap differs from previous attempts at regulatory motif assessment in that it automates motif discovery tool pipelines, automatically constructs orthologous upstream sequences, and provides automated benchmarks for many popular tools. as a proof of concept, we have run benchmarks over human, mouse, fly, yeast, e. coli and b. subtilis.  mtap presents a new approach to the challenging problem of assessing regulatory motif discovery methods. the most current version of mtap can be downloaded from 23– february fifth annual mcbios conference. systems biology: bridging the omics oklahoma city, ok, usa 