Model of Overlapping Messages with Degenerate Coding

Valery Kirzhner, Zeev Volkovich

Institute of Evolution, University of Haifa, Haifa, Israel.
Software Engineering Department, ORT Braude College of Engineering, Karmiel, Israel.

DOI: 10.4236/am.2012.32030                

Abstract

Superposition of signals in DNA molecule is a sufficiently general principle of information coding. The necessary re-quirement for such superposition is the degeneracy of the code, which allows placing different messages on the same DNA fragment. Code words that are equivalent in the informational sense (i.e., synonyms) form synonymous group and the entire set of code words is partitioned into synonymous groups. This paper is dedicated to constructing and analyzing the model of synonymous coding. We evaluate some characteristics of synonymous coding as applied to code words of length two although many definitions may be extended for words of arbitrary length.

Keywords

Overlapping Messages; Degenerate Coding; Sequence Compacting; De Bruijn Graph; DNA Triplet Code

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	P. J. Cock and D. E. Whitworth, “Evolution of Gene Overlaps: Relative Reading Frame Bias in Prokaryotic Two-Component System Genes,” Journal of Molecular Evolution, Vol. 64, No. 4, 2007, pp. 475-462. doi:10.1007/s00239-006-0180-1
[2]	Z. I. Johnson and S. W. Chisholm, “Properties of Overlapping Genes are Conserved across Microbial Genomes,” Genome Research, Vol. 14, No. 11, 2004, pp. 2268-2272. doi:10.1101/gr.2433104
[3]	C. Kingsford, A. Delcher and S. L. Salzberg, “A Unified Model Explaining the Offsets of Overlapping and Nearoverlapping Prokaryotic Genes,” Molecular Biology and Evolution, Vol. 24, No. 9, 2007, pp. 2091-2098. doi:10.1093/molbev/msm145
[4]	I. Makalowska, C. F. Lin and W. Makalowski. “Overlapping Genes in Vertebrate Genomes,” Computational Biology and Chemistry, Vol. 29, No. 1, 2005, pp. 1-12. doi:10.1016/j.compbiolchem.2004.12.006
[5]	D. Candotti, C. Chappey, M. Rosenheim, P. M’Pelé, J. M. Huraux and H. Agut, “High Variability of the Gag/Pol Transframe Region among HIV-1 Isolates,” Comptes Rendus de l’Académie des Sciences: Série III, Vol. 317, No. 2, 1994, pp. 183-923.
[6]	K. M. McGirr and G. C. Buehuring, “Tax & Rex: Overlapping Genes of the Deltaretrovirus Group,” Virus Genes, Vol. 32, No. 3, 2006, pp. 229-239. doi:10.1007/s11262-005-6907-z
[7]	H. L. Zaaijer, F. J. van Hemert, M. N. Koppelman and V. V. Lukashov, “Independent Evolution of Overlapping Polymerase and Surface Protein Genes of Hepatitis B Virus,” Journal of General Virology, Vol. 88, 2007, pp. 2137-2143. doi:10.1099/vir.0.82906-0
[8]	M. Gorel and V. M. Kirzhner, “Degenerate Coding and Sequence Compacting,” ESI Preprints 1819, 2006. http://www.esi.ac.at/preprints/ESI-Preprints.html
[9]	M. Lothaire, “Applied Combinatorics on Words,” Encyclopedia of Mathematics and Its Applications, Cambridge University Press, Cambridge, 2005
[10]	M. Hall, “Combinatorial Theory,” John Wiley & Sons, Hoboken, 1976.
[11]	L. R. Ford, Jr. and D. R. Fulkerson, “Flows in Networks,” Princeton University Press, Princeton, 1962.
[12]	I. F. Blake, “A Perspective on Coding Theory,” Information Sciences, Vol. 57-58, 1991, pp. 111-118. doi:10.1016/0020-0255(91)90070-B