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] or [MS2].
x: linear or nonlinear coding construction from [SAMP].

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, 805--812 (2002).
[THC] D.C. Tulpan, H.H. Hoos, and A.E. Condon. Stochastic local search algorithms for DNA word design. DNA Computing: 8th International Workshop on DNA-Based Computers, 229--241 (2002).
[TH] D.C. Tulpan and H.H. Hoos. Hybrid randomised neighbourhoods improve stochastic local search for DNA code design. Advances in Artificial Intelligence: 16th Conference of the Canadian Society for Computational Studies of Intelligence, 418--433 (2003).
[K] O.D. King. Bounds for DNA codes with constant GC-content. Electronic Journal of Combinatorics, vol. 10 R33, 13pp (2003).
[GK] P. Gaborit and O.D. King. Linear constructions for DNA codes. Theoretical Computer Science, vol. 334, 99--113 (2005).
[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, 391--394 (2008).
[MS] R. Montemanni and D.H. Smith. Construction of Constant GC-content DNA codes via a Variable Neighbourhood Search algorithm. Journal of Mathematical Modelling and Algorithms, vol. 7(3), 311--326 (2008).
[MS2] R. Montemanni and D.H. Smith. Metaheuristics for the construction of constant GC-content DNA codes. Proceedings of the VIII Metaheuristic International Conference (MIC 2009), 10pp (2009). Note: this also includes codes for 20 ≤ n ≤ 30 (with 14 ≤ d ≤ n), outside the range of these tables.
[SAMP] D.H. Smith, N. Aboluion, R. Montemanni and S. Perkins. Linear and nonlinear constructions of DNA codes with Hamming distance d and constant GC-content. Discrete Mathematics, in press (doi:10.1016/j.disc.2010.03.005). Note: this also includes codes for 20 ≤ n ≤ 30 (with 14 ≤ d ≤ n), outside the range of these tables.

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	288^v	78^v	22^l	7.^l	3.^p	-	-	-	-	-	-	-	-	-	-	-	-	-
8	1056^m	256^d	63^v	28^v	5.^l	4.^p	-	-	-	-	-	-	-	-	-	-	-	-
9	3012^m	555^m	134^a	48^v	18^v	5.^l	3.^p	-	-	-	-	-	-	-	-	-	-	-
10	10622^m	2016^v	504^x	116^c	34^v	16.^l	5.^l	4.^p	-	-	-	-	-	-	-	-	-	-
11	32636^m	7392^c	1848^c	472^x	75^v	32^l	11.^v	4.^l	3.^p	-	-	-	-	-	-	-	-	-
12	118272^c	29568^c	3696^x	1888^x	183^v	118^v	24^v	9.^m	4.^p	4.^p	-	-	-	-	-	-	-	-
13	473088^c	109824^c	8614^m	3432^x	464^x	134^m	46^v	20^l	8.^m	4.^l	3.^p	-	-	-	-	-	-	-
14	1537536^c	439296^x	28032^x	7424^x	1856^x	512^x	112^m	49^x	17^v	8.^l	4.^p	4.^p	-	-	-	-	-	-
15	6589440^c	1647360^c	103680^x	27840^x	6960^v	1920^x	240^x	124^x	34^v	15^v	6.^m	4.^m	3.^p	-	-	-	-	-
16	26357760^c	6589440^c	414720^x	111360^c	27840^x	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	1530^x	380^l	132^l	123^c	24^v	9.^m	5.^m	4.^m	3.^p	-	-	-
18	210862080^c	26357760^c	5601024^c	1400704^c	97520^x	87516^c	5508^x	920^l	282^v	180^x	46^v	20^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	213^v	83^v	38^v	17^m	8.^m	5.^m	4.^m	3.^p	-
20	3027042304^c	378380288^c	94595072^c	23688192^c	1478048^c	369512^x	24552^x	5882^c	2112^x	520^x	167^v	69^v	33^v	16^v	8.^m	5.^m	4.^p	4.^p

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	21^v	8^m	2.^l	1.^p	-	-	-	-	-	-	-	-	-	-	-
10	4542^m	855^a	176^v	54^c	17^v	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	12^v	4.^s,l	2.^p	2.^p	-	-	-	-	-	-	-	-
13	167263^m	27376^c	3974^v	924^c	206^v	62^v	23^v	10^v	4.^m	2.^m	1.^p	-	-	-	-	-	-	-
14	430080^c	192192^c	11878^c	2963^c	749^c	180^c	49^v	20^v	8^v	4.^m	2.^p	2.^p	-	-	-	-	-	-
15	1646240^c	411821^c	25670^c	6634^v	1600^c	347^v	109^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	243^v	83^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	175^v	62^v	30^c	12^v	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	133^v	49^v	21^v	10^v	4.^m	2.^p	2.^p	2.^p	-	-
19	47102080^c	23647760^c	698592^c	698592^c	46838^m	11319^c	3678^v	960^v	285^v	99^v	39^v	18^v	8^v	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	77^v	33^v	15^v	7^v	4.^m	2.^p	2.^p	2.^p

Last updated June 23, 2010

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):