# Generate Max Number of Sequences Separated by Hamming Distance of 3

I'm interested in whether there is an algorithm for generating the maximum possible number of DNA sequences that are $$7$$ nucleotides long that differ by at least $$3$$ nucleotides:

• I believe this is similar, though not identical, to attempting to generate as many $$14$$ digit binary sequences that differ by at least $$3$$ bits.
• Is there an algorithm for doing this ?.

A little more background:

• I have written code that makes a list, randomly generates $$7$$ nucleotide sequences, and adds them to the list if they're $$3$$ or more nucleotides away from all sequences in the list.
• I can get $$\sim 300$$ sequences this way.
• However, the Hamming bound suggests I should be able to get $$\leq 744$$ sequences.
• For my application, I need as many as possible.
• So, I am interested in algorithms that efficiently fill sequence space with the maximum possible number of sequences.

Update 7/31/24:

I believe the best way to do this is that this article describes a way to generate 8192 9-letter quaternary sequences. With this list, I could:

1. identify at least 8192/4=2048 sequences whose nth letter match
2. Select these sequences and trim the nth letter. Because they were all separated by a Hamming distance of 3 and the only letter I trimmed was identical in all sequences, this will yield 204& 8-letter sequences
3. Repeat to trim to 512 7-letter sequences

However, I do not really understand how the above article generated 8192 9-letter sequences, and an algorithm they use (wclique) is, as far as I can tell, not readily available to download. Any guidance on how to implement the algorithm described in the article above to generate 8192 9-letter sequences would be much appreciated!

Update 8/2/24:

Was able to understand the algorithm in the above paper and successfully generated by list. Thanks all for the help!

• "generate as many 14 digit binary sequences that differ by at least 3 bits" That looks wrong to me. You can regard a 7-length sequence of a quaternary alphabet as a 14-length binary sequence. But 3 differences in the binary sequence don't translate necessarily to 3 differences in the quaternary sequence. Commented Jul 17 at 22:10
• Please accept the answer math.stackexchange.com/help/someone-answers Commented Jul 18 at 12:21
• Agreed that 14-length binary sequences with distance 3 is not identical, but I thought it would be much more likely there was an algorithm for binary sequences and thought it would be very straightforward to convert them to 7-letter quaternary sequences and after that trim any sequences that were shifted to be <3 away from other sequences Commented Aug 1 at 14:47

Edit: The following doesn't work. I may not have time to get back to it for a while, sorry.

The paper by Bogdanova et al available here constructs a code demonstrating $$A_4(7,4)\geq 128,$$ on page 339, via some base vectors and permutations acting on them. Now take this code, call it $$C$$ and fix a coordinate, say the first one. Then for each codeword replace the symbol there by an arbitrary symbol from $$\{0,1,2,3\}.$$ This gives you 4 codewords in a new code $$C'.$$ But these 4 codewords would be at distance one apart, invalidating the argument

Clearly $$d_{min}(C')=3,$$ since changing a coordinate can reduce distance by at most $$1,$$ and $$|C'|=4|C|=512.$$

How exactly are you applying the Hamming bound?*

Note that a Hamming distance of $$3$$ which you would take over a binary codeword of length $$14$$ will include codewords which don't match your constraints, since a distance of 3 could convert to a distance of only $$\lceil 3/2\rceil=2$$ over the quaternary alphabet.

What you are after are quaternary codes (use $$\mathbb{Z}_4$$ as alphabet). There are relations to binary codes, via a Gray map, but the most well known of those codes in the guise of Kerdock or Preparata codes

https://encyclopediaofmath.org/wiki/Kerdock_and_Preparata_codes

or Family A, in terms of near optimal quadriphase CDMA sequences

https://encyclopediaofmath.org/wiki/Correlation_property_for_sequences

are $$\mathbb{Z}_4-$$linear (as well as cyclic over the quaternary alphabet). You do not have to have this constraint. All you want is a collection of strings. Plus these codes actually optimize the Lee distance not the Hamming distance.

For arbitrary quaternary codes, I am not as familiar with the results, but the table from Brouwer's home page

https://www.win.tue.nl/~aeb/codes/quaternary-1.html

has the bounds $$512\leq A_4(7,3)\leq 596$$ where $$A_q(n,d)$$ is defined as the size of the largest code with minimum Hamming distance $$d$$ of length $$n$$ over an alphabet of size $$q.$$

He does not link to the construction giving the lower bound in the references, however. The paper https://arxiv.org/pdf/1602.02531 may have pointers to where to find the construction (it is relevant to the upper bound).

• This answer was incredibly helpful, thank you! Commented Jul 15 at 18:49
• @ReedTrende If you found this answer useful, you should upvote it, and eventually accept it. Commented Jul 17 at 22:35
• For the construction from Bogdanova et al - (1) I am having a hard time downloading the algorithm they used to make their construction, but (2) even if I could, I don't think I can permute the codewords like you're describing. As I understand it, you're saying to take the first letter of the code word and randomize it, giving me 4x as many codewords. However, the codewords that differ only at the randomized letter will only be separated by Hamming distance 1. Commented Jul 19 at 18:36
• For example, if one of my codewords in A4(7,4) is 0000000, if I try to add 1000000, 2000000, and 3000000 to construct A4(7,3), while each of the new codewords will differ from the other codewords in A4(7,4) by Hamming distance >=3, they only differ from each other by Hamming distance 1 Commented Jul 19 at 18:38