# Regexp with gaps

**URL:** <https://www.ruby-forum.com/t/regexp-with-gaps/143019>\
**Category:** Ruby\
**Created:** [July 14, 2008, 4:10pm UTC](https://www.ruby-forum.com/t/regexp-with-gaps/143019 "2008-07-14T16:10:45Z")\
**Posts on this page:** 4\
**Page:** 1

<div class="post-metadata">

**Author:** ![egrasso](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/e/87869e/32.png) [@egrasso](https://www.ruby-forum.com/u/egrasso)\
**Post date:** [July 14, 2008, 4:10pm UTC](https://www.ruby-forum.com/t/regexp-with-gaps/143019/1 "2008-07-14T16:10:45Z")

</div>

Hi, I need to find the position of some substrings inside of a long  
string. For this I’m using a loop that uses str.index(pattern,  
(last\_found\_position+1)) so I find all positions where the pattern  
matches. The pattern is a string of 20 chars, different each time I  
run the script. That worked perfect. The problem is that now I need to  
find all positions where the pattern matches 12 or more chars.  
For example: For the pattern “aaaaaa”, find substrings “aaaaaa”,  
“aaabaa”, “baaaaa”, “ababaa”, etc

First I thought that I could create all possible patterns (with \w)  
and check them, but I realized that there would be a lot of different  
patterns to check (over a few hundreds I think).  
Is there any way to do this without the need of checking a lot of  
patterns?  
thanks

---

<div class="post-metadata">

**Author:** ![egrasso](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/e/87869e/32.png) [@egrasso](https://www.ruby-forum.com/u/egrasso)\
**Post date:** [July 14, 2008, 4:22pm UTC](https://www.ruby-forum.com/t/regexp-with-gaps/143019/2 "2008-07-14T16:22:29Z")

</div>

> The problem is that now I need to  
> find all positions where the pattern matches 12 or more chars.  
> For example: For the pattern “aaaaaa”, find substrings “aaaaaa”,  
> “aaabaa”, “baaaaa”, “ababaa”, etc
> 
> First I thought that I could create all possible patterns (with \w)

\w{12,}

Right?

Either that or \w{12}\w\*

---

<div class="post-metadata">

**Author:** ![egrasso](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/e/87869e/32.png) [@egrasso](https://www.ruby-forum.com/u/egrasso)\
**Post date:** [July 15, 2008, 5:23am UTC](https://www.ruby-forum.com/t/regexp-with-gaps/143019/3 "2008-07-15T05:23:17Z")

</div>

Mmmmm… nop. I think I didn’t explain the idea very well… I’m writing  
a  
script to find specific secuences of DNA (binding sites) inside of a  
large  
secuence of DNA (for thosse who doesn’t know, DNA sequences are made of  
4  
diferent bases: A, T, C and G). The problem is that the binding sites  
don’t  
need to be 100% exact to work. For example, the binding site for an X  
protein is “AAATTT”, but the protein can also bind to the secuence  
“AAAGTT”  
or “AACGTT” and work fine. I need to find all this sites, but the only  
data  
I have is that “Protein X binds to AAATTT”.  
I finally solve the problem without using str.index nor regexp,  
basically,  
I seek it manually:

(Note: variables are in spanish!: buscarBS=find binding site,  
patron=pattern, semejanza=1 to 0, minimal similarity, cadena=string,  
respuesta=answer, largo=length)

def buscarBS(patron, semejanza=0.6, cadena=@secuencia)  
respuesta = “”  
i = 0.0  
j = 0.0  
largoc = cadena.length  
largop = patron.length

while i \<= (largoc-largop)  
j = 0.0  
puntos = 0.0  
subpuntos = largop \* (1-semejanza)

while (j \< largop) and (subpuntos \> 0)  
pos = i + j  
if cadena[pos] == patron[j] then  
puntos +=1  
else  
subpuntos -=1  
end  
j+=1  
end  
if (puntos / largop) \>= semejanza then  
respuesta = respuesta + “desde: “+(i+1).to\_i.to\_s+” hasta:  
“+(i+j).to\_i.to\_s+” - similitud: - “+(puntos / largop \* 100).to\_s+”%\n”  
end  
i+=1  
end

if respuesta == “” then  
respuesta = “No se encontro ninguna secuencia similar (similitud:  
#{semejanza} - #{patron})”  
else  
respuesta = “\nSe encontraron las siguientes  
similitudes:\n\n”+respuesta  
end  
return respuesta

end

I still need to polish and optimize the code but it find all possible  
sites with at least an specific similarity and tells me how similar they  
are. If anyone have another idea, need more details about the code or is  
interested in bioinformatic with ruby tell me.  
Thanks

---

<div class="post-metadata">

**Author:** ![egrasso](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/e/87869e/32.png) [@egrasso](https://www.ruby-forum.com/u/egrasso)\
**Post date:** [July 15, 2008, 11:16am UTC](https://www.ruby-forum.com/t/regexp-with-gaps/143019/4 "2008-07-15T11:16:02Z")

</div>

-------- Original-Nachricht --------

> Datum: Tue, 15 Jul 2008 12:18:09 +0900  
> Von: removed\_email\_address@domain.invalid  
> An: removed\_email\_address@domain.invalid  
> Betreff: Re: regexp with gaps

> I have is that “Protein X binds to AAATTT”.  
> j = 0.0  
> if cadena[pos] == patron[j] then  
> i+=1
> 
> > > find all positions where the pattern matches 12 or more chars.

Hi —

you could make use of the McIlroy-Hunt longest common subsequence (LCS)  
algorithm,  
which will give you longest common subsequences, and also information of  
the type

‘sequence AAATTT is transformed into AAAGTT by changing T to G at the  
fourth entry.’

You can find a Ruby gem implementation here:  
[http://raa.ruby-lang.org/project/diff-lcs/](http://raa.ruby-lang.org/project/diff-lcs/)

Best regards,

Axel