First, FSWM finds all 'spaced-word matches' between a pair of genomic sequences with respect to a pre-defined binary pattern of 'match' and 'don't-care' positions. A 'spaced-word match' is a gap-free alignment of two words from the input sequences, that has the same length as the pattern. Nucleotides at the 'match' positions must be identical, while mismatches are possible at the 'don't-care positions'.

For each pair of input sequences, our program estimates the average number of substitutions per position, based on the ratio of mismatches at the 'don't-care positions' of the spaced-word matches.

To distinguish between spaced-word matches representing true homologies and spurious background spaced-word matches, our program gives a score to each spaced word match, based on a nucleotide substitution matrix (Chiaromonte et al., 2002):

The score of a spaced-word match is then defined as the sum of the substitution scores of the aligned nucleotides at the don't care positions. In the above example, there are four don't-care positions, so four pairs of aligned nucleotides are to be considered, namely (C,C), (T,A), (A,C) and (A,G). With the above substitution matrix, the score of this spaced-word match is therefore 100-123-114-31 = -168.

Our program discards all spaced-word matches with a score below a certain threshold. By default, the threshold is zero, but the user can adjust this value.

For each pair of input sequences, the scores of the spaced-word matches can be visualized using a so-called 'spaced-word histogram'. Here, the number of spaced-word matches is plotted against the scores, i.e. for each possible score value the number of spaced-word matches with this score is plotted.

For a pair of i.i.d. random sequences, two peaks are visible in the spaced-word histograms which are both approximately binomially distributed (see above). The peak on the left-hand side (negative score values) essentially consists of random background hits, while the peak on the right-hand side (positive values) consists of spaced-word matches representing true homologies. Please note that for real data, the homologous peak looks more complex because the varying degrees of sequence similarity in different parts of the sequences, see below (Octadecabacter arcticus 238 vs Octadecabacter antarticus 307).

Spaced-word histograms can be visualized by our web server and the user can change the threshold for each pairwise sequence comparison individually, to distinguish true homologies from noise. Our command line tool, which can be downloaded in the download section, allows the user as well to change the threshold, but the difference compared to our web server is that only a global threshold can be set for all sequence pairs.

FSWM also removes ambigous spaced-word matches, see our paper for more details.

After the threshold is set and the background spaced-word matches are discarded, FSWM estimates for each pair of input sequences their evolutionary distance, i.e. the average number of substitutions per sequence position since the two sequences diverged from their last common ancestor. To this end, we calculate mismatch rate for the aligned nucleotide pairs at the don’t care positions of the remaining (homologous) spaced-word matches. We then use the Jukes-Cantor correction to estimate the number of substitutions per position. The output of the command line program is a distance matrix in phylip format, containing the estimated distances for all sequence pairs. On our web server the distance matrix can be downloaded, including the resulting tree, obtained with Neighbor-Joining.