Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí toán học quốc tế đề tài: Bounds for DNA codes with constant GC-content | Bounds for DNA codes with constant GC-content Oliver D. King Department of Biological Chemistry and Molecular Pharmacology Harvard Medical School Boston MA USA oliver_king@ Submitted Jun 10 2003 Accepted Aug 30 2003 Published Sep 8 2003 MR Subject Classification 05B40 Abstract We derive theoretical upper and lower bounds on the maximum size of DNA codes of length n with constant GC-content w and minimum Hamming distance d both with and without the additional constraint that the minimum Hamming distance between any codeword and the reverse-complement of any codeword be at least d. We also explicitly construct codes that are larger than the best previously-published codes for many choices of the parameters n d and w. Introduction Libraries of DNA words satisfying certain combinatorial constraints have applications to DNA barcoding and DNA computing see . 17 and the references therein . The goal is to design libraries that are as large as possible given the constraints. We first review some terminology and notation - see 16 17 for more context. Let Zq denote the -character alphabet 0 . q 1 . By a q-ary word of length n we mean an element x of Zq which we write as x X1 xn. A q-ary code of length n is just a subset of Zq and the elements of the code are called codewords. The Hamming distance H x y between two q-ary words x and y of length n is defined to be the number of coordinates in which they differ and the Hamming weight of x is the number of coordinates in which it is nonzero. The maximum cardinality of a q-ary code of length n for which the minimum Hamming distance between two distinct codewords is at least d is denoted Aq n d . If we also require each codeword to have Hamming weight w . that the code be a constantweight code the maximum cardinality is denoted Aq n d w . A DNA code is a q-ary code with q 4 we identify the elements 0 1 2 3 G Z4 with the nucleotides A C G T in that order . The reverse complement of a DNA word x X1 xn is denoted
