Sequence Generation with Combinations and Permutations

Question

I am trying to generate a set of genetic sequences with conditions. The problem uses a base 4 numerical notation:

nucleotides = ['A','C','G','T']

From this, I'd like to generate as many sequences as possible of 10 nucleotides long, e.g.

ACGCTATACA
ACGCATCTAA
...

On condition that all sequences in the set have at least 5 or more nucleotides in the same character position different. In the previous example, the positions 5,6,7,8,9 (TATAC vs ATCTA) are different giving it a distance of 5 satisfying our criteria.

For sequences of 4 bases, the following set satisfies a distance of at least 3 (No pair of sequences has more than one common same-position nucleotide):

    ACGT
    CATG
    GTAC
    TGCA
    GCTA
    TAGC
    ATCG
    CGAT
    TCAG
    GACT
    CTGA
    AGTC
    AAAA
    CCCC
    GGGG
    TTTT

The problem relates to the Kirkman's Schoolgirl Problem.

The problem could be solved computationally by generating sequencing one-by-one whilst verifying the condition at every step. I am curious if there is a mathematical approach.

How could I approach generating a set for 10 bases with a distance of at least 5? How can I generalise this to n bases and at least d distance?

Answer 1

According to this table an $(n,d)=(10,5)$ quaternary code can have at least $1024$ different strings but not more than $2045.$

An example giving the lower bound can likely be described simply using the field with $4$ elements.

The upper bound seems weak. There are $w=1048576$ words. For each one chosen there are $30$ which differ from it in exactly one place and $405$ in exactly two. $\frac{w}{436}=2404.99$ This does not yet account for words at distance $3$ or $4$ from one or more chosen ones.