# Learning Q-gram distance

#### aka n-gram

Posted by Riino Site on February 26, 2021 algorithm

Some content of this article comes from the slide of Zsuzsanna Liptak.

## Introduction

Q-gram, aka n-gram, is an algorithm to compare two strings with a given alphabet.

It is used in string retrieval with $O(n)$ and a fixed static number $q$ (in n-gram’s case, this will be marked as $n$)

## Definition of q-gram

q-gram is a string of length $q$, with a given alphabet $\Sigma$ with length $\sigma$.

For example, here we define : $$\Sigma=\{'A','C','G','T'\}$$ thus $\sigma = 4$, if we define $q=2$, and we can choose q-grams from alphabet with a custom approach, like using lexicographic order.

Here we CAN select these strings over $\Sigma$ :AA,AC,AG,AT,CA,CC,CG,CT,GA,GC,GG,GT,TA,TC,TG,TT

## Definition of occurrence count

With an array of q-grams , we can define occurrence count with a given string $s$: $$N(s,q-gram)=|\{i:s_i\dots s_{i+q-1}\}|$$ e.g. Let $s$ = ‘ACAGGGCA’ and $q=2$, then $N(s,AC)=N(s,AG)=N(s,GC)=1$

In another word, $N$ is the number of count that a g-gram figures in $s$

## Definition of q-gram table

With a axes of strings we want to compare, and another axes of q-grams, we can fill occurrence count into this matrix:

for $s$= ‘ACAGGGCA’, $t$=’GGGCAACA’, $v$=’AAGGACA’, q-gram profiles = AA,AC,AG,AT,CA,CC,CG :

$u$ $P_q(s)$ $P_q(t)$ $P_q(v)$
AA 0 1 1
AC 1 1 1
AG 1 0 1
AT 0 0 0
CA 2 2 1
CC 0 0 0
CG 0 0 0

## Definition of q-gram distance

For two strings $s$ and $t$, the q-gram distance is : $$dist_{q-gram}(s,t)=\sum_{u\in\sum q}|N(s,u)-N(t,u)|$$ or equivalently: $$dist_{q-gram}(s,t)=\sum_{i=1}^{\sigma^q}|P_q(s)[i]-P_q(t)[i]|$$ which is the Manhattan distance for two vectors ,which are the mapping result of given strings of q-gram profile

## Algorithm

• Use a sliding window of size $q$ over $s$ and $t$
• Use an array $d$ of size $\sigma^q$, aka the q-gram profile
• Scan s, then scan t, assign the occurrence count into $d$ with different operators.
• Now $d[r]=N(s,u_r)-N(t,u_r)$
• Sum up the absolute value of $d$
def get_q_gram_distance(s,t,qgrams,q):
n=len(s)
m=len(t)
d=[]
for i in range(len(qgrams)):
d.append(0)#init vector, O(q)

for i in range(1,n-q+1):#slide window, O(n)
for r in range(0,len(grams)):#get count, O(q)
if s[i:i+q-1] == qgram[r]:
d[r]+=1#first vector sends postive effect

for i in range(1,m-q+1):#slide window, O(m)
for r in range(0,len(grams)):#get count, O(q)
if s[i:i+q-1] == qgram[r]:
d[r]-=1#second vector sends negtive effect
res=0
for i in vector:
res+=abs(i)

return res



## Tips:

1. q-gram = 0 does not mean that two strings are same.
2. $\frac{dist_{q-gram}(s,t)}{2q}<=d_{edit}(s,t)$ , $d_{edit}(s,t)$ is the unit cost edit distance.