1,721,508 research outputs found
Construction of constant GC-content DNA codes via a variable neighbourhood search algorithm
No full textDNA codes are sets of words of fixed length n over the alphabet {A,C,G,T} which satisfy a number of combinatorial conditions. They have application in DNA computing, in DNA microarray technologies and as molecular bar codes. The combinatorial conditions considered are (i) minimum Hamming distance d, (ii) fixed GC content and, in some cases (iii) minimum distance d between any codeword and the reverse Watson-Crick complement of any codeword. The problem is to find DNA codes with the maximum number of codewords. In this paper the construction of DNA codes is studied from an algorithmic perspective. Four local search algorithms are developed and combined in a variable neighbourhood search framework. The algorithm has been run extensively. Over 254 problems considered, it was able to match or improve the best known lower bounds in 180 cases, with 52 new bests
Heuristic algorithms for constructing binary constant weight codes
No full textConstant weight binary codes are used in a number of applications. Constructions based on mathematical structure are known for many codes. However, heuristic constructions unrelated to any mathematical structure can become of greater importance when the parameters of the code are larger. This paper considers the problem of finding constant weight codes with the maximum number of codewords from a purely algorithmic perspective. A set of heuristic and metaheuristic methods is presented and developed into a variable neighborhood search framework. The proposed method is applied to 383 previously studied cases with lengths between 29 and 63. For these cases it generates 153 new codes, with significantly increased numbers of codewords in comparison with existing constructions. For 10 of these new codes the number of codewords meets a known upper bound, and so these 10 codes are optimal. As well as the ability to generate new best codes, the approach has the advantage that it is a single method capable of addressing many sets of parameters in a uniform way
Some constant weight codes from primitive permutation groups
Get PDFIn recent years the detailed study of the construction of constant weight codes has been extended from length at most 28 to lengths less than 64. Andries Brouwer maintains web pages with tables of the best known constant weight codes of these lengths. In many cases the codes have more codewords than the best code in the literature, and are not particularly easy to improve. Many of the codes are constructed using a specified permutation group as automorphism group. The groups used include cyclic, quasi-cyclic, affine general linear groups etc. sometimes with fixed points. The precise rationale for the choice of groups is not clear.
In this paper the choice of groups is made systematic by the use of the classification of primitive permutation groups. Together with several improved techniques for finding a maximum clique, this has led to the construction of 39 improved constant weight codes
Heuristic manipulation, tabu search and frequency assignment
No full textHeuristic manipulation attempts to modify the search space of an optimization problem, using information provided by an underlying heuristic method. In this paper it is applied in combination with tabu search to the fixed spectrum frequency assignment problem.
The frequency assignment problem involves the assignment of discrete channels (or frequencies) to the transmitters of a radio network, such as a mobile telephone network. Frequency separation is necessary to avoid interference by other transmitters to the signal received from the wanted transmitter at the reception points. Unnecessary separation causes an excess requirement for spectrum. Good assignments minimize interference and the spectrum required. In fixed spectrum frequency assignment the frequency spectrum available is given and the target is to minimize the interference in the network.
Computational experiments confirm that the manipulation technique is able to drive the underlying tabu search algorithm towards improved solutions
A new table of permutation codes
No full textPermutation codes (or permutation arrays) have received considerable interest in recent years, partly motivated by a potential application to powerline communication. Powerline communication is the transmission of data over the electricity distribution system. This environment is rather hostile to communication and the requirements are such that permutation codes may be suitable. The problem addressed in this study is the construction of permutation codes with a specified length and minimum Hamming distance, and with as many codewords (permutations) as possible. A number of techniques are used including construction by automorphism group and several variations of clique search based on vertex degrees. Many significant improvements are obtained to the size of the best known codes
FIGURES 19–20. Fig. 19 in Six new, unusually small ants of the genus Leptomyrmex (Hymenoptera: Formicidae)
No full textFIGURES 19–20. Fig. 19, graph of head length versus head width. Fig. 20, graph of scape length versus head width.Published as part of Smith, Derek J. & Shattuck, Steve, 2009, Six new, unusually small ants of the genus Leptomyrmex (Hymenoptera: Formicidae), pp. 57-68 in Zootaxa 2142 (1) on page 65, DOI: 10.11646/zootaxa.2142.1.5, http://zenodo.org/record/532313
- …
