to understand how cells read off information from the genome at the right time at the right position , we have to learn the sequence motifs that the regulatory factors recognize and bind to .
a large variety of experimental methods yield sequences that are enriched in binding sites of regulatory factors
. methods that can discover these enriched motifs have therefore proven to be of great practical importance for modern biological research and a multitude of motif discovery methods have been developed ( 14 ) .
most of the tools can only be run on the command line , making them inaccessible to the majority of biologists .
the most popular one is the meme suite server ( 5 ) , within which the position weight matrix ( pwm)-based meme and glam2 motif discovery programs can be run ( 6,7 ) , alongside several related tools to compare the discovered motifs with libraries of literature motifs and to search for matches to the discovered motifs in sequence databases . with a higher order background model to describe sequences that should not carry the sought motifs , meme has shown state - of - the - art performance ( 8) . to use higher order models , users have to upload their own model file generated using a meme command line tool , which will limit most users to the zero - order model with lower sensitivity .
the scope web server combines three pattern - based motif discovery tools , which are specialized to find non - degenerate , degenerate and gapped motifs , into a single prediction using a  winner takes all learning rule ( 9 ) .
the reganalyst server runs a motif discovery method that searches for the most enriched patterns using fixed thresholds for the maximum number of allowed mismatches .
it was originally developed for mycobacterial and yeast sequences , on which it was reported to have higher sensitivity than scope ( 10 ) .
the webmotifs server takes gene names from human , mouse or saccharomyces cerevisiae as input , extracts promoter sequences , launches four motif discovery programs and displays the results in a uniform format ( 11 ) .
rsat is a web toolbox for regulatory sequence analysis that also offers several simple tools and gibbs sampling for motif discovery ( 12 ) .
finally , amadeus ( 13 ) is a software tool with a nicely designed graphical user interface that presents an alternative to these web services .
although various published tools can score conservation in multiple sequence alignments of related species and a few can exploit the positional clustering of motifs , to our knowledge , none of the web services offers this useful functionality .
in contrast , the xxmotif web server can combine enrichment p - values for pwms with p - values for sequence conservation and for positional clustering of motif occurrences .
the binding site motifs of regulatory factors are described either with pwms or with patterns , such as consensus sequences with degenerate iupac characters , sometimes allowing for mismatches ( 14 ) .
a pwm is a statistical model  represented by 4    l matrix  that has weights for the four bases at each of the l binding sites positions .
in contrast to patterns that either do or do not match , a pwm gives a more nuanced description of the binding affinity landscape . from a thermodynamic point of view
, a pwm approximates the binding energy under the assumption that each position contributes independently of the others .
although it is straightforward to calculate enrichment p - values for patterns , this is more challenging to do for pmws and usually involves time - consuming random sampling .
therefore , all pwm - based methods to date have taken a likelihood - based approach for finding enriched pwms .
xxmotif is the first pwm - based method to directly optimize the motif enrichment p - value in its pwm stage .
xxmotif consists of three stages : a masking stage , a pattern stage , and a pwm stage . in the masking stage ,
when parts of sequences in the input set are identical or similar over longer regions , this region can give rise to a significant motif even if just these two occurrences are observed .
the reason is that the motif is so long and informative that it would be very unlikely to observe even two such motifs by chance .
hence , to avoid reporting false motifs stemming from regions of local homology , xxmotif masks regions of local homology found by an all - against - all sequence comparison using blast . for similar reasons ,
xxmasker also masks perfect repeats of length 50 or more base pairs . in the pattern stage , xxmotif calculates enrichment p - values for seed patterns , consisting of all 5-mers with up to two degenerate iupac characters , and all palindromic and tandemic 6-mer seeds with gaps up to size 11 . for each seed pattern
, an enrichment p - value is calculated using a binomial distribution and a length- and gap - dependent bonferroni correction factor . for each non - degenerate seed
( i.e. without iupac characters ) , the five most significant matching iupac seed patterns are extended , allowing gaps of up to 3 , until the p - value can not be improved anymore .
iupac strings are then converted to pwms by counting the nucleotides at each position in the matching sequence segments . in the pwm stage ,
thousands of candidate pwms are iteratively optimized : similar pwms are merged , and pwms are extended ( allowing gaps up to 2 ) or shortened , until their enrichment p - value can not be improved anymore .
enrichment p - values give the statistical significance of the enrichment of a pwm in the positive sequence set compared with the expectation derived from the background model .
enrichment p - values are calculated from the single - site p - values for each possible motif position .
a single - site p - value quantifies the significance of the match of a single site to the pwm .
it is the probability that a random site ( generated from the background model ) will obtain at least the same score .
hence , the better the pwm score of the single site , the more significant and the nearer to zero is its single - site p - value .
we developed an efficient branch - and - bound algorithm to compute the single - site p - values for all sites in the positive sequence set .
the enrichment p - value is calculated from all single - site p - values in the input sequences using order statistics : the enrichment p - value is the probability to obtain by chance on a same - size set of background sequences at least k out of n possible motif positions with better single - site p - values than the kth single - site p - value actually observed .
finally , the enrichment p - value can be combined with the p - values for conservation and localization into a total p - value .
e - values are obtained by multiplying the total motif p - values with a bonferroni - like correction factor , which penalizes model complexity similar to the akaike information criterion . for a detailed description ,
guthoehrlein , m. siebert , s. luehr and j. sding , submitted for publication ) .
xxmotif has been compared with various versions of five state - of - the - art methods for motif discovery ( meme ( 7 ) , weeder ( 15 ) , priority ( 16 ) , amadeus ( 5 ) and ermit ( 17 ) ) on a standard benchmark set containing 352 datasets of chip - enriched sequences from s. cerevisiae ( 18 ) , and the other containing 34 sets of metazoan sequences obtained with a wide range of experimental approaches ( 5 ) .
xxmotif showed 2050% higher sensitivity ( number of correctly identified motifs ) than the other tools on the harbison datasets ( 18 ) and 15300% on the metazoan datasets .
the quality of the reported pwms was measured in a partial area under receiver operating characteristic curve ( pauc ) analysis and showed between 30 and 75% higher values than the other tools ( h. hartmann , e.w .
guthoehrlein , m. siebert , s. luehr and j. sding , submitted for publication ) .
on the  data upload page ( figure 1a ) , users can enter the input sequence set and an optional background sequence set ( up to 25 mb per file ) .
the background sequences are used to learn the statistical background model , which describes how 
xxmotif will then try to find motifs that are enriched in the input set in comparison to the expectation derived from the background model .
when no background sequences are supplied , a second - order background model is trained from the input sequences . 

figure 1.pages for submitting a job to the xxmotif web server : ( a ) upload input and background sequence sets , ( b ) set options for the motif search and ( c ) verify and submit .
pages for submitting a job to the xxmotif web server : ( a ) upload input and background sequence sets , ( b ) set options for the motif search and ( c ) verify and submit .
it should have a trinucleotide distribution similar to the positive sequences while not being enriched for the motifs we seek . more concretely
, the background set should have a similar mono- , di- and trinucleotide composition as the positive set .
if this is not the case , xxmotif may run very slowly  because it tries to extend sequences too much  and it may produce falsely significant motifs . if in doubt , it is better to omit the background set altogether and to let xxmotif learn the background model from the positive set .
we are about to add an automatic quality test that will warn the user if the background set is not well chosen . to increase the sensitivity of the motif search , xxmotif can calculate motif conservation p - values during the search , which are combined with the enrichment p - values . in this case
, the user can upload a set of input and background multiple sequence alignments , using the  multiple fasta format . on the  options page , the suggested
first , the user can specify how many motif occurrences per input sequence are expected . for most transcription factor and microrna binding sites
, we would expect multiple occurrences , for example . for core promoter motifs or splice sites
when selecting the latter option , only the best occurrence per sequence is scored , whereas with the former option , all occurrences above a certain single - site significance p - value are scored . searching on both strands
is recommended for all motifs that should occur with similar probabilities on both strands ( i.e. as reverse complements of each other ) .
this is true for most transcription factor and microrna binding sites , for example , but not for core promoter or splice site motifs .
the order of the background model specifies how long the patterns are that xxmotif learns from the background sequence set .
an eighth - order model learns the frequencies of 9-mer nucleotides to model the correlations between nearby nucleotides .
this is the default option selected when a background set is supplied by the user . when the background model is learned from the positive set , the default order is set to 2 .
if we were to train a model of order 8 from the positive set , no motif shorter than 10 nucleotides could become significant . under 
advanced options , the user can first specify one of three similarity thresholds for merging motifs ( low , medium and high ) . setting this threshold to
 high will produce longer lists of motifs consisting of groups of similar , partially redundant motifs , which were not similar enough to be merged with each other . setting the threshold to 
low will produce shorter , non - redundant lists of motifs , as similar motifs are merged into a single pwm . however , to be able to discern pwms of factors with similar binding affinities , the 
high threshold is preferable , as it prevents xxmotif from merging the similar but distinct motifs .
the user can further specify which 5-mer and 6-mer patterns are evaluated as seed patterns to initiate the search
. the number of uninformative ( gap ) positions in the 5-mer seeds can also be set .
when setting this parameter to 1 , all seeds of the types xxxxx , xnxxxx , xxnxxx , xxxnxx and xxxxnx will be assessed , for example , where x stands for an informative position and
n stands for  any nucleotide. usually , it is sufficient to choose zero here .
xxmotif also allows changing the amount of pseudocounts added to the nucleotide counts in motif occurrences .
the addition of pseudocounts ensures that the pwm constructed from the motif occurrences in the positive set can predict motif occurrences in new datasets better than without pseudocounts .
the xxmasker tool can be switched off , which masks repeat regions and regions of local homology ( see method summary section ) . upon pressing 
next step , a summary of all selected options is presented ( figure 1c ) , and corrections can be made using the  back button .
after job submission , the user is directed to a status page , which can be bookmarked and automatically redirects to the results page when the job is finished . if the user has provided an email address , a notification with the result page url is sent .
run time scales approximately linearly with the average sequence length and the number of sequences in the positive sequence set .
the results page lists the web logos , e - values and number of sites of matched motifs found up to an e - value of 100 ( figure 2a ) .
when both strands were searched , the reverse complement versions of the motifs are also plotted .
figure 2.sample results with boxes that can be expanded with the orange buttons on the left .
( a ) summary list of discovered motifs sorted by significance ( e - value ) .
( b ) the  multi distribution plot depicts positions and strand of motif occurrences on the input sequences .
the single - site p - values are represented by the height of the box , their length corresponds to the motif length .
( c ) the  localization plot is a histogram view of the positional distribution of selected motifs relative to an anchor point .
sample results with boxes that can be expanded with the orange buttons on the left .
( a ) summary list of discovered motifs sorted by significance ( e - value ) .
( b ) the  multi distribution plot depicts positions and strand of motif occurrences on the input sequences .
the single - site p - values are represented by the height of the box , their length corresponds to the motif length .
( c ) the  localization plot is a histogram view of the positional distribution of selected motifs relative to an anchor point .
multi distribution plot ( figure 2b ) depicts with colored boxes the position and strand of significant motif occurrences within the input sequences .
the motifs to display in this plot can be selected by the user in the upper part of the plot .
this allows plotting clustered binding sites marking , for example , cis - regulatory elements , co - occurring pairs of motifs and other positional biases . setting the mouse over a particular motif site
will show the site s sequence , strand , start and end position , the single - site p - value measuring the match quality with the pwm and a conservation p - value ( if multiple sequence alignments had been supplied ) .
most significant motifs are drawn last and may hide less significant ones . when the input sequences are all of the same length , a  localization plot can be displayed ( figure 2c ) .
this graph is useful to analyze positional preferences with respect to the fixed - length sequence window of the input sequences .
it shows in a histogram view the positional distributions of all user - selected motif occurrences with each motif in a different color .
for instance , motif 1 ( tata - box ) in figure 2b is exactly positioned between 33 to 27  bp with respect to the transcription start site ( tss ) at position 0 , whereas motif 2 ( yy1 ) is located mainly downstream of the tss .
mouse - over in the histogram provides the position with respect to the anchor point and the number of counts of the motif .
for instance , motif 4 in figure 2c has 15 counts sharply peaked at position 6 with respect to the tss and a 
detailed information about each motif can be obtained by clicking the expand buttons in the motif summary list .
the  motif distribution plot is similar to the  multi distribution plot and indicates the positions of significant matches of the selected motif on the input sequences .
the  motif site table lists all significant matches with their sequence identifiers , strands , positions , the single - site p - values and the sequence contexts of the motif . 
 figure 3.detailed motif view .
the first box ( motif distribution plot ) plots the position of significant motif matches within the input sequences .
the second box ( motif site table ) gives detailed information on all significant motif matches .
detailed motif view . the first box ( motif distribution plot ) plots the position of significant motif matches within the input sequences .
the second box ( motif site table ) gives detailed information on all significant motif matches .
all data files generated by the xxmotif program , such as lists of motifs with their occurrence positions , p - values and site sequences , pwm weight coefficients and images of motif logos can be downloaded by expanding the box 
two sample input sets and pre - computed results allow the user to get a quick overview of the server s usage and results .
the xxmotif web server runs on an apache server and is implemented using php , perl and r scripts .
with the xxmotif web server , we aim to make a very sensitive and reliable motif discovery method easily accessible to non - expert users .
the server has clearly structured input and results pages and offers various useful interactive analyses .
it is unique in being able to include evidence from motif conservation and positional clustering in the motif search .
we acknowledge financial support by the dfg , the center for protein science munich ( cipsm ) , and a research professorship from the ludwig - maximilians - universitt mnchen , financed through the excellence initiative of the german bundesministerium fr bildung und forschung .
 the discovery of regulatory motifs enriched in sets of dna or rna sequences is fundamental to the analysis of a great variety of functional genomics experiments 
 . these motifs usually represent binding sites of proteins or non - coding rnas , which are best described by position weight matrices ( pwms ) . 
 we have recently developed xxmotif , a de novo motif discovery method that is able to directly optimize the statistical significance of pwms . 
 xxmotif can also score conservation and positional clustering of motifs . 
 the xxmotif server provides ( i ) a list of significantly overrepresented motif pwms with web logos and e - values ; ( ii ) a graph with color - coded boxes indicating the positions of selected motifs in the input sequences ; ( iii ) a histogram of the overall positional distribution for selected motifs and ( iv ) a page for each motif with all significant motif occurrences , their p - values for enrichment , conservation and localization , their sequence contexts and coordinates . 
 free access : http://xxmotif.genzentrum.lmu.de . 
INTRODUCTION
METHOD SUMMARY
INPUT
OUTPUT
DOCUMENTATION
IMPLEMENTATION
CONCLUSION
FUNDING