## 2 Pms6
### Computing \(B_{d}(C(n_{1},\cdots,n_{5}))\)
The remaining \(n_{5}-N_{5,a}-N_{5,b}-N_{5,c}\) Type 5 positions, \(k\), of \(w\) are set to the single character of the 4-letter alphabet that differs from \(x[k]\), \(y[k]\), and \(z[k]\). We see that the number of ways to populate the \(n_{5}\) Type 5 positions is \({n_{5}\choose N_{5,a}}{n_{5}-N_{5,a}\choose N_{5,b}}{n_{5}-N_{5,a}-N_{5,b} \choose N_{5,c}}\). The preceding strategy to generate \(B_{d}(x,y,z)\) generates \(3^{q}2^{r}2^{s}2^{u}{n_{1}\choose N_{1,a}}{n_{2}\choose N_{2,a}}{n_{2}-N_{2,a }\choose N_{3,a}}{n_{3}\choose N_{3,a}}{n_{3}-N_{3,a}\choose N_{3,b}}\)\({n_{4}\choose N_{4,b}}{n_{5}\choose N_{5,a}}{n_{5}-N_{5,a}\choose N_{5,b}}{n_{5}-N_{5,c} \choose N_{5,c}}\)\(l\)-mers \(w\) for each 10-tuple \((N_{1,a},\cdots,N_{5,c})\). While every generated \(l\)-mer is in \(B_{d}(x,y,z)\), some \(l\)-mers may be the same. Computational efficiency is obtained by computing \(B_{d}(x,y,z)\) for all \((x,y,z)\) in the same class \(C(n_{1},\cdots,n_{5})\) concurrently by sharing the loop overheads as the same loops are needed for all \((x,y,z)\) in a class. Algorithm 2 gives the pseudocode to compute \(B_{d}(x,y,z)\) by classes. As an example, lets say we have 3 input strings \(s_{1}=ACTG\), \(s_{2}=GCTA\) and \(s_{3}=AGTC\) and we are asked to find \((3,1)\) motifs _i.e._, motifs of length 3 with at most 1 mismatch. Also, the \(l\)-mer \(s_{i}[p]...s_{i}[p+l-1]\) is denote by \(s_{i}(p)\). In this particular case, \(l=3\) and hence \(s_{1}(1)=CTG\) for example. For the triplet \((s_{1}(0),s_{2}(0),s_{3}(0)\), _i.e._, for the triplet \((ACT,GCT,AGT)\) we have \(n1=1,n2=1,n3=1,n4=0,n5=0\). Hence it belongs to the class \(C(1,1,1,0,0)\). For the triplet \((s_{1}(1),s_{2}(0),s_{3}(0)\)_i.e._, \((CTG,GCT,AGT)\) we have \(n1=0,n2=0,n3=0,\)\(n4=1,n5=2\) and it belongs to class \(C(0,0,0,1,2)\). After evaluating all 8 triplets, we will end up having class \(C(0,0,0,1,2)=\{(s_{1}(1),s_{2}(0),s_{3}(0)),(s_{1}(0),s_{2}(1),s_{3}(1))\}\). We then need to find \(B_{1}(s_{1}(1),s_{2}(0),s_{3}(0))\) and \(B_{1}(s_{1}(0),s_{2}(1),s_{3}(1))\) to compute \(B_{1}(C(0,0,0,1,2))\). To computer \(B_{1}(s_{1}(1),s_{2}(0),s_{3}(0))\), we need to compute \(B_{1}(CTG)\cap B_{1}(GCT)\cap B_{1}(AGT)\). We can evaluate that \(B_{1}(CTG)=\{CTG,ATG,GTC,TTG,CAG,CGG,CTA,CTC,CTT\}\)\(B_{1}(GCT)=\{GCT,ACT,CCT,TCT,GAT,GGT,GTT,GCA,GCC,GCG\}\) and \(B_{1}(AGT)=\{AGT,CGT,GGT,TGT,ACT,ACT,ATT,AAT,AGA,AGC,AGG\}\) and subsequently we have \(B_{1}(CTG)\cap B_{1}(GCT)\cap B_{1}(AGT)=\phi\). Similarly, we can see that \(B_{1}(s_{1}(0),s_{2}(1),s_{3}(1))=B_{1}(ACT)\cap B_{1}(CTA)\cap B_{1}(GTC)=\phi\) and hence \(B_{1}(C(0,0,0,1,2))=\phi\). Run-time may be reduced by pre-computing data that do not depend on the string set \(S\). So, for a given pair \((l,d)\), there are \(O((l+1)^{5})\) 5-tuples \((n_{1},\cdots,n_{5})\). For each of the 5-tuples, we can pre-compute all 10-tuples (\(N_{1,a},\cdots,N_{5,c}\)) that are solutions to the ILP. For each 10-tuple, we can pre-compute all combinations (_i.e._, selections of positions in \(w\)). The pre-computed 10-tuple solutions for each 5-tuple are stored in a table with \((l+1)^{5}\) entries and indexed by \([n_{1},\cdots,n_{5}]\) and the pre-computed combinations for the 10-tuple solutions are stored in a separate table. By storing the combinations in a separate table, we can ensure that each is stored only once even though the same combination may be needed by many 10-tuple solutions. ```
ClassBd(\(C(n_{1},n_{2},n_{3},n_{4},n_{5})\)) \(B_{d}\leftarrow\emptyset\) FindallILPsolutionswithparameters\(n_{1},n_{2},n_{3},n_{4},n_{5}\) foreachsolution(\(N_{1,a},\cdots,N_{5,c}\)) { curComb\(\leftarrow\)firstcombinationforthissolution; for\(i=0\)to(#combinations) { foreachtriplet(\(x,y,z\))in\(C(n_{1},\cdots,n_{5})\) { Generate\(\mathit{ws}\)for\(\mathit{curComb}\);  Addthese\(\mathit{ws}\)to\(B_{d}\); } CurComb\(\leftarrow\)nextcombinationinGraycodeorder; } } return\(B_{d}\)
```  
**Algorithm 2**Compute \(B_{d}(n_{1},\cdots,n_{5})\)[23]. We store pre-computed combinations as vectors.