Fuzzy regex: fuzzy count for substitution is always 1

user_10403839 0
Viewed 150

I am using the Python regex module for approximate string matching. I have a DNA sequence which I would like to search for a specific pattern, while allowing for at most 1 substitution: {s<=1}. In the DNA sequence, multiple patterns are acceptable. For example, the first three characters can either be 'GAG' or 'GAT', and the same principle holds true for the rest of the DNA sequence.

I made an example below, where I want to use regex search on a 9 character long string. To my understanding, the pattern should match the string without any subtitution.

However, regex gives me a match with a fuzzy count of 1 for substitutions (see below). I do not understand this, as the sequence matches the pattern.

import regex

dna_patt = regex.compile("((GAG|GAT)(TCT|GAA)(GCC|GGG|GGT)){s<=1}")
sequence = "GATGAAGGG"

print(dna_patt.search(sequence))

<regex.Match object; span=(0, 9), match='GATGAAGGG', fuzzy_counts=(1, 0, 0)>

When I get rid of having multiple options for the three characters, this problem does not occur anymore.

dna_patt = regex.compile("(GATGAAGGG){s<=1}")

print(dna_patt.search(sequence))

<regex.Match object; span=(0, 9), match='GATGAAGGG'>

My question is: what am I doing wrong in pattern creation? Or am I missunderstanding how the fuzzy counts work? Any tips or improvements are welcome.

fuzzy-search python regex
2 Answers

From the regex module documentation:

By default, fuzzy matching searches for the first match that meets the given constraints.

In your case, the first match is obtained using GAG and performing one substitution (since GAG is tried before GAT). You can use the BESTMATCH flag to look for the best match instead:

import regex

dna_patt = regex.compile("((GAG|GAT)(TCT|GAA)(GCC|GGG|GGT)){s<=1}", regex.BESTMATCH)
sequence = "GATGAAGGG"

print(dna_patt.search(sequence))

It gives:

<regex.Match object; span=(0, 9), match='GATGAAGGG'>
user_151877280

You could also use a character class to match either G or T with GA[GT] to find GAT the first time.

If you don't need the capture groups afterwards, you can make them non capturing using (?:

import regex

dna_patt = regex.compile("(?:GA[GT](?:TCT|GAA)(?:GCC|GG[GT])){s<=1}")
sequence = "GATGAAGGG"

print(dna_patt.search(sequence))

Result

<regex.Match object; span=(0, 9), match='GATGAAGGG'>

Python demo

user_54249880
Related