Tables of lower bounds for DNA codes with constant GC-content

Guide to superscripts:

t: template-map construction from [LLCC];
s: stochastic local search from [THC] or [TH];
p: from Proposition 1 of [K];
l: lexicographic construction from [K] or [GK];
c: linear coding construction from [GK];
m: miscellaneous (non-linear, non-lexicographic) construction from [GK];
d: personal communication from Dan Tulpan [T];
a: stochastic local search from [CL];
b: stochastic local search reported in [CL] due to X. Lu, Z. Shi, T. Wang, Y. Wang;
v: variable neighborhood search from [MS].

Multiple superscripts are occasionally given when codes have special structure (e.g. "l" and "c"), except when "p" applies.
Entries followed by periods are optimal by the Johnson-type upper bounds in [K].
Entries followed by are colons are optimal by max-clique computations in [CL].

References:

[LLCC] M. Li, H.J. Lee, A.E. Condon, and R.M. Corn. DNA word design strategy for creating sets of non-interacting oligonucleotides for DNA microarrays. Langmuir, vol. 18 (2002), 805--812.
[THC] D.C. Tulpan, H.H. Hoos, and A.E. Condon. Stochastic local search algorithms for DNA word design. In DNA Computing: 8th International Workshop on DNA-Based Computers (2002), pp. 229--241.
[TH] D.C. Tulpan and H.H. Hoos. Hybrid randomised neighbourhoods improve stochastic local search for DNA code design. In Advances in Artificial Intelligence: 16th Conference of the Canadian Society for Computational Studies of Intelligence (2003), pp. 418--433.
[K] O.D. King. Bounds for DNA codes with constant GC-content. Electronic Journal of Combinatorics, vol. 10 R33 (2003), 13pp.
[GK] P. Gaborit and O.D. King. Linear constructions for DNA codes. Theoretical Computer Science, vol. 334 (2005), 99--113.
[T] D.C. Tulpan, "Stochastic Local Search for DNA Strand Design". Ph.D. thesis, 2006.
[CL] Y.M. Chee and S. Ling. Improved Lower Bounds for Constant GC-Content DNA codes. IEEE Transactions on Information Theory, vol. 54 (2008), 391--394.
[MS] R. Montemanni and D.H. Smith. Construction of constant GC-content DNA codes via a Variable Neighbourhood Search algorithm. Preprint, 2008.

Please e-mail Philippe Gaborit (gaborit-at-unilim.fr) or Oliver King (ok-at-csua.berkeley.edu) with improvements or questions.

Lower bounds for A₄^GC(n,d,w):

n\d	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20
4	12.^s,l	4.^p	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-
5	30:^m	10.^l	3.^p	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-
6	112^m	40.^l	8:^s,l	4.^p	-	-	-	-	-	-	-	-	-	-	-	-	-	-
7	274^m	72^m	22^l	7.^l	3.^p	-	-	-	-	-	-	-	-	-	-	-	-	-
8	1056^m	256^d	56^l,c	28^v	5.^l	4.^p	-	-	-	-	-	-	-	-	-	-	-	-
9	3012^m	555^m	134^a	40^l	16^m	5.^l	3.^p	-	-	-	-	-	-	-	-	-	-	-
10	10622^m	1710^a	420^c	116^c	34^v	16.^l	5.^l	4.^p	-	-	-	-	-	-	-	-	-	-
11	32636^m	7392^c	1848^c	462^c	73^v	32^l	11.^v	4.^l	3.^p	-	-	-	-	-	-	-	-	-
12	118272^c	29568^c	2994^m	1848^c	183^v	68^l	24^v	9.^m	4.^p	4.^p	-	-	-	-	-	-	-	-
13	473088^c	109824^c	8614^m	1921^m	440^l	134^m	46^v	20^l	8.^m	4.^l	3.^p	-	-	-	-	-	-	-
14	1537536^c	384384^c	27456^l	6076^c	1534^c	404^c	112^m	38^l	16^m	8.^l	4.^p	4.^p	-	-	-	-	-	-
15	6589440^c	1647360^c	96096^c	25740^c	6470^c	1575^c	225^m	107^c	32^v	14^v	6.^m	4.^m	3.^p	-	-	-	-	-
16	26357760^c	6589440^c	411840^c	111360^c	25880^c	6680^c	532^m	177^l	117^c	60^c	12.^m	5.^m	4.^p	4.^p	-	-	-	-
17	105431040^c	26357760^c	1555840^c	390080^c	48620^c	24310^c	1272^l	380^l	132^l	123^c	23^v	9.^m	5.^m	4.^m	3.^p	-	-	-
18	210862080^c	26357760^c	5601024^c	1400704^c	87516^c	87516^c	3192^l	920^l	280^v	123^c	44^v	19^v	9.^m	5.^m	4.^p	4.^p	-	-
19	756760576^c	94595072^c	22404096^c	5922048^c	370128^c	92378^c	7038^m	2047^v	615^v	206^v	81^v	37^v	15^m	8.^m	5.^m	4.^m	3.^p	-
20	3027042304^c	378380288^c	94595072^c	23688192^c	1478048^c	369120^c	23100^c	5882^c	1461^c	457^v	166^v	67^v	31^c	13^m	8.^m	5.^m	4.^p	4.^p

(examples of linear codes from which entries were derived)

Lower bounds for A₄^GC,RC(n,d,w):

n\d	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20
4	6.^s,l	2.^p	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-
5	15:^l	3:^l	1.^p	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-
6	44^a	16:^l	4.^l	2.^p	-	-	-	-	-	-	-	-	-	-	-	-	-	-
7	135^a	36^b	11:^m	2:^l	1.^p	-	-	-	-	-	-	-	-	-	-	-	-	-
8	528^m	128^d	28^b	12^s	2.^p	2.^p	-	-	-	-	-	-	-	-	-	-	-	-
9	1354^m	275^a	67^a	20^a	8^m	2.^l	1.^p	-	-	-	-	-	-	-	-	-	-	-
10	4542^m	855^a	175^a	54^c	16^a	8.^l	2.^p	2.^p	-	-	-	-	-	-	-	-	-	-
11	14405^m	2457^m	477^a	117^a	37^v	14^v	5.^m	2.^m	1.^p	-	-	-	-	-	-	-	-	-
12	58976^c	14624^c	1381^v	924^c	87^v	29^v	11^m	4.^s,l	2.^p	2.^p	-	-	-	-	-	-	-	-
13	167263^m	27376^c	3974^v	924^c	206^v	62^v	22^a	9^m	4.^m	2.^m	1.^p	-	-	-	-	-	-	-
14	430080^c	192192^c	11878^c	2963^c	749^c	180^c	48^v	19^v	8^v	4.^m	2.^p	2.^p	-	-	-	-	-	-
15	1646240^c	411821^c	25670^c	6634^v	1600^c	347^v	106^v	37^v	18^m	6^m	3.^m	2.^m	1.^p	-	-	-	-	-
16	13174400^c	3293600^c	55376^c	55376^c	12864^c	3264^c	238^v	78^v	52^c	24^c	5^m	2.^p	2.^p	2.^p	-	-	-	-
17	26355520^c	6587200^c	97450^c	97450^c	12864^c	6060^c	579^v	172^v	60^v	30^c	11^m	4.^m	2.^m	2.^m	1.^p	-	-	-
18	44808192^c	11202048^c	698592^c	698592^c	41784^c	10496^c	1459^l	407^l	129^m	47^m	20^m	9^m	4.^m	2.^p	2.^p	2.^p	-	-
19	47102080^c	23647760^c	698592^c	698592^c	46838^m	11319^c	3519^m	960^v	285^v	96^v	37^v	16^m	7^m	4.^m	2.^m	2.^m	1.^p	-
20	756760576^c	189189536^c	11806240^c	11806240^c	184756^c	184756^c	11452^c	2868^c	766^c	179^c	76^v	31^v	14^m	6^m	4.^m	2.^p	2.^p	2.^p

(examples of linear codes from which entries were derived)

Last updated February 25, 2008
Previous version

Tables of lower bounds for DNA codes with constant GC-content

Lower bounds for A4GC(n,d,w):

Lower bounds for A4GC,RC(n,d,w):

Lower bounds for A₄^GC(n,d,w):

Lower bounds for A₄^GC,RC(n,d,w):