## 2 Pms6
### Computing \(B_{d}(C(n_{1},\cdots,n_{5}))\)  
Let \((x,y,z)\) be a triple in \(C(n_{1},\cdots,n_{5})\) and let \(w\) be an \(l\)-mer in \(B_{d}(x,y,z)\). Then \(n_{i}\) is the number of positions of Type \(i\), \(1\leq i\leq 5\) for the triple \((x,y,z)\). Each \(n_{i}\) may be decomposed as below for all \(w\in B_{d}(x,y,z)\)[22]:  
1. \(N_{1,a}\) = number of Type 1 positions \(i\) such that \(w[i]=x[i]\). 2. \(N_{2,a}(N_{2,b})\) = number of Type 2 positions \(i\) such that \(w[i]=x[i]\)(\(w[i]=z[i]\)). 3. \(N_{3,a}(N_{3,b})\) = number of Type 3 positions \(i\) such that \(w[i]=x[i]\)(\(w[i]=y[i]\)). 4. \(N_{4,a}(N_{4,b})\) = number of Type 4 positions \(i\) such that \(w[i]=y[i]\)(\(w[i]=x[i]\)). 5. \(N_{5,a}(N_{5,b}\), \(N_{5,c})\) = number of Type 5 positions \(i\) such that \(w[i]=x[i]\)(\(w[i]=y[i]\),\(w[i]=z[i]\)). As the distance of \(w\) has to be less than or equal to \(d\) from each of \(x\), \(y\) and \(z\), the following equations result. 1. \(n_{1}-N_{1,a}+n_{2}-N_{2,a}+n_{3}-N_{3,a}+n_{4}-N_{4,b}+n_{5}-N_{5,a}\leq d\)
2. \(n_{1}-N_{1,a}+n_{2}-N_{2,a}+n_{3}-N_{3,b}+n_{4}-N_{4,a}+n_{5}-N_{5,b}\leq d\)
3. \(n_{1}-N_{1,a}+n_{2}-N_{2,b}+n_{3}-N_{3,a}+n_{4}-N_{4,a}+n_{5}-N_{5,c}\leq d\)
4. \(N_{1,a}\leq n_{1}\)
5. \(N_{2,a}+N_{2,b}\leq n_{2}\)
6. \(N_{3,a}+N_{3,b}\leq n_{3}\)
7. \(N_{4,a}+N_{4,b}\leq n_{4}\)
8. \(N_{5,a}+N_{5,b}+N_{5,c}\leq n_{5}\)
9. All variables are non-negative integers. Given a 10-tuple solution to this ILP, we may generate all \(l\)-mers \(w\) in \(B_{d}(x,y,z)\) as follows:  
1. Each of the \(l\) positions in \(w\) is classified as being of Type 1, 2, 3, 4, or 5 depending on the classification of the corresponding position in the \(l\)-mers \(x\), \(y\), and \(z\) (see Section 2.2). 2. Select \(N_{1,a}\) of the \(n_{1}\) Type 1 positions of \(w\). If \(i\) is a selected position, then, from the definition of a Type 1 position, it follows that \(x[i]=y[i]=z[i]\). Also from the definition of \(N_{1,a}\), these many Type 1 positions have the same character in \(w\) as in \(x\), \(y\), and \(z\). So, for each selected Type 1 position \(i\), we set \(w[i]=x[i]\). The remaining Type 1 positions of \(w\) must have a character different from \(x[i]\) (and hence from \(y[i]\) and \(z[i]\)). So, for a 4-character alphabet there are 3 choices for each of the non-selected Type 1 positions of \(w\). As there are \({n\choose N_{1,a}}\) ways to select \(N_{1,a}\) positions out of \(n_{1}\) positions, we have \(3^{q}{n_{1}\choose N_{1,a}}\) different ways to populate the \(n_{1}\) Type 1 positions of \(w\), where \(q=n_{1}-N_{1,a}\). 3. Select \(N_{2,a}\) positions \(I\) and \(N_{2,b}\) different positions \(J\) from the \(n_{2}\) Type 2 positions of \(w\). For each \(i\in I\), set \(w[i]=x[i]\) and for each \(j\in J\), set \(w[j]=z[i]\). Each of the remaining \(n_{2}-N_{1,a}-N_{1,b}\) Type 2 positions of \(w\) is set to a character different from the characters in \(x\), \(y\), and \(z\). So, if \(k\) is one of these remaining Type 2 positions, \(x[k]=y[k]\
eq z[k]\). We set \(w[k]\) to one of the 2 characters of our 4-letter alphabet that are different from \(x[k]\) and \(z[k]\). Hence, we have \(2^{r}{n_{2}\choose N_{2,a}}{n_{2}-N_{2,a}\choose N_{2,b}}\) ways to populate the \(n_{2}\) Type 2 positions in \(w\), where \(r=n_{2}-N_{2,a}-N_{2,b}\). 4. Type 3 and Type 4 positions are populated using a strategy similar to that used for Type 2 positions. The number of ways to populate Type 3 positions is \(2^{s}{n_{3}\choose N_{3,a}}{n_{3}-N_{3,a}\choose N_{3,b}}\), where \(s=n_{3}-N_{3,a}-N_{3,b}\) and that for Type 4 positions is \(2^{u}{n_{4}\choose N_{4,a}}{n_{4}-N_{4,a}\choose N_{4,b}}\), where \(u=n_{4}-N_{4,a}-N_{4,b}\). 5. To populate the Type 5 Positions of \(w\), we must select the \(N_{5,a}\) Type 5 positions, \(k\), that will be set to \(x[k]\), the \(N_{5,b}\) Type 5 positions, \(k\), that will be set to \(y[k]\), and the \(N_{5,c}\) Type 5 positions, \(k\), that will be set to \(z[k]\).