Abstract
DNA codes consisting of DNA sequences are necessary for DNA computing. The minimum distance parameter of such codes is a measure of how dissimilar the codewords are, and thus is indirectly a measure of the likelihood of undetectedable or uncorrectable errors occurring during hybridization. To compute distance, an abstract metric, for example, longest common subsequence, must be used to model the actual bonding energies of DNA strands. In this paper we continue the development [1,2,3] of similarity functions for q-ary n-sequences The theoretical lower bound on the maximal possible size of codes, built on the space endowed with this metric, is obtained. that can be used (for q = 4) to model a thermodynamic similarity on DNA sequences. We introduce the concept of a stem similarity function and discuss DNA codes [2] based on the stem similarity. We suggest an optimal construction [2] and obtain random coding bounds on the maximum size and rate for such codes.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
D’yachkov, A.G., Macula, A.J., Pogozelski, W.K., Renz, T.E., Rykov, V.V., Torney D.C.: A Weighted Insertion—Deletion Stacked Pair Thermodynamic Metric for DNA Codes. In: Proc. of 10th Int. Workshop on DNA Computing. Milan, Italy, pp. 90–103 (2004)
D’yachkov, A.G., Macula, A.J., Torney, D.C., Vilenkin, P.A., White, P.S., Ismagilov, I.K., Sarbayev, R.S.: On DNA Codes. Probl. Peredachi Informatsii (in Russian) 41(4), 57–77 (2005). English translation: Problems of Information Transmission 41(4), 349–367 (2005)
D’yachkov, A.G., Erdos, P.L., Macula, A.J., Rykov, V.V., Torney, D.C., Tung, C.S., Vilenkin, P.A., White, P.S.: Exordium for DNA Codes. J. Comb. Optimization 7(4), 369–379 (2003)
Levenshtein, V.I.: Binary Codes Capable of Correcting Deletions, Insertions, and Reversals. Dokl. Akad. Nauk USSR (in Russian) 163, 845–848 (1965), English translation: J. Soviet Phys.–Doklady 10, 707–710 (1966)
Levenshtein, V.I.: Efficient Reconstruction of Sequences from Their Subsequences and Supersequences. J. Comb. Th., Ser. A 93, 310–332 (2001)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
D’yachkov, A., Macula, A., Rykov, V., Ufimtsev, V. (2008). DNA Codes Based on Stem Similarities Between DNA Sequences. In: Garzon, M.H., Yan, H. (eds) DNA Computing. DNA 2007. Lecture Notes in Computer Science, vol 4848. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-77962-9_15
Download citation
DOI: https://doi.org/10.1007/978-3-540-77962-9_15
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-77961-2
Online ISBN: 978-3-540-77962-9
eBook Packages: Computer ScienceComputer Science (R0)