Revision as of 17:10, 27 February 2012

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.

The Pattern Discovery component is available when a sequence (FASTA format) file has been loaded in the Project Folders component, and its data node is selected.

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

• Normal - 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 of Sequences) - The pattern must appear in at least given percentage of sequences.
• Support (Number of Sequences) - The pattern must appear in at least the given number of sequences.
• Support (Number of Occurrences) - The pattern must occur at least the given number of times in the set of sequences (can be more than once per sequence).

Additional options are:

• Minimum Tokens - The minimum number of tokens in a discovered motif.
• Density Window - A sliding window in which at least the number of tokens set in "Density Window Min. Tokens" must be found.
• Density Window Min. 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.

• Decrement support (%) - sets the size of intervals by which support level is decreased in successive searches (default is 5). The decrease is multiplicative, e.g. if one enters 5%, support will be reduce to 95% of its previous value at each step.
• Minimum Support (%) - sets the lower limit on the percentage of sequences that must contain a specific motif (default is 10%).

Note - Prior to version 2.2.1, if a % sign is included in the minimum support text field, the percentage entered will be applied to the initial minimum support value. For example, if the initial minimum support is 70%, and "10%" is entered in this field, the final stopping value for the calculation will be 7%.

• Minimum Pattern Number - sets a lower limit on the number of motifs in a cluster (point at which support decrease 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.

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.
  • When unchecked, the choices for similarity matrix and threshold are enabled.

• 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 input is restricted to integers. (Note that the threshold is however stored as a double).

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.c2b2.columbia.edu, 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

Single Pattern

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 the "All/Matching Pattern" box is checked (red arrow), only sequences that have a match to a selected pattern will be shown.

Multiple Patterns

If more than one pattern is selected, each will be displayed using a separate color (note we have scrolled down in the result list, so these are not the same hits as above):

Details as Hover Text

If the mouse cursor is placed over a particular pattern match, details of any matches at that point are displayed as hover text.

Details include

• current cursor location on sequence
• pattern(s) matching
• start and end positions of matching patterns in angle brackets <>.

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) full sequence view

BLOSUM50 was selected in the Advanced parameters tab and the search repeated with the same parameters otherwise. Note that the "All/Matching Pattern" box is checked. The correspondence between the highlighted sequence and the selected regular expression result can be seen.

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. The step size is entered as an integer.
• 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 shows three 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.

Sequence Selection

By default, Pattern Discovery will be run on all sequences in the currently selected sequence data node. However, subsets of sequences can be created and activated in the Markers component. The Pattern Discovery component will respect any activated marker sets, restricting discovery to those sequences in activated sets. If no marker sets are activated, then all sequences will be used.

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.

• Similarity Threshold - the threshold is input as an integer number. (However, note that it is passed to the Splash server as a double).

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).