Searches

Searches consist of querying the data set for exact or inexact patterns. Patterns can be specified by entering a query into the Pattern box of the Input Pane, and clicking the Search button on the Input Pane.
The simplest way to construct a query is to enter a nucleotide sequence (acgt) with optional positional wildcards (*) into the Pattern box, and specify mismatches in the Mismatches box. Multiple queries can be performed at once, by separating the patterns with a semi-colon  ( ; ). Searches performed in this manner are conducted on all sequences in the data set, at any position, and any length.
In order search for a pattern located at a specific sequence, and position, enter a triple for each query: <sequence, position, length> e.g. 2, 123500, 15. This will cause the pattern at the given position and sequence to be searched against all sequences.
By default, a search produces a single results table for each query.

Traversals

Traversals consist of examining the input sequences for common substrings. Traversals produce one or more result tables, depending on which settings are selected. The traversal section of the settings window allows the user to select the different types of result tables that are presented. Each different setting will, if selected, produce one or more additional result tables. For example, the user can ask for the longest common substrings (LCS) present N times for N = 2  to N=200, in any number of sequences in the data set, by selecting and setting LCS occurrences=100 in the traversal settings window. In this case, one result table would be produced for each value of N, with the LCS for that N value would displayed in a results table, giving 100 results total for this particular traversal.
Depending on the traversal settings, a single traversal can produce many different result tables – one for each distinct type of traversal that is conducted.

Top bar

The top bar contains buttons for initiating the primary actions of STS.

Sequence display area

The sequence display are takes up the most space in the Input panel. It takes the form of a table containing a single row for each sequence in the input files. Each input sequence is associated with a number from 1 to the number of sequences. Information about each sequence is displayed in the following columns, which can be used to sort the sequences:

• Number – The number associated with the sequence.
• SeqName – The name of the sequence as indicated in the FASTA file.
• FileName – The name of the FASTA file that the sequence was imported from.
• OrigSize – The number of bytes read from the file for the sequence.
• DNASize – The number of bytes of the sequence that corresponded to the characters ‘acgt’. All other characters are ignored.
• Begin – The first sixteen nucleotides of the sequence.
• End – The last sixteen nucleotides of the sequence.
• Wildcards – The number of wildcard characters encountered in the sequence. (R, Y, W, S, M, K, H, B, V, D, and N).
• NChunks – The number of contiguous chunks of N characters encountered in the sequence.
• GarbageBytes – The number of non-ACTG non-wildcard characters encountered in the sequence.
• TailLength – The number of repeats of a single motif encountered at the end of the sequence. This column is deprecated; it was previously used for development purposes.

Query input area

The query input area is used to specify the options for searches and traversals before they are initiated through top bar buttons. As such, the area is divided into Search and Traverse areas, each with their own input boxes.

Search

• Pattern – Used to specify search patterns, using ACGT to specify nucleotides, and * to specify wildcards. Patterns can also be specified by entering 3 numbers per pattern for <sequence, position, length> e.g. “2, 125000, 25”. If multiple patterns can be entered by separating individual patterns with a semi-colon “;”.
• Mismatches – This box is used to specify the number of mismatches in the search pattern entered into the Pattern box. If left blank, the number of mismatches allowed will be zero. Mismatches currently do not work when specifying multiple patterns at once.
• Max results – The maximum number of search results to display in non-standard results tables.

Traverse

• Threshold length – Common substrings must be at least this length in order to show up in results tables.
• Display length – Restricts the number of nucleotides that are displayed for each common substring. When copying the sequence from the results table for a pattern search, the entire sequence will still be copied
• Max results – The maximum number of search results to display in non-default result sets.
• Reference genome – Only display results common substrings that are present in this sequence. Takes a sequence number, as shown in the Number column of the Sequence Display Area of the Input Pane.

Console

The console area displays output from the backend executables when building the suffix tree or importing sequences, such as the amount of time a process took to complete, and is used to report any errors that arise during a process. Red text will be shown here if an error occurs.

Settings

The settings window contains tabs for altering the settings of STS:

General settings

Settings pertaining to the general operation of the program.

• Workspace – Specifies the root directory that all files will be written to. This should be the same as the parent directory of the <suffix_tree_name>.ST file, if loading a previously constructed suffix tree.
• Clear results – If selected, STS will delete all results tables in the Output pane every time a new search or traversal is run.
• Advanced – This section is intended primarily for development/debugging purposes. This section allows the user to feed command-line arguments directly to the individual executables that implement the backend.

Build settings

Settings for suffix tree building.

• Partition size (number of nodes) –  The number of nodes per suffix tree partition. The average user should not need to adjust this, as the partition size is automatically adjusted for the the user’s computer when the suffix tree is built.
• Suffix buffer size (each) – The buffer size when constructing the suffix tree. The average user should not need to adjust this.
• Skip sort phase – Suffix sorting phase of construction. May increase memory load during the subsequent merge phase. When building suffix trees for large data sets, selecting this option may decrease the time build time.

Traverse settings

Settings governing the types of result sets displayed from a traversal. Each setting will produce additional table(s).

• LCS occurrences –  Default set. Gather the longest common substring (LCS) appearing N times, for N=2 to the number specified in any sequence. Produces a single result table.
• LCS inputs – Default set. Gather the single longest substring  common K sequences for each value of K from K=2 up to the specified number of inputs. Produces a single result table.
• Number of occurrences – Similar to LCS occurrences, but allows the user to specify the exact values of N, as a comma-separated list, e.g. 2, 3, 5. Produces a result table for each value of N.
• Number of inputs – Similar to LCS inputs, but allows the user to specify the exact values of K, as a comma-separated list, e.g. 2, 3, 4. Produces a result table for each value of N.
• Sets – Allows the user to specify specific subsets of sequences to include a result table for. Each set is specified with curly braces surrounding a comma/space-separated list of the sequences in the set, e.g. {1, 2, 5, 7}. Multiple sets are specified by placing them next to each other, e.g.  {1, 2, 5, 7}{1, 4, 6}. A result table will be produced for each set. The number of substrings displayed can be specified by the “Max results” section of the “Traverse” query input section of the Input Panel.
• All singles – Produce a result table for each single sequence.
• All pairs – Produce a result table for each possible pair of sequences.

Search settings

Settings governing the display of search results.

• One result set – If selected, forces results for multi-pattern queries to all be displayed in a single table, rather than separate tables for each pattern.

Top bar

• Clear All – Remove all results tables from the display area.
• View Inputs – Open a window that maps sequence numbers to sequence names. This is useful for determining which result corresponds to which sequence(s).
• Save Results – Save the current results tables to disk, so that they can be re-loaded later.
• Load Results – Load previously saved results tables.

Results display area

This area contains result tables from queries. Each row corresponds to a result. Each table has an associated Remove table and View in separate window button. Result tables are added to the display area for each subsequent query, and remain until individually removed, or the window is cleared. Result tables display information about each result in columns. Tables can be sorted by multiple columns. The columns present in each differs depending on whether the table is displaying search or traversal results:

Traversal result tables

Each row in a traversal result table corresponds to a LCS. LCSs are always maximal – they cannot be extended in either direction without violating one or more of their properties. The columns listed below are present in all traversal result tables.

• Number – The hit number. This number serves to identify the specific LCS in the context of the given result table.
• Where – A string of binary digits of length <=32, containing 1’s and 0’s, representing the different input sequences. If there is a 1 in a give position, this indicates that the substring is present in the sequence corresponding to that position, starting at one on the left and counting up for each position to the right.  For example, a value of 100110 indicates that a substring is present in sequences 1, 4, and 5.
• K – The number of sequences the substring is present in.
• N – The number of times the substring is present in the number of sequences that the table displays results for.
• NC – The number of other substrings that exist for the given N and length values, since only one is displayed for each length, i.e. In a table that displays only one result for each N-value, if there exist two different sub sequences for N=2, only the longest one will be displayed, but if they are both of the same length, the table will still only display one, and the NC value will be 1 to represent the sequence that is not shown.
• Sequence – One of the input sequences that the substring occurs in.
• Position – The start position of the substring in the sequence specified in the sequence column.
• Length – The length of the substring.
• Pattern – The nucleotide sequence of the substring. The number of nucleotides displayed here is controlled with the “Display length” box in Traverse section of the Input Panel. The user can right-click the pattern to perform a pattern search for the sequence in the whole data set, without the need to copy and paste the pattern into the Input Pane.

Search result tables

Although the number of hits displayed is controlled by the user, the table title always shows the total number of hits.

• Number – The hit number. This number serves to identify the specific result in the context of the given result table.
• Sequence – The sequence that the hit occurred in.
• Position – The position of the hit in the sequence.
• Length – The length of the hit.
• Right – The number of nucleotides remaining to the right (3′) of the hit in given input the sequence.
• SeqLength – The length of the sequence that the hit was found in.
• Count – The total number of hits for the query pattern.

Console

The console area displays output from the backend executables during searches or traversals, such as the amount of time a process took to complete, and is used to report any errors that arise during a process. Red text will be shown here if an error occurs.