# Search for a string in another string allowing mismatches

**URL:** <https://www.ruby-forum.com/t/search-for-a-string-in-another-string-allowing-mismatches/195331>\
**Category:** Ruby\
**Created:** [September 21, 2010, 8:07pm UTC](https://www.ruby-forum.com/t/search-for-a-string-in-another-string-allowing-mismatches/195331 "2010-09-21T20:07:26Z")\
**Posts on this page:** 4\
**Page:** 1

<div class="post-metadata">

**Author:** ![janus](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/j/c2a13f/32.png) [@janus](https://www.ruby-forum.com/u/janus)\
**Post date:** [September 21, 2010, 8:07pm UTC](https://www.ruby-forum.com/t/search-for-a-string-in-another-string-allowing-mismatches/195331/1 "2010-09-21T20:07:26Z")

</div>

Hi all,

I’m sure this is a very common problem. But can’t find a simple &  
efficient way of solving it.

Basically, I want to find out if a string contains my search string as a  
substring. However, a certain amount of mismatches has to be allowed.  
Here’s an example:

query string:  
“acgt”

subject string  
“acctaggg”

If no mismatch was allowed, there would be 0 hits.  
If 1 mismatch was allowed, the query string would match “acct”.  
If 2 mismatches were allowed, the query string would match “acct” and  
“aggg”.

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]/

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

I’d be very grateful for any suggestions!

Cheers,  
Janus

---

<div class="post-metadata">

**Author:** ![janus](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/j/c2a13f/32.png) [@janus](https://www.ruby-forum.com/u/janus)\
**Post date:** [September 22, 2010, 1:16am UTC](https://www.ruby-forum.com/t/search-for-a-string-in-another-string-allowing-mismatches/195331/2 "2010-09-22T01:16:21Z")

</div>

On Sep 21, 2010, at 11:07 , Janus B. 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

---

<div class="post-metadata">

**Author:** ![janus](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/j/c2a13f/32.png) [@janus](https://www.ruby-forum.com/u/janus)\
**Post date:** [September 22, 2010, 2:48pm UTC](https://www.ruby-forum.com/t/search-for-a-string-in-another-string-allowing-mismatches/195331/3 "2010-09-22T14:48:19Z")

</div>

On Wed, Sep 22, 2010 at 3:07 AM, Janus B. [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid)  
wrote:

> If no mismatch was allowed, there would be 0 hits.  
> If 1 mismatch was allowed, the query string would match “acct”.  
> If 2 mismatches were allowed, the query string would match “acct” and  
> “aggg”.

This does not use regular expressions.  
It does not tell you which characters match. It tells you how many.

I don’t know if it is useful or fast enough but maybe it will give you  
some ideas.

str = “acctaggg”

(0…str.length-4).each do |y|  
p str.unpack(“@#{y}a4”)[0].split(//).zip(“acgt”.split(//)).map{|r|  
r[0]\<=\>r[1]}.select{|f| f==0}.size  
end

Harry

---

<div class="post-metadata">

**Author:** ![janus](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/j/c2a13f/32.png) [@janus](https://www.ruby-forum.com/u/janus)\
**Post date:** [September 26, 2010, 10:34am UTC](https://www.ruby-forum.com/t/search-for-a-string-in-another-string-allowing-mismatches/195331/4 "2010-09-26T10:34:04Z")

</div>

On Wed, Sep 22, 2010 at 9:47 PM, Harry K. [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid)  
wrote:

> > “acctaggg”  
> > I don’t know if it is useful or fast enough but maybe it will give you
> 
> Harry

A little modification of my previous post.  
Again, (lack of) speed may be a problem.

class String  
def fuz(m,n) # (string to match, number of matches)  
a = []  
(0…size-4).each do |y|  
t = self[y,4]  
if t.split(//).zip(m.split(//)).map{|r| r[0]\<=\>r[1]}.select{|f|  
f==0}.size\>=n  
a \<\< t  
end  
end  
a  
end  
end

str = “acctaggg”

p str.fuz(“acgt”,2) #\> [“acct”, “aggg”]

Harry