GIMSAN: A Gibbs motif finder with significance analysis

GIMSAN

GIMSAN (GIbbsMarkov with Significance ANalysis) is a web-server tool for de novo motif discovery:

Hybrid Gibbs sampler for motif finding that uses a Bayesian prior on the percentage of sequences containing sites but uses a maximum likelihood approach on the motif matrix
Biologically realistic and reliable statistical significance analysis
- Using a 3-Gamma approximation scheme
- Factoring local sequence composition information
- Reports an approximate 95% confidence interval of the point estimator of the motif p-value
Can be used to select the optimal width from a range of motif widths based on our significance analysis
Column pair dependency estimated using a Monte-Carlo scheme

It is available as a stand-alone application on Unix and PBS (Portable Batch System) cluster:

Download GIMSAN

(2010/05/02) Column pair dependency added to Unix version

Frequently Asked Questions (FAQ)

Question: My job exceeded the time-limit and it was finished prematurely on BioHPC. What can I do?
You can increase the "Number of Processors" to allocate on BioHPC. There is a 24-hour execution-time limit for each processor on BioHPC.
Question: What should I put as the width parameter?
GIMSAN (both Unix and web version) allows the user to specify multiple widths. We recommend that you start with {8,14,20}, and then see which width gives you a motif with the smallest p-value (i.e. highest significance). Note that you should increase the number of processors if you add additional widths. Allocating one additional processor for each additional width should suffice, e.g. 3 processors for widths {8,14,20}.
Question: What does the following output mean: "MLE of p-value is 1.1e-73 and its confidence interval is (0, 1e-43)"?
Intuitively, the GIMSAN p-value is defined as the probability that a random sample of the same size as the input set will contain a motif of the same width that scores better than the motif found by GIMSAN. Thus a smaller p-value implies a more statistically significant motif. The MLE (maximum likelihood estimate) of the p-value in this example is 1.1×10^-73. Since this can often over-estimate the significance of the motif, GIMSAN augments it with a 95% confidence interval of the p-value. The upper value of the CI is the important number for discerning whether the candidate motif is statistically significant. In this example, the upper value of the CI is 10^-43.
Question: How would duplicates or long substring/superstring in FASTA file affect the output of GIMSAN?
Duplicates and substring/superstring in the data would overestimate the p-value and cause GIMSAN to incorrectly label a motif significant.

Please send any additional questions, comments, or suggestions to ppn3 "at" cs.cornell.edu

GIMSAN input options

Options	Cmdline	Description
input FASTA	--f	a set of sequences in FASTA format for de novo motif discovery
background model	--bg	file (FASTA format) for background model estimation. For example, this can be a set of S. Cerevisiae intergenic sequences. This data is used to generate null sets of sequences that preserve the dimensions and local GC-content of the input set, as well as estimating the background model for the de novo motif-finding task. Note: It is recommended that the user either "upload your own genomic file" or use "one of our standard genomic files".
motif widths	--w	user can specify a range of motif widths (e.g. {8,14,20,30}). Once the GIMSAN job has completed, user can select the optimal width by choosing the motif with the lowest p-value (i.e. highest significance).
size of nullset	--nullset	size of the randomly drawn set to estimate the motif-finder's null distribution based on 3-Gamma approximation. A larger null set would give a more accurate p-value at the expense of longer runtime.
number of processors		the number of processors to allocate on the computer cluster. The specified number of processors are allocated before any execution of the job. Therefore, it is recommended that this parameter should be set to less than 10.

GIMSAN sample output on FHL1 motif

Commercial use of GIMSAN without written permission from the authors is prohibited. If you use this program in your research, please cite:

Patrick Ng, Uri Keich. GIMSAN: A Gibbs motif finder with significance analysis. Bioinformatics, 24 (19): 2256-2257, 2008.

The motif significance analysis approach is described in detail in:

Patrick Ng, Uri Keich. Factoring local sequence composition in motif significance analysis. Proceedings of the 19th International Conference on Genome Informatics (GIW), Gold Coast Australia, 2008.
Uri Keich, Patrick Ng. A conservative parametric approach to motif significance analysis. Proceedings of the 18th International Conference on Genome Informatics (GIW), Singapore 2007.

If you use the sequence logos from GIMSAN in your research, please cite WebLogo.

We thank Robert Bukowski for deploying GIMSAN as a web application. GIMSAN is based upon work supported by the National Science Foundation under Grant No. 0644136.

Please send any questions, comments, or suggestions to ppn3 "at" cs.cornell.edu