From: Dave Howell <groups.2009a@...>
Date: 2010-09-22T08:15:43+09:00
Subject: Re: Search for a string in another string allowing mismatches


On Sep 21, 2010, at 11:07 , Janus Bor wrote:

> Hi all,
> 
> I'm sure this is a very common problem. But can't find a simple &
> efficient way of solving it.

Hmm. I wouldn't think this is  common at all. I have dealt with a somewhat similar situation in the past in two ways:

1. Let the user do partial searches.

2. Using the 'soundex' tools in a database

Neither of those matches your situation, which appears to be scanning for near-matches in genetic material.

> Unfortunately, performance is also very important, as I will have to
> perform thousands of searches in strings that contain several million
> characters.

This certainly isn't my field of expertise, but I don't expect a fuzzy-logic search and 'performance' to be particularly compatible. Hope I'm wrong!

> If possible, I would like to do this using regular expressions, as my
> search string can also contain ambiguous characters. So a real search
> pattern might look something like this: /[ac][c][cg][t][acgt][c][gt][t]/

Gah. 

What came to my mind was something like 

	fuzzysearch("agct", 1)

where "1" is the number of mismatches allowed. The code in question would run the following searches:
	/.gct/
	/a.ct/
	/ag.t/
	/agc./

for fuzzysearch("agct",2) it would run
	/..ct/
	/.g.t/
	/.gc./
	/a..t/
	/a.c./
	/ag../

I have no idea what the overhead of wildcards are; if there's some ultra-simple ultra-fast string matching tool somewhere that you can call from Ruby or invoke through a command line, then you could take advantage of the tiny set of possible alternatives, and break the fuzzy search into 13 static searches:
	agct
	cgct
	ggct
	tgct
	aact
	acct
	atct
	.
	.
	.
	agca
	agcc
	agcg