# Global Repeat Map (GRM) Application: Finding All DNA Tandem Repeat Units
## 2 Materials and Methods  
### Algorithm Outline  
In the first step, we create a \(N-k\) dimensional array, \(\mathbf{A}~{}=~{}\left\{a^{i},~{}\ldots,a^{N-k}\right\}\), of three-dimensional vectors  
\[a^{i}~{}=~{}\left(a^{i}_{1},a^{i}_{2},a^{i}_{3}\right),~{}i\in[1,N-k] \tag{1}\]  
where \(N\) is the length of the observed sequence, and \(k\) is the length of the key string (\(k=8\)). The first component of each vector in array contains the vector's position in the sequence (\(a^{i}_{1}~{}=~{}i\)), and the second component of each vector contains an integer value of the subsequence with the length of 8 bps whose first nucleotide is at the position \(a^{i}_{1}\), i.e., \(a^{i}_{2}~{}=~{}int\big{(}sequence.substring\big{(}a^{i}_{1},8\big{)}\big{)}\) (Figure 1). The third component, \(a^{i}_{3}\), represents the fragment's length in bps, and its value is calculated in the next step. In the second step, we sort array \(\mathbf{A}~{}\rightarrow~{}\mathbf{A}^{\prime}\) on two levels; the criterion for the first sorting level is the second vector's component, \(a^{i}_{2}\), and the criterion for the second sorting level is the first vector's component, \(a^{i}_{1}\). In this way, all vectors with \(a^{i}_{2}~{}=~{}int(AAAAAAAAAA)\) end up at the beginning of the array (sorted by the first component \(a^{i}_{1}\)), and all vectors with \(a^{i}_{2}~{}=~{}int(TTTTTTTT)\) end up at the end of the array (also sorted by the first component \(a^{i}_{1}\)). Note that, in the sorted array, the first component of the vector generally no longer corresponds to its position in the sequence, i.e., \(a^{i}_{1}\
eq i\). Next, we subtract the first components of all adjacent vectors and write down the difference in the third component of minuend vector, i.e., \(a^{\prime i}_{3}~{}=~{}a^{\prime i}_{1}-a^{\prime i+1}_{2}\). Because all adjacent vectors in the sorted array have identical second component, \(a^{\prime i}_{2}\), the difference written in \(a^{\prime i}_{3}\) actually represents the minimum distance between two identical key strings in a sequence, which is known as  
Figure 1: Scheme of construction of \(N-k\) dimensional array of three-dimensional vectors in the first step of the GRM algorithm. a fragment length. The exceptions are adjacent vectors in which the second component changes (for example, from \(int(AAAAAAAAAA)\) to \(int(AAAAAAAC)\)), in which case we assign zero to the the third component of the minuend. In the third step, we sort back array \(\mathbf{A}^{\prime}\) by the first component \(a^{\prime i}_{1}\) to get the initial array \(\mathbf{A}\) in which now each vector has its fragment length written in the third component. In this array, the position of each vector again corresponds to its first component, i.e., \(a^{i}_{1}~{}=~{}i\). Next, we divide resulting array in smaller subarrays of variable length \(\mathbf{B}^{j}~{}=~{}\left\{a^{j},\ldots,a^{j+n}\right\}\) where \(n\) is integer between 100 and 2000. In the case of large \(n\), the resulting subarray can contain more different TRs and the most dominant TR could saturate the others. On the other hand, too small value of \(n\) would result in excessive algorithm running time. We bypass this conundrum by starting each subarray with sufficiently small \(n~{}=~{}100\) bp, calculate its GRM diagram, and increase \(n\) as long as only peaks of one TR and its multiples are present in the GRM diagram. As the upper limit of this procedure, we took the length \(n~{}=~{}2000\) bp, because for a too large subarray, noise in the GRM diagram can mask new peaks, i.e., a new TR. In this way, we ensure that the algorithm detects all TRs without spending too much running time in the following steps. In the fourth step, we use the GRM diagram of each subarray from last step. By identifying the prominent GRM peak (fragment lengths with higher frequency), we detect dominant subarray's TR unit and its multiples.