Revision as of 16:31, 10 March 2011

Overview

Sequence Pattern Discovery is the process of identifying nucleotide or amino acid arrangements, also called motifs, that are enriched in a set of sequences. Such motifs may identify regions that have been preserved by evolution and which therefore may play a key functional or structural role. geWorkbench provides two modes of Sequence Pattern Discovery: Regular Discovery and Exhaustive Discovery.

Regular Discovery is based on the algorithm SPLASH (Califano, A., 2000); it generates a list of all regular expression patterns (motifs) that satisfy a user-defined minimum support and a minimum density criteria. The former determines the minimum number of times a pattern must occur in the sequence set to be reported. This can also be expressed as the minimum percent of sequences that must contain the pattern. The latter determines how sparse the pattern can be, in other words the minimum number of matching characters k (any character except for the dot character “.”) over a window of predefined length w.

SPLASH-based motif discovery is extremely efficient and can process most large protein super-families in a few minutes on a conventional workstation. Discovery is uniquely effective in identifying sparse patterns using extremely low-density constraints, and the results obtained with Discovery can provide the core for a large number of more specific local alignments.

Exhaustive Discovery starts from a relatively high minimum support (e.g. patterns occurring in 75% of the sequences) and it progressively reduces the support, until a statistically significant pattern is discovered. Discovered patterns are reported and then masked in the sequence set so that they are no longer discovered. Then the process continues iteratively until the minimum support reaches a lower user-defined limit. Exhaustive Discovery, thus, produces a list of non-overlapping motifs in order of support.

Component layout

The Pattern discovery component control area has three sections.

1. Run controls are shown at top,
2. the hit display area is in the center (empty in the figure below), and
3. the parameter settings are at bottom.

Top-level run controls

• Norm - select the "normal" pattern discovery algorithm.
• Exhaustive - select the "exhaustive" pattern discovery algorithm. This takes much more time.

• Curling arrow - start a new pattern discovery run.
• Stop sign - Cancel the current pattern discovery run
• File folder - load a pattern file

• Progress bar - To the right of the control buttons is a progress bar that reports on the current stage of discovery being executed.

Setting parameters

A number of parameters can be adjusted by the user to adjust the sensitivity of the search.

Basic tab

Three options for specifying support are available via a pulldown menu:

• Support Percent % - The pattern must appear in at least given percentage of sequences.
• # Support Sequences - The pattern must appear in at least the given number of sequences.
• # Support Occurrences - The pattern must occur at least the given number of times in the set of sequences (can be more than once per sequence).

• Min Tokens - The minimum number of "Density Tokens" in a discovered motif.
• Density Window - A sliding window in which at least the number of tokens set in "Density Tokens" must be found.
• Density Tokens - the minimum number of matching full character tokens (not wildcards) within the "Density Window".

Exhaustive tab

Parameters specific to the "exhaustive" search algorithm can be set in this tab.

• Dec. support (%) - sets the size of intervals by which support level is decremented in successive searches (default is 5)
• Dec. density support - not used.
• Min support - sets the lower limit on the percentage of sequences that must contain a specific motif (default is 10%).
• Min pattern number - sets a lower limit on the number of motifs in a cluster (point at which support decrementing stops).

Limits

• Max Pattern Number - limits the number of patterns to discover. The actual upper limit to the number of patterns the server will return is 99,999.
• Max run time (sec) - limits search time.

Advanced tab

• Exact Only (default checked)
  • When checked, no substitution matrix will be used. Exact character matches are required.
  • When checked, the choices for similarity matrix and similarity threshold are disabled.
  • Note - "Exact only" should always be used for DNA as no DNA substitution matrix is provided.

The choices for similarity matrix and threshold are enabled when "Exact Only" is unchecked.

• Similarity matrix choice (default BLOSUM50) - Other choices are BLOSUM62 and BLOSUM100.
• Similarity threshold (default 2) - pairs of amino acids with a score higher than the specified threshold in the chosen BLOSUM similarity matrix are considered similar.

The Advanced tab when "Exact Only" is checked:

The Advanced tab when the "Exact Only" is unchecked:

Run Pattern Discovery

• Pushing on the button with the curling arrow icon will bring up the session creation box:

Discovery Session

• Discovery Session Name: A name is auto-generated for identifying the job on the server, but any name can be entered.
• Create - Push to start the search.
• Cancel- Cancel the discovery run.

Discovery Session Server

• Server and Port: Columbia supports a Pattern Discovery server at splash.cu-genome.org, Port 80.
• Username: Any name can be entered to identify the job.
• Password: none currently required.

The progress bar will show the several stages of a search:

• Uploading
• Processing seeds
• Discovering
• Collating
• Done

Viewing results

The result of the search can be viewed both in the Pattern Discovery module itself and in sequence viewer modules such as "Sequence" and "Promoter" and "Position Histogram". In Pattern Discovery the results are returned in a table, and the hits for the motif(s) selected in the table will be displayed superimposed on the sequences displayed e.g. in the Sequence Viewer located above in the Visual area. In this picture, the results were first sorted by the number of tokens.

Note that if a substitution matrix was used during discovery, the motif may contain a range of possible residues, enclosed by square brackets, for a particular position. This is depicted below under the BLOSUM50 result headings.

Motifs found are listed in a table with the following columns:

• Hits - The total number of times a motif was found in the sequence dataset, including any multiple hits in individual sequences.
• Sequences Hit - The number of sequences which contained at least one occurrence of the discovered motif.
• # of Tokens - the number of full-character tokens in the motif.
• ZScore - a measure of how often the motif would be found in a random set of sequences of the same size and composition as the project dataset.
• Motif - a sequence of tokens, which may be full characterd or wildcard.
  • A period (.) represents a wildcard and matches any character.
  • Square brackets are used to indicate multiple possible characters at a given position (occurs when a substitution matrix (BLOSUM) is used during discovery).

Result (Exact matches) sequence line view

Each sequence is shown as a line with length proportional to the sequence length. All sequences are left-aligned.

The position of matches along the sequence are shown using colored boxes (here blue).

If more than one pattern is selected, each will be displayed using a separate color:

Result (Exact matches) full sequence view

In full sequence view, the actual sequence letters are displayed and matches are again outlined in colored boxes (here blue).

Result (BLOSUM50) in sequence line view

BLOSUM50 was selected in the Advanced parameters tab.

Result (BLOSUM50) full sequence view

BLOSUM50 was selected in the Advanced parameters tab.

Position Histogram

The Position Histogram displays (binned) support of each motif along the length of the sequences.

• Support - The number of times a motif is found among all the sequences at a particular position or within a particular range of positions (bin step size) is counted. The result is displayed as fractional support for the motif at that position.

• Step - the sequences are divided into bins of the specified "step" size.
• Plot Position - push to draw a new histogram.
• Image snapshot - place a copy of the histogram as an image into the Project Folders component.

Note that this will only be useful to the extent that the sequences are in some way aligned before analysis.

The figure below show two motifs selected. Each is displayed in a unique color in the position histogram.

Adding results to the Projects Folder

The results of a run of Pattern Discovery are automatically placed in the Project Folder:

Options to Save or Mask Patterns

Several operations are possible on the returned patterns. The options menu can be seen by right-clicking on a selection of one or more returned patterns.

1. The patterns can be saved, either with their positions on the original sequences, or just as regular expressions.

2. The patterns can be masked out of the query sequence.

The options shown in the picture below are:

• Mask Pattern - The selected pattern(s) will be masked out of the sequence for future searches. They will not be re-discovered.

• Unmask All Patterns - Undo the masking.

• Save Patterns (Regex Only) - This will save the selected pattern(s) in the form of regular expressions, that is, letters and wild-card characters.

• Save Selected Patterns - This will save both the selected pattern(s) and their hits to the query sequences. The locations (positions on the query sequences) saved are specific to the particular input file used. The name of this file is saved in the pattern file.

• Save All Patterns - This will save both all of the patterns and their hits to the query sequences. The locations positions on the query sequences) saved are specific to the particular input file used. The name of this file is saved in the pattern file.

• Add Patterns to Project - This will add the patterns found as a data node in the Projects Folder, with the position information on the input sequences.

Notes on display of results

1. Pattern Discovery results can only be displayed in the context of the sequences from which they were derived.
2. There is no provision for filtering out repeats from genomic DNA sequence. Affected sequences should be masked before loading into geWorkbench.

Example Pattern Discovery runs

Prerequisites

1. Make sure that Pattern Discovery and Position Histogram (if desired) are loaded in the Component Configuration Manager.
2. Load a file containing the sequence or sequences to be analyzed into the Project Folders component.

For this example, we use a file containing a number of histone sequences, H1H5_HistoneDB_NHGRI.fasta.

The Pattern Discovery component appears in the Command area of geWorkbench (lower right quadrant) when a sequence data node is selected.

Setup (Exact matches)

We will try parameters set to allow longer matches. No changes from default are made in the other parameter tabs. In particular, this search uses exact matching of the sequence letters, without substitutions.

• Support Percent: 30
• Min tokens: 10
• Density Window: 7
• Density tokens: 4

These parameters were empirically chosen. You can try variations to see how it affects the result.

The results are pictured above in Viewing Results.

Setup (BLOSUM50)

If the "Exact only" checkbox in the Advanced Parameters tab is unchecked, a selected BLOSUM substitution matrix for protein sequences will be used.

The results of repeating the same run as before but using BLOSUM50 are pictured above in Viewing Results.

References

Califano, A. (2000). SPLASH: structural pattern localization analysis by sequential histograms. Bioinformatics, Apr;16(4):341-57 (link to paper).