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!