In this text we use the cross-correlation method using the fast Fourier transform to present a simple algorithm, with a time complexity of O(NlogN), in order to calculate the exact value of the cyclic Hamming distance between two sequences of length N over any alphabet of size k. It may be useful in applications where we only want to know that value, like in sequence alignment, without taking into account insertions and deletions. 1 Introduction There are many string metrics for measuring the edit distances between two sequences, the most common is the Levenshtein distance [1], which allows insertions, deletions and substi- tutions. Another useful metric is the Hamming distance [2], which allows only substitutions. In this text we will focus on the creation of a simple and efficient algorithm to get the min- imum cyclic Hamming distance between two sequences using the well-known techniques of cross-correlation and FFT; although it is probably a known method, it is not easy to find an explicit and simple algorithm to do this task [3]. It will be especially useful for sequence alignment applications, in situations where only substitutions are allowed and we want to know the exact Hamming distance, not only a cross-correlation measure [4]. Let’s make a quick summary of basic concepts before present our algorithm. We have the following scenario: given two sequences x={x0, . . . , x nx−1}andy={y0, . . . , y ny−1}over an alphabet of size k, where nx≥ny, we want to get the cross-correlation values ( x ⋆ y )n. As both sequences should have equal length N=nx, in case nx> n yit is a common practice to do a zero-extension of y. First of all, the (circular) cross-correlation for two sequences x, y∈CNis defined by: (x ⋆ y)n=N−1X m=0xm·y∗ (m−n)mod Nn= 0, . . . , N −1 (1) The Discrete Fourier Transform (DFT) of xis denoted by F{x}=X={X0, . . . , X N−1}, where Xkis calculated as: Xk=N−1X n=0xne−2πi Nknk= 0, . . . , N −1 (2) 1 The Inverse Discrete Fourier Transform (IDFT) of Xis denoted by F−1{X}=x, where xn is calculated as: xn=1 NN−1X k=0Xke2πi Nknn= 0, . . . , N −1 (3) As both DFT and IDFT have similar expressions, any implementation to calculate DFT can easily calculate IDFT (the asterisk means the complex conjugate): F−1{X}=1 NF∗{X∗} (4) The cross-correlation theorem satisfies the following (the multiplication is pointwise): x ⋆ y =F−1{F{x} · F∗{y}} (5) The most common practice to calculate x ⋆ y is the use of the cross-correlation theorem, but computing DFT or IDFT directly from the definition has a time complexity of O(N2), too slow to be practical. The use of Fast Fourier Transform (FFT) to compute the DFT and IDFT reduces the time complexity to O(NlogN). The value of Nis not a problem for current FFT algorithms [5]. 2 Algorithm The real scenario is slightly different to the previous one, because we are interested in he cyclic Hamming distance instead of the cross-correlation. Definition 2.1. The Hamming distance d(x, y)between two sequences of equal length is defined as the minimum number of substitutions required to change one string into the other. d(x, y) = #{j:xj̸=yj, j={0, ..., N −1}} (6) Definition 2.2. Given two sequences x and y, the number of coincidences c(x, y)is the number of positions at which the corresponding symbols are equal. c(x, y) = #{j:xj=yj, j={0, ..., N −1}}=N−d(x, y) (7) Definition 2.3. The cyclic Hamming distance dmin(x, y)is the minimum Hamming distance between xand each possible rotation of y, dmin(x, y) = min j∈[0. .N−1]{d(x, rj(y))}, (8) where rj(y)is the j-th rotation of y. Given two sequences x={x0, . . . , x nx−1}andy={y0, . . . , y ny−1}over an alphabet of size k, where nx≥ny, we want to get the cyclic Hamming distance dmin(x, y). As both sequences should have equal length N=nx, in case nx> n ywe will make a k-extension of y(i.e. filling with a value equal to k, which is outside of our alphabet). The direct computation of this has a time complexity of O(N2), so we should think of a more efficient way to do it. Let’s see if we can take benefit of the cross-correlation method, giving us a time complexity of O(NlogN). 2 Proposition 2.1. Given two binary sequences xandy, and encoding symbol 0 as number 0 and symbol 1 as number 1, the cross-correlation x ⋆ y gives the number of coincident ones between both sequences. Theorem 2.1. Given two sequences xandy, we can denote c(x, y)as the following sum: c(x, y) =k−1X i=0v(i)(x)⋆ v(i)(y) (9) v(i) j(z) =( 1ifzj=i 0ifzj̸=ij= 0, ..., N −1 Proof. We can decompose (7) as the following sum, making the comparisons separately for each symbol of our alphabet: c(x, y) =k−1X i=0#{j:xj=i∧yj=i, j={0, ..., N −1}} We can also denote sequences xandyby a sum of binary vectors multiplied by each symbol, where a value of 1 in the vector means that the symbol appears in that position in the sequence. x=k−1X i=0i·v(i)(x) y=k−1X i=0i·v(i)(y) As the number of coincidences of ones between v(i)(x) and v(j)(y) must be 0 ∀i̸=jbecause they refer to different symbols, we can denote c(x, y) by: c(x, y) =k−1X i=0#{j:v(i) j(x) = 1∧v(i) j(y) = 1 , j={0, ..., N −1}} Applying Proposition 2.1 to the content of the sum we finally come to expression (9). In summary: 1. We compute in (9) the number of coincidences c(x, y) (keep in mind that it is a vector), with a time complexity of ktimes O(NlogN). 2. Then we apply (7) for the computation of the Hamming distance d(x, y) (again, it is a vector). 3. We finally apply (8) to get the cyclic Hamming distance dmin(x, y) and the offsets of y overxwhere we obtain that value. We can allow all rotations of yor not (see Algorithm 1 for a simple implementation, without optimizations). 3 Algorithm 1 Compute cyclic Hamming distance dmin(x, y), requiring nx≥ny Input: x,y,nx,ny,k,cyclic Output: dmin,offsets 1:N←nx 2:offsets ←[ ] ▷Empty array 3:ifnx> n ythen 4: y[ny, ..., n x−1]←k ▷ k-Fill to make equal length 5:c[0, ..., N −1]←0 ▷Vector initialization for c(x, y) 6:fori= 0 to k−1do 7: forj= 0 to N−1do ▷Create binary sequences vx≡v(i)(x) and vy≡v(i)(y) 8: ifx[j] =ithen 9: vx[j]←1 10: else 11: vx[j]←0 12: ify[j] =ithen 13: vy[j]←1 14: else 15: vy[j]←0 16: corr←Re{IFFT (FFT(vx)·FFT∗(vy))} ▷Cross-correlation vector in O(NlogN) 17: c←c+corr ▷ Accumulate vector values 18:ifcyclic =True then ▷All rotations allowed? 19: range ←N−1 20:else 21: range ←nx−ny 22:cmax←max{c[0, ..., range ]} ▷Find dminand offsets 23:forj= 0 to range do 24: ifc[j] =cmaxthen 25: offsets. Append (j) 26:dmin←N−cmax 3 Example Let’s suppose an example of sequence alignment for DNA: we have sequences CCGATTCC and CCA over an alphabet of 4 symbols {C,G,A,T }. Doing the alignment by hand, we get dmin(x, y) = 6 for offsets {0,1,6,7 }(see Table 1, best results in bold). If we are not interested in all rotations of yaround x, but only in those inside the windowed space of x(cyclic =False in Algorithm 1), then we obtain the same value for dmin(x, y) but only for offsets {0,1}. 4 Table 1: Manual sequence alignment Offset C C G A T T C C c(x, y)d(x, y) 0 C C A - - - - - 2 6 1 - C C A - - - - 2 6 2 - - C C A - - - 0 8 3 - - - C C A - - 0 8 4 - - - - C C A - 0 8 5 - - - - - C C A 1 7 6 A - - - - - C C 2 6 7 C A - - - - - C 2 6 Now, let’s use Algorithm 1 step by step: 1. In our example we initially have k= 4, nx= 8 and ny= 3, then N= 8. We encode alphabet {C,G,A,T }as{0,1,2,3 }, and sequences as x={0,0,1,2,3,3,0,0}andy= {0,0,2,4,4,4,4,4}. The initial vector of coincidences is c(x, y) ={0,0,0,0,0,0,0,0}. 2. Iteration i= 0. Take in mind that corr =v(i)(x)⋆v(i)(y) and c(x, y) is the accumulated number of coincidences. Offset 0 1 2 3 4 5 6 7 v(0)(x)1 1 0 0 0 0 1 1 v(0)(y)1 1 0 0 0 0 0 0 corr 2 1 0 0 0 1 2 2 c(x, y)2 1 0 0 0 1 2 2 3. Iteration i= 1. Observe that, when one of the vectors is a zero vector, the cross- correlation is also a zero vector. Offset 0 1 2 3 4 5 6 7 v(1)(x)0 0 1 0 0 0 0 0 v(1)(y)0 0 0 0 0 0 0 0 corr 0 0 0 0 0 0 0 0 c(x, y)2 1 0 0 0 1 2 2 4. Iteration i= 2. Offset 0 1 2 3 4 5 6 7 v(2)(x)0 0 0 1 0 0 0 0 v(2)(y)0 0 1 0 0 0 0 0 corr 0 1 0 0 0 0 0 0 c(x, y)2 2 0 0 0 1 2 2 5 5. Iteration i= 3. In this final iteration we get the best result of dmin(x, y) = 6 for offsets {0,1,6,7 }, marked in bold. Same results of Table 1, as we expected. Offset 0 1 2 3 4 5 6 7 v(3)(x)0 0 0 0 1 1 0 0 v(3)(y)0 0 0 0 0 0 0 0 corr 0 0 0 0 0 0 0 0 c(x, y)2 2 0 0 0 1 2 2 d(x, y)6 6 8 8 8 7 6 6 4 Conclusion We have successfully done a simple and efficient algorithm to know the exact value of the cyclic Hamming distance between two sequences, in order to be used in sequence alignment applications or other situations. Take in mind that the time complexity is O(NlogN) as long as k≪N, but that will usually be the case.