Exordium for DNA codes

被引:24
作者
D'Yachkov, AG [1 ]
Erdös, PL
Macula, AJ
Rykov, VV
Torney, DC
Tung, CS
Vilenkin, PA
White, PS
机构
[1] Moscow MV Lomonosov State Univ, Dept Probabil, Moscow, Russia
[2] Alfred Renyi Inst Math, Budapest, Hungary
[3] SUNY Coll Geneseo, Dept Math, Geneseo, NY 14454 USA
[4] NE Nebraska Univ, Dept Comp Sci, Omaha, NE USA
[5] Los Alamos Natl Lab, Div Theoret, Los Alamos, NM 87545 USA
[6] Los Alamos Natl Lab, Biosci Div, Los Alamos, NM 87545 USA
关键词
binding propensity; DNA computing; DNA hybridization; digital velcro; formulation; directed design;
D O I
10.1023/B:JOCO.0000017385.39168.0d
中图分类号
TP39 [计算机的应用];
学科分类号
081203 ; 0835 ;
摘要
We describe how deletion-correcting codes may be enhanced to yield codes with double-strand DNA-sequence codewords. This enhancement involves abstractions of the pertinent aspects of DNA; it nevertheless ensures specificity of binding for all pairs of single strands derived from its codewords - the key desideratum of DNA codes - i.e. with binding feasible only between reverse complementary strands. We defer discussing the combinatorial-optimization superincumbencies of code construction. Generalization of deletion similarity to an optimal sequence-alignment score could readily effect advantageous improvements (Kaderali, Master's Thesis, Informatics, U. Koln, 2001) but would render the combinatorics opaque. We mention motivating applications of DNA codes.
引用
收藏
页码:369 / 379
页数:11
相关论文
共 24 条
[1]   MOLECULAR COMPUTATION OF SOLUTIONS TO COMBINATORIAL PROBLEMS [J].
ADLEMAN, LM .
SCIENCE, 1994, 266 (5187) :1021-1024
[2]   REPETITIVE DNA-SEQUENCES - SOME CONSIDERATIONS FOR SIMPLE SEQUENCE REPEATS [J].
BELL, GI ;
TORNEY, DC .
COMPUTERS & CHEMISTRY, 1993, 17 (02) :185-190
[3]   PREDICTING DNA DUPLEX STABILITY FROM THE BASE SEQUENCE [J].
BRESLAUER, KJ ;
FRANK, R ;
BLOCKER, H ;
MARKY, LA .
PROCEEDINGS OF THE NATIONAL ACADEMY OF SCIENCES OF THE UNITED STATES OF AMERICA, 1986, 83 (11) :3746-3750
[4]   Flow cytometry-based minisequencing: A new platform for high-throughput single-nucleotide polymorphism scoring [J].
Cai, H ;
White, PS ;
Torney, D ;
Deshpande, A ;
Wang, ZL ;
Marrone, B ;
Nolan, JP .
GENOMICS, 2000, 66 (02) :135-143
[5]  
Colbourn C. J., 1996, The CRC handbook of combinatorial designs
[6]   On similarity codes [J].
D'yachkov, AG ;
Torney, DC .
IEEE TRANSACTIONS ON INFORMATION THEORY, 2000, 46 (04) :1558-1564
[7]  
DYACHKOV AG, UNPUB IEEE T INFORMA
[8]  
ERDOS PL, 2001, ELEC J COMBINATORICS, V8
[9]  
ERDOS PL, UNPUB SUBWORDS REVER
[10]   A RELATION BETWEEN LEVENSHTEIN-TYPE DISTANCES AND INSERTION-AND-DELETION CORRECTING CAPABILITIES OF CODES [J].
HOLLMANN, HDL .
IEEE TRANSACTIONS ON INFORMATION THEORY, 1993, 39 (04) :1424-1427