Fast tool for finding a subsequences?

[Rammaria]

Hello!
I'm new to bioinformatics and I have faced with such a problem.
I'm looking for a fast, desirably multithreading (or which can be parallelized) tool, that can find all the occurences of certain short subsequence with several mismatches in every read in NGS output. Most of all mismatches are substitutions, not indels.
For example, I have a lot (thousands) of sequences like this: "fdsjfsjdkdfjSPARjdskfjdskSPAMfddjskdsfjkSPAMdkdsfjk", and I need to get a matrix with positions of all the entries of "SPAM" in every sequence.
I tried to use the patternMatch from R-Bioconductor and the Python package fuzzysearch, but they are not actually fast. "Motif" from Biopython does not seem quite right for my goals and also is not very fast.

Do you know any suitable tool for me?

I believe it exits and I do not need to reinvent the wheel.

Thank you in advance.

[GenoMax]

Do you know the pattern you want to look for (e.g. SPAM in the example above) then fuzznuc from EMBOSS may be an option.

If you are looking for patterns de novo then a k-mer search (of the length you want) may work.

Having to allow for mismatches would make this job lot more difficult.

Then there may be the possibility of using "grep" in some creative ways (if you know the pattern you want to search for).

[Brian Bushnell]

BBDuk can find all instances of a string (up to 31 bp) allowing a set number of mismatches. It will not return a matrix of positions, but it can replace all instances with some symbol that is then easy to find with a different tool that is not capable of handling mismatches. For example:

bbduk.sh -Xmx1g in=reads.fa out=masked.fa literal=ACGT k=4 ktrim=x hdist=1 rcomp=f

For the input file:

>1
GGGGGACGTGGGGGGGACGT

the output would be

>1
GGGGGxxxxGGGGGGGxxxx

You can use the "hdist" flag to specify a hamming distance. And you can use the "rcomp" flag to determine whether only forward or both forward and reverse sequences will be replaced. It's fast and multithreaded.

Edit - the functionality I suggested seems to be broken; I will investigate.
Edit2 - Fixed now as of v33.40b.

[maubp]

Another k-mer based approach would be mirabait from the MIRA v4 assembler. This assumes you pattern SPAM is short enough that you can use it directly as a k-mer to search for.

[Rammaria]

Many thanks to you all for your great solutions!

I know the pattern exactly (it must be strictly 'SPAM' in my example), so fuzznuc and bbduk seem to be right for me.

[Rammaria]

Brian, how can I cite bbduk and other bbtools if I use them?

[Brian Bushnell]

They're not yet published, so you can just cite my name and the Sourceforge website (https://sourceforge.net/projects/bbmap/).

[Rammaria]

Ok, thank you!