# Bioinformatics meets Combinatorics. How to find a subset in a combinatorial problem?

I’m having a bioinformatics related problem. Let me walk you through it:

The DNA base ambiguity code can be represented by 15 letters, where each codes for a different subset of DNA bases therefore giving each letter a degeneracy:

Code    DNA bases   Degeneracy
A       A           1
C       C           1
G       G           1
T       T           1
R       A,G         2
Y       C,T         2
S       G,C         2
W       A,T         2
K       G,T         2
B       C,G,T       3
D       A,G,T       3
H       A,C,T       3
V       A,C,G       3
N       A,C,G,T     4


So a sequence like CBKGNWCV has a total degeneracy (or number of encoded specific DNA base sequences) of 1*3*2*1*4*2*1*3 = 144. This sequence is one out of 15^8 possible sequences of length eight representable by this code.

I’m not interested in all 15^8 sequences, but only in those which have a specific total degeneracy. I would like to have a formula or easy recursive algorithm that provides me how many possible sequences with one specific total degeneracy and with one specific sequence length there are and a way to generate those sequences. So that I know, for instance, that in the set of degenerate sequences of length 8 with a total degeneracy of 144, the sequence number 110’305’178 is CBKGNWCV.

Is there any set of formulas, theorem, … you might have heard of that could help me with this issue? Maybe you heard already of a similar problem and it’s solution. For me this sounds roughly like combinatorics with coding theory, but those fields are to broad for me to find something without having a deeper mathematic or computer theoretic understanding.

So far I approached this problem by generating all these sequencing by counting from 0 to 15^8 and converting each number into pentadecimal numbers represented by the letter code and in parallel a 8 digit number consisting of their corresponding degeneracies. So I could extract for each sequence by the product of digits a total degeneracy and sort the corresponding code sequences according to their total degeneracy into different lists. This creates a huge data base that’s not really convenient. Anyway I can then read only the sequences of a specific total degeneracy into my program to further work with them. Generating the sequences in the same way directly inside my program and discarding all the time sequences that don’t have the specific total degeneracy seems very inefficient to me.

That’s why I would like to find a more mathematical approach to filtering the sequences I need. I’m not expecting a complete solution to my very specific problem, of course. I’m just having trouble to find any literature that might help me with this. So any clue or even just some keywords to look for would be really great help already!

Thank you!

• I don't understand what you mean by " the sequence number 110’305’178 is CBKGNWCV" – Gregory Grant Mar 31 '15 at 20:16
• @GregoryGrant I would like to build a function like $f(D, n) \rightarrow S$ where $D$ is the chosen total degeneracy, $n$ goes from 0 to the number of sequence combinations with $D$ (202'997'760 in the case of $D=144$), and $S$ is either a number that I can convert into a pentadecimal representation as I did it before or directly the sequence string. 110’305’178 was just an arbitrary number as example input for $n$. – Daniel Mar 31 '15 at 20:58

Suppose the length is $m$ and the total degeneracy is $n$. Then factor $n$ into primes. If $n$ is a total degeneracy it must factor as $2^a3^b$. Now if $a=0$ the number of ways is just the number of places you can put the $b$ $3$'s. So $m\choose 3$. Then multiply by the number of different symbols that give you the right number of 1's and 3's. If $a=1$ then you have to place one two and $m$ 3's. So $m\cdot{{m-1}\choose{b}}$. The case $a>1$ is tricker but you can probably work it out.