BACKGROUND
sensitive information, especially secret information must be protected against unauthorized access.
to achieve this researchers have looked for new cryptographic or steganographic techniques.
existing algorithms encrypt or hide information in binary files, however there are other media, which can be used.
there are several algorithms, which encode information into dna sequences.
examples are the concepts of clelland et al., gehani et al., leier et al, wong et al.
and arita et al  <cit> .
these techniques can be used for authentication or to store data for long time.
clelland et al
inspired by the micro-dots used during the 2nd world war, clelland et al.
developed an extension of this principle  <cit> .
the scientists produced artificial dna strands, which contained secret messages.
a triplet encodes one character or number .
the clelland algorithm is a simple substitution cipher which encodes characters into dna sequences using the following encoding function
• e : x → y
• x ∈ {a, b, c,..., z,  <dig>   <dig> ...,  <dig>  ".
",","," : ","⊔"}
• y ∈ {xyz : x, y, z ∈ {a, c, g, t}}
the decoding function is corresponding d : y → x.
now clelland et al.
ligated two primers with the synthesized dna sequences, a forward and a reverse primer.
these ligated sequences were mixed up with dummy strands.
important preconditions are:
• length of dummy strand = length of message dna with primers
• #copies of each dummy = #copies of message dna
the receiver must know the decoding function and the primer to decode the message.
the primers are used for the polymerase chain reaction and in the last step the amplified dna sequence has to be sequenced and decoded.
to improve the security one can use dummy strands, which are not random but correspond to words out of a dictionary.
gehani et al
the original one-time pad uses the xor – exclusive or .
in the case of dna, the xor is very impracticable and therefore it is better to use the properties of dna.
gehani et al.
established a dna one-time pad by creating word pairs  <cit> .
the first word is the plain text and the second one is the cipher text.
after such a block of plain and cipher text, there is a stop codon .
the dna polymerase completes the plain and cipher text.
to encode a message, the plain text is mixed with the dna sequences.
it binds directly to the corresponding complementary sequence.
the dna polymerase creates the cipher text accordingly and the decoding is functionally analogous.
the cipher text binds to its complement and the dna polymerase creates the plain text.
leier et al
leier et al.
encoded binary information into dna sequences.
a short dna sequence represents the binary  <dig>  another one represents  <dig>  <cit> .
further there are another two short dna sequences, which represent start and end.
the fragments have sticky ends and can be ligated .
all resulting sequences are like this s{02|12}e. the start and end marker have primer sequences on one site for the polymerase chain reaction, which can not be ligated.
although it seems to be more complicated, it is very similar to the algorithm of clelland et al.
the resulting dna sequence is mixed with dummy strands and can only be detected and isolated knowing the primer sequences.
wong et al
wong et al.
developed a steganographic algorithm based on dna, which is able to store data in living organisms  <cit> .
the data are translated into a dna sequence which is inserted into a vector.
the insert sequence is flanked by two primer sequences which do not exist in the genome yet.
this vector is introduced into a cell of a living organism where it coexists and is replicated with the genomic dna.
to extract the data they used a polymerase chain reaction.
wong et al.
used a substitution cipher similar to clelland et al.
to encode a song text into a dna sequence and stored it in deinococcus radiodurans.
deinococcus radiodurans survive extreme conditions, e.g.
ionizing radiation, so the song text can be stored for hundreds of years.
arita et al
arita et al.
developed a steganographic algorithm based on the degenerative genetic code.
amino acid codes are redundant so that the translation of mrna into proteins is a substitution cipher with the following characteristics
• e : x → y
• x ∈ {xyz : x, y, z ∈ {a, c, g, u}}
• y ∈ {a, c, d, e, f, g, h, i, k, l, m, n, p, q, r, s, t, v, w, y, stop}
but the inverse function d : y → x is not injective.
an example:
threonine = e = e = e = e
the triplet of threonine is redundant in the third base so mutations in the third base do not exert any influence on the translation of threonine and the translated protein.
these mutations are called "synonymous substitutions", in contrast to the "non-synonymous substitutions".
arita et al.
translated each letter of the english alphabet into six codons .
a value of  <dig> means to keep the original base at the third position of a codon, while a value of  <dig> means to change the third base at that position.
arita et al.
added a parity bit to each letter, to keep it odd for possible error detection  <cit> .
they encoded 'keio' into the ftsz gene of bacillus subtilis which is essential for cell division and demonstrated as expected that the changed codon sequences did not affect the cell division, colony morphology, growth rate and sporulation frequency of these bacteria.
to extract the encoded message one has to know the original sequence so that one can decide whether the codon is the original or the altered sequence.
comparison to dna-crypt
clelland et al., gehani et al.
and leier et al.
produced synthesized dna sequences which were mixed with dummy strands.
these sequences contained a secret message.
knowing the unique primer sequence, the secret message can be read out.
wong et al.
and arita et al.
introduced dna sequences containing a secret message into living organisms.
wong et al.
used a vector which incorporated into the genome of deinococcus radiodurans and arita et al.
used point mutations in redundant codons.
arita et al.
used a parity bit for error detection.
the disadvantage is that if mutations occur, the hidden information is lost.
the dna-crypt algorithm is based on small redundant regions comparable to least significant bits in the case of image steganography .
the least significant bits encode a difference in colour of just one on the colour scale, not visible to the human eye, and can be used to hide information in images.
text or binary information can also be encoded using any dna based encryption.
however unlike image steganography, the dna steganography does not lead to a loss of information if the focused range is a protein coding region.
dna-crypt checks for "synonymous codons" in a genome and point mutations are produced by changing the bases .
this algorithm offers the possibility to incorporate data into the genome of living organisms, using an alternative method to wong et al.
<cit>  .
the algorithm is similar to the algorithm of arita et al., but dna-crypt has some important extensions e.g.
the use of several encryption and mutation correction codes, which allows encoding of binary information.
these extensions are described in the next subsections  <cit> .
a comparative overview of the algorithms and their features is shown in table  <dig>
organism: the use of this algorithm in living organisms;
affect: observation that the algorithm exerts an effect on the organims;
error detection/correction: the algorithm shows an error detection/correction function;
binary: binary information can be encoded;
encryption: the use of binary encryption algorithm like aes or rsa;
utilization: storage utilization in a  <dig> bp dna sequence;
- = negative;
+ = positive;
encoding binary information using dna-crypt
dna-crypt encodes binary information using the following substitution cipher:
• e : x → y
• x = {xy : x, y ∈ { <dig>  12}}
• y ∈ {a, c, g, t}
a standard setting is given in table  <dig>
the binary sequence  <dig> would be encoded to e = gatcgtaa.
two bits could be encoded by one base, so one byte needs four bases for its encoding.
based on this binary encryption, several private and public key cryptographic algorithms are integrated in dna-crypt:
• one-time pad  <cit>
• aes  <cit>
• blowfish  <cit>
• rsa  <cit>
to use dna-crypt one has to register so that dna-crypt can create aes, blowfish and rsa keys for the user.
these keys can be used to encrypt the binary information which then gets integrated into the genome.
in addition it is possible to export and to import these keys and to exchange them with other users.
further the user can create new keys in dna-crypt or delete old ones.
another possibility is to use a one-time pad instead of an encryption key.
compared to arita et al.
our substitution cipher allows to use several encryption algorithms as decribed above.
in addition dna-crypt offers a better storage utilization compared to the algorithm of arita et al.
.
mutation correction
mutations do not occur very often, approximately 10- <dig> to 10- <dig> per cell division, but they can destroy the encrypted information in dna sequences.
to correct these failures dna-crypt uses a correction code based on binary correction.
one of them is the 8/ <dig> hamming-code and another one is the wdh-code  <cit> .
the advantage of the wdh-code is that it can correct more mutations than the 8/ <dig> hamming-code.
the n-times wdh-code repeats the enrypted dna sequence n times.
it can correct ⌊n−12⌋
mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbaebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqaciaacagaaeqabaqabegadaaakeaadagbdaqaamaalaaabagaemoba4maeyoei0iaegymaedabagaegomaidaaagaayj84laawup+aaaa@3608@ failures.
all wdh-codes where n is an odd number are perfect.
the 8/ <dig> hamming-code can only correct ≤ 25% of the mutations.
four bits are used for information  and the other four bits as parity bits.
a complete byte is represented by these eight bits b <dig> b <dig> ⊕ b <dig> ⊕ b <dig> b <dig>  ¬b <dig> ⊕ b <dig> ⊕ b <dig> b <dig>  ¬b <dig> ⊕ b <dig> ⊕ b <dig> b <dig>  ¬b <dig> ⊕ b <dig> ⊕ b0
which are called h <dig>  h <dig>  h <dig>  h <dig>  h <dig>  h <dig>  h <dig>  h <dig>  to decode the byte, the following parity sums are build:
• p = h <dig> ⊕ h <dig> ⊕ h <dig> ⊕ h <dig> ⊕ h <dig> ⊕ h <dig> ⊕ h <dig> ⊕ h0
c <dig> = h <dig> ⊕ h <dig> ⊕ h <dig> ⊕ h0
c <dig> = h <dig> ⊕ h <dig> ⊕ h <dig> ⊕ h1
c <dig> = h <dig> ⊕ h <dig> ⊕ h <dig> ⊕ h1
if p =  <dig> there are  <dig> or  <dig> failures in the byte.
the byte was transmitted correct, if the parity bits c <dig>  c <dig>  c <dig> are correct, which means equal to  <dig>  if not, there happened  <dig> failures, which cannot be corrected.
if p =  <dig> there is  <dig> failure in the byte which can be corrected using table  <dig>
only one of four bits can be corrected.
but not all mutations can be corrected by the 8/ <dig> hamming-code.
failures which only differ in one bit can be corrected, e.g.
<dig> ↔  <dig> or  <dig> ↔  <dig>  failures like  <dig> ↔  <dig> or  <dig> ↔  <dig> cannot be corrected.
the limiting resource for mutation correction is not the time, but the space.
the advantage of the 8/ <dig> hamming-code is that it is very compact.
the space requirements of the 8/ <dig> hamming-code is f = 2n ∈ Θ. in contrast to f={n <dig>  n is an odd numbern2+n, else}∈Θ
mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbaebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqaciaacagaaeqabaqabegadaaakeaacqwgmbgzcqggoaakcqwgubgbcqggpaqkcqgh9aqpdagadeqaauaabeqaceaaaeaacqwgubgbdaahaawcbeqaaiabikdayaaakiabcycasiabbccagiabd6gaujabbccagiabdmgapjabdohazjabbccagiabdggahjabd6gaujabbccagiabd+gavjabdsgakjabdsgakjabbccagiabd6gaujabdwha1jabd2gatjabdkgaijabdwgaljabdkhaybqaaiabd6gaunaacaaaleqabagaegomaidaaogaey4kasiaemoba4maeiilawiaeeiiaaiaemyzaumaemibawmaem4camnaemyzaugaaagaay5eaiaaw2haaiabgigiolabfi5arjabcicaoiabd6gaunaacaaaleqabagaegomaidaaogaeiykakcaaa@620b@ for the wdh-code.
for example to encode one byte, which means a dna sequence of four bases, the 8/ <dig> hamming-code needs eight synonymous codons instead of twenty synonymous codons for the 5-times wdh-code.
in contrast to the data published by arita et al.
we can not only exibit error detection but error corrections which enables us to maintain the data.
this obviously represents an important advantage.
fuzzy controller
the integrated fuzzy controller decides and recommends whether to use the 8/ <dig> hamming-code, the wdh-code or no mutation correction for optimal performance  <cit>  .
it uses the singleton-fuzzyfication and has three input dimensions with each separated into three triangular sets.
the first dimension is the individual mutation rate  of the dna sequence containing the secret message .
this is based on a standard mutation rate, by default  <dig> * 10- <dig> for prokaryotes and  <dig> * 10- <dig> for eukaryotes, which is changed by specific mutation rates  for each base pair.
these changes are based on the transversion and transition rate and in addition on the stability  of gc rich regions.
• φ=∑i=03αi/4
mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbaebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqaciaacagaaeqabaqabegadaaakeaaiigacqwfgpgzcqgh9aqpdaaewaqaaiab=f7ahnaabaaaleaacqwgpbqaaeqaaogaei4la8iaeginaqdaleaacqwgpbqacqgh9aqpcqaiwaamaeaacqaizawma0gaeyyeiuoaaaa@3abe@
• α0=#c∗/δ
mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbaebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqaciaacagaaeqabaqabegadaaakeaaiigacqwfxoqydawgaawcbagaegimaadabeaakiabg2da9iabcocajiabdoeadjabgehiqiabcicaomaaqadabagae8xsde2aasbaasqaaiabdoeadjabdmgapbqabagccqggvawlcqaizawmcqggpaqkcqggvawlcqwf0oazasqaaiabdmgapjabg2da9iabdgeabjabcycasiabdeeahjabcycasiabdsfaubqaaiabiodazaqdcqghris5aaaa@47fe@
• α1=#g∗/δ
mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbaebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqaciaacagaaeqabaqabegadaaakeaaiigacqwfxoqydawgaawcbagaegymaedabeaakiabg2da9iabcocajiabdeeahjabgehiqiabcicaomaaqadabagae8xsde2aasbaasqaaiabdeeahjabdmgapbqabagccqggvawlcqaizawmcqggpaqkcqggvawlcqwf0oazasqaaiabdmgapjabg2da9iabdgeabjabcycasiabdoeadjabcycasiabdsfaubqaaiabiodazaqdcqghris5aaaa@4808@
• α2=#a∗∑i=c,g,t3αai/3
mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbaebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqaciaacagaaeqabaqabegadaaakeaaiigacqwfxoqydawgaawcbagaegomaidabeaakiabg2da9iabcocajiabdgeabjabgehiqmaaqadabagae8xsde2aasbaasqaaiabdgeabjabdmgapbqabagccqggvawlcqaizawmasqaaiabdmgapjabg2da9iabdoeadjabcycasiabdeeahjabcycasiabdsfaubqaaiabiodazaqdcqghris5aaaa@43c6@
• α3=#t∗∑i=a,c,g3αti/3
mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbaebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqaciaacagaaeqabaqabegadaaakeaaiigacqwfxoqydawgaawcbagaeg4mamdabeaakiabg2da9iabcocajiabdsfaujabgehiqmaaqadabagae8xsde2aasbaasqaaiabdsfaujabdmgapbqabagccqggvawlcqaizawmasqaaiabdmgapjabg2da9iabdgeabjabcycasiabdoeadjabcycasiabdeeahbqaaiabiodazaqdcqghris5aaaa@43ee@
the first input dimension is separated into three triangular sets xi =   <cit> .
the first called "low" =  describes a low mutation rate.
the second "middle" =  and the third "high" =  describes a middle and a high mutation rate.
the second input dimension is the length of the dna sequence containing the secret message .
the triangular sets are "short" = , "middle" =  and "long" = .
the third input dimension is the stability over time, which is represented by the number of generations .
it is separated into "low" = , "middle" =  and "high" = .
the three input dimensions are linked through a set of rules based on heuristics to one output dimension .
the maximum of each correction code means a cut on the y axis .
in the next step the fuzzy controller decides, whether to use an 8/ <dig> hamming-code, a wdh-code or no mutation correction by using the first-maximum method and recommends it to the user.
RESULTS
the program described above was tested by in silico experiments using the dna sequence encoding the ypt <dig> in saccharomyces cerevisiae.
ypt7
the small gtpases termed ypt in yeast and rab in higher eukaryotes are molecular switches in cellular transport processes  <cit> .
each ypt protein is localized to the membrane of specific intracellular compartments and highly specific for a particular transport step  <cit> .
the ypt <dig> gtpase from s. cerevisiae is involved in late endosome-to-vacuole transport and vacuole fusion events  <cit> .
ypt <dig> is one of the  <dig> members of the s. cerevisiae ypt family and is homologous to mammalian rab <dig>
analysis of the ypt <dig> dna sequence showed that 32% of the codons allow synonymous substitutions, resulting in  <dig> bytes, which could be encrypted .
the first steganogram contains the message "this is a test" and the second one "yet another test" .
the results of the analyses of these steganograms with the fuzzy controller are shown in table  <dig>  translation with dna-crypt and the expasy translate tool shows that the translated amino acid sequences are identical  <cit> .
the pairwise and the multiple sequence alignments show a few mismatches between the three sequences .
the pairwise sequence alignment was performed with dotlet and the multiple sequence alignment was performed using clustalw of the european bioinformatics institute with standard settings  <cit> .
discussion
dna-crypt produces few sequence mismatches similar to the low noise in image steganography.
in case of image steganography one can look at the least significant bits to attack the steganographic algorithms.
to attack dna steganography one can perform pairwise or multiple sequence alignments with the original sequences.
CONCLUSIONS
the dna-crypt algorithm can encode cryptic messages into dna sequences, which can be used as watermarks for authentication.
dna-crypt is a substantial extension to other steganographic algorithms based on dna, which can be used in combination with a binary encryption algorithm such as aes, rsa or blowfish and a mutation correction code such as the hamming-code or the wdh-code.
the most appropriate code of these correction codes can be selected by a fuzzy controller, which uses three input dimensions.
mutations, which cause changes in the reading frame, are problematic and are not appropriate for dna steganography.
mutations, which change a non-synonymous codon to a synonymous codon or vice versa are more important as these mutations cause errors in the encrypted information.
the relevance of these errors depends on the encrypted information.
if the encrypted information is an image, e.g.
a logo, there would be only a linear colour shift in the image, which is not very relevant and can be corrected very easily.
however if the encrypted information must remain correct, e.g.
a password, the wdh-code must be used to detect these mutations.
we have not encoutered any problems so far performing our in silico analyses using dna-crypt watermarks in dna coding regions.
the use of dna-crypt in non-coding sequences like a regulatory rna sequence or promoter, and enhancer sequences has to be tested in silico and in vivo.
further analyses to clarify, whether alternative splicing events pose a problem for watermarks still have to be carried out.
in conclusion dna-crypt algorithm represents an interesting tool for hiding authenticating watermarks within coding dna sequences in silico and most probably in living organisms without affecting the process of protein translation and protein function.
availability and requirements
project name: dna-crypt
project homepage:
operating systems: cross-platform
programming language: java  <dig>  or higher
authors' contributions
dh: conception, software development, sequence alignments, figure preparation, manuscript preparation
ab: conception, design, manuscript preparation, coordination, research funds collection.
the authors read and approved the final manuscript.
supplementary material
additional file 1
the dna-crypt v. <dig>
click here for file
additional file 2
the fuzzy controller.
click here for file
additional file 3
the set of rules for the fuzzy-controller.
click here for file
additional file 4
the dna sequences of the ypt <dig> and the two steganograms.
click here for file
acknowledgements
the authors thank prof. dr. achim clausing and dr. mark kail for critical reading the manuscript.
this work is part of the phd thesis of dh.

 sensitive information, especially secret information must be protected against unauthorized access. to achieve this researchers have looked for new cryptographic or steganographic techniques. existing algorithms encrypt or hide information in binary files, however there are other media, which can be used. there are several algorithms, which encode information into dna sequences. examples are the concepts of clelland et al., gehani et al., leier et al, wong et al. and arita et al. these techniques can be used for authentication or to store data for long time. clelland et al inspired by the micro-dots used during the 2nd world war, clelland et al. developed an extension of this principle. the scientists produced artificial dna strands, which contained secret messages. a triplet encodes one character or number. the clelland algorithm is a simple substitution cipher which encodes characters into dna sequences using the following encoding function • e: x → y • x ∈ {a, b, c,..., z,..., ".",",",": ","⊔"} • y ∈ {xyz: x, y, z ∈ {a, c, g, t}} the decoding function is corresponding d: y → x. now clelland et al. ligated two primers with the synthesized dna sequences, a forward and a reverse primer. these ligated sequences were mixed up with dummy strands. important preconditions are: • length of dummy strand = length of message dna with primers • #copies of each dummy = #copies of message dna the receiver must know the decoding function and the primer to decode the message. the primers are used for the polymerase chain reaction and in the last step the amplified dna sequence has to be sequenced and decoded. to improve the security one can use dummy strands, which are not random but correspond to words out of a dictionary. gehani et al the original one-time pad uses the xor – exclusive or. in the case of dna, the xor is very impracticable and therefore it is better to use the properties of dna. gehani et al. established a dna one-time pad by creating word pairs. the first word is the plain text and the second one is the cipher text. after such a block of plain and cipher text, there is a stop codon. the dna polymerase completes the plain and cipher text. to encode a message, the plain text is mixed with the dna sequences. it binds directly to the corresponding complementary sequence. the dna polymerase creates the cipher text accordingly and the decoding is functionally analogous. the cipher text binds to its complement and the dna polymerase creates the plain text. leier et al leier et al. encoded binary information into dna sequences. a short dna sequence represents the binary another one represents. further there are another two short dna sequences, which represent start and end. the fragments have sticky ends and can be ligated. all resulting sequences are like this s{02|12}e. the start and end marker have primer sequences on one site for the polymerase chain reaction, which can not be ligated. although it seems to be more complicated, it is very similar to the algorithm of clelland et al. the resulting dna sequence is mixed with dummy strands and can only be detected and isolated knowing the primer sequences. wong et al wong et al. developed a steganographic algorithm based on dna, which is able to store data in living organisms. the data are translated into a dna sequence which is inserted into a vector. the insert sequence is flanked by two primer sequences which do not exist in the genome yet. this vector is introduced into a cell of a living organism where it coexists and is replicated with the genomic dna. to extract the data they used a polymerase chain reaction. wong et al. used a substitution cipher similar to clelland et al. to encode a song text into a dna sequence and stored it in deinococcus radiodurans. deinococcus radiodurans survive extreme conditions, e.g. ionizing radiation, so the song text can be stored for hundreds of years. arita et al arita et al. developed a steganographic algorithm based on the degenerative genetic code. amino acid codes are redundant so that the translation of mrna into proteins is a substitution cipher with the following characteristics • e: x → y • x ∈ {xyz: x, y, z ∈ {a, c, g, u}} • y ∈ {a, c, d, e, f, g, h, i, k, l, m, n, p, q, r, s, t, v, w, y, stop} but the inverse function d: y → x is not injective. an example: threonine = e = e = e = e the triplet of threonine is redundant in the third base so mutations in the third base do not exert any influence on the translation of threonine and the translated protein. these mutations are called "synonymous substitutions", in contrast to the "non-synonymous substitutions". arita et al. translated each letter of the english alphabet into six codons. a value of means to keep the original base at the third position of a codon, while a value of means to change the third base at that position. arita et al. added a parity bit to each letter, to keep it odd for possible error detection. they encoded'keio' into the ftsz gene of bacillus subtilis which is essential for cell division and demonstrated as expected that the changed codon sequences did not affect the cell division, colony morphology, growth rate and sporulation frequency of these bacteria. to extract the encoded message one has to know the original sequence so that one can decide whether the codon is the original or the altered sequence. comparison to dna-crypt clelland et al., gehani et al. and leier et al. produced synthesized dna sequences which were mixed with dummy strands. these sequences contained a secret message. knowing the unique primer sequence, the secret message can be read out. wong et al. and arita et al. introduced dna sequences containing a secret message into living organisms. wong et al. used a vector which incorporated into the genome of deinococcus radiodurans and arita et al. used point mutations in redundant codons. arita et al. used a parity bit for error detection. the disadvantage is that if mutations occur, the hidden information is lost. the dna-crypt algorithm is based on small redundant regions comparable to least significant bits in the case of image steganography. the least significant bits encode a difference in colour of just one on the colour scale, not visible to the human eye, and can be used to hide information in images. text or binary information can also be encoded using any dna based encryption. however unlike image steganography, the dna steganography does not lead to a loss of information if the focused range is a protein coding region. dna-crypt checks for "synonymous codons" in a genome and point mutations are produced by changing the bases. this algorithm offers the possibility to incorporate data into the genome of living organisms, using an alternative method to wong et al.. the algorithm is similar to the algorithm of arita et al., but dna-crypt has some important extensions e.g. the use of several encryption and mutation correction codes, which allows encoding of binary information. these extensions are described in the next subsections. a comparative overview of the algorithms and their features is shown in table organism: the use of this algorithm in living organisms; affect: observation that the algorithm exerts an effect on the organims; error detection/correction: the algorithm shows an error detection/correction function; binary: binary information can be encoded; encryption: the use of binary encryption algorithm like aes or rsa; utilization: storage utilization in a bp dna sequence; - = negative; + = positive; encoding binary information using dna-crypt dna-crypt encodes binary information using the following substitution cipher: • e: x → y • x = {xy: x, y ∈ { 12}} • y ∈ {a, c, g, t} a standard setting is given in table the binary sequence would be encoded to e = gatcgtaa. two bits could be encoded by one base, so one byte needs four bases for its encoding. based on this binary encryption, several private and public key cryptographic algorithms are integrated in dna-crypt: • one-time pad • aes • blowfish • rsa to use dna-crypt one has to register so that dna-crypt can create aes, blowfish and rsa keys for the user. these keys can be used to encrypt the binary information which then gets integrated into the genome. in addition it is possible to export and to import these keys and to exchange them with other users. further the user can create new keys in dna-crypt or delete old ones. another possibility is to use a one-time pad instead of an encryption key. compared to arita et al. our substitution cipher allows to use several encryption algorithms as decribed above. in addition dna-crypt offers a better storage utilization compared to the algorithm of arita et al.. mutation correction mutations do not occur very often, approximately 10- to 10- per cell division, but they can destroy the encrypted information in dna sequences. to correct these failures dna-crypt uses a correction code based on binary correction. one of them is the 8/ hamming-code and another one is the wdh-code. the advantage of the wdh-code is that it can correct more mutations than the 8/ hamming-code. the n-times wdh-code repeats the enrypted dna sequence n times. it can correct ⌊n−12⌋ mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbaebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqaciaacagaaeqabaqabegadaaakeaadagbdaqaamaalaaabagaemoba4maeyoei0iaegymaedabagaegomaidaaagaayj84laawup+aaaa@3608@ failures. all wdh-codes where n is an odd number are perfect. the 8/ hamming-code can only correct ≤ 25% of the mutations. four bits are used for information and the other four bits as parity bits. a complete byte is represented by these eight bits b b ⊕ b ⊕ b b ¬b ⊕ b ⊕ b b ¬b ⊕ b ⊕ b b ¬b ⊕ b ⊕ b0 which are called h h h h h h h h to decode the byte, the following parity sums are build: • p = h ⊕ h ⊕ h ⊕ h ⊕ h ⊕ h ⊕ h ⊕ h0 c = h ⊕ h ⊕ h ⊕ h0 c = h ⊕ h ⊕ h ⊕ h1 c = h ⊕ h ⊕ h ⊕ h1 if p = there are or failures in the byte. the byte was transmitted correct, if the parity bits c c c are correct, which means equal to if not, there happened failures, which cannot be corrected. if p = there is failure in the byte which can be corrected using table only one of four bits can be corrected. but not all mutations can be corrected by the 8/ hamming-code. failures which only differ in one bit can be corrected, e.g. ↔ or ↔ failures like ↔ or ↔ cannot be corrected. the limiting resource for mutation correction is not the time, but the space. the advantage of the 8/ hamming-code is that it is very compact. the space requirements of the 8/ hamming-code is f = 2n ∈ Θ. in contrast to f={n  n is an odd numbern2+n, else}∈Θ mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbaebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqaciaacagaaeqabaqabegadaaakeaacqwgmbgzcqggoaakcqwgubgbcqggpaqkcqgh9aqpdagadeqaauaabeqaceaaaeaacqwgubgbdaahaawcbeqaaiabikdayaaakiabcycasiabbccagiabd6gaujabbccagiabdmgapjabdohazjabbccagiabdggahjabd6gaujabbccagiabd+gavjabdsgakjabdsgakjabbccagiabd6gaujabdwha1jabd2gatjabdkgaijabdwgaljabdkhaybqaaiabd6gaunaacaaaleqabagaegomaidaaogaey4kasiaemoba4maeiilawiaeeiiaaiaemyzaumaemibawmaem4camnaemyzaugaaagaay5eaiaaw2haaiabgigiolabfi5arjabcicaoiabd6gaunaacaaaleqabagaegomaidaaogaeiykakcaaa@620b@ for the wdh-code. for example to encode one byte, which means a dna sequence of four bases, the 8/ hamming-code needs eight synonymous codons instead of twenty synonymous codons for the 5-times wdh-code. in contrast to the data published by arita et al. we can not only exibit error detection but error corrections which enables us to maintain the data. this obviously represents an important advantage. fuzzy controller the integrated fuzzy controller decides and recommends whether to use the 8/ hamming-code, the wdh-code or no mutation correction for optimal performance. it uses the singleton-fuzzyfication and has three input dimensions with each separated into three triangular sets. the first dimension is the individual mutation rate of the dna sequence containing the secret message. this is based on a standard mutation rate, by default * 10- for prokaryotes and * 10- for eukaryotes, which is changed by specific mutation rates for each base pair. these changes are based on the transversion and transition rate and in addition on the stability of gc rich regions. • φ=∑i=03αi/4 mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbaebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqaciaacagaaeqabaqabegadaaakeaaiigacqwfgpgzcqgh9aqpdaaewaqaaiab=f7ahnaabaaaleaacqwgpbqaaeqaaogaei4la8iaeginaqdaleaacqwgpbqacqgh9aqpcqaiwaamaeaacqaizawma0gaeyyeiuoaaaa@3abe@ • α0=#c∗/δ mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbaebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqaciaacagaaeqabaqabegadaaakeaaiigacqwfxoqydawgaawcbagaegimaadabeaakiabg2da9iabcocajiabdoeadjabgehiqiabcicaomaaqadabagae8xsde2aasbaasqaaiabdoeadjabdmgapbqabagccqggvawlcqaizawmcqggpaqkcqggvawlcqwf0oazasqaaiabdmgapjabg2da9iabdgeabjabcycasiabdeeahjabcycasiabdsfaubqaaiabiodazaqdcqghris5aaaa@47fe@ • α1=#g∗/δ mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbaebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqaciaacagaaeqabaqabegadaaakeaaiigacqwfxoqydawgaawcbagaegymaedabeaakiabg2da9iabcocajiabdeeahjabgehiqiabcicaomaaqadabagae8xsde2aasbaasqaaiabdeeahjabdmgapbqabagccqggvawlcqaizawmcqggpaqkcqggvawlcqwf0oazasqaaiabdmgapjabg2da9iabdgeabjabcycasiabdoeadjabcycasiabdsfaubqaaiabiodazaqdcqghris5aaaa@4808@ • α2=#a∗∑i=c,g,t3αai/3 mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbaebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqaciaacagaaeqabaqabegadaaakeaaiigacqwfxoqydawgaawcbagaegomaidabeaakiabg2da9iabcocajiabdgeabjabgehiqmaaqadabagae8xsde2aasbaasqaaiabdgeabjabdmgapbqabagccqggvawlcqaizawmasqaaiabdmgapjabg2da9iabdoeadjabcycasiabdeeahjabcycasiabdsfaubqaaiabiodazaqdcqghris5aaaa@43c6@ • α3=#t∗∑i=a,c,g3αti/3 mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbaebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqaciaacagaaeqabaqabegadaaakeaaiigacqwfxoqydawgaawcbagaeg4mamdabeaakiabg2da9iabcocajiabdsfaujabgehiqmaaqadabagae8xsde2aasbaasqaaiabdsfaujabdmgapbqabagccqggvawlcqaizawmasqaaiabdmgapjabg2da9iabdgeabjabcycasiabdoeadjabcycasiabdeeahbqaaiabiodazaqdcqghris5aaaa@43ee@ the first input dimension is separated into three triangular sets xi =. the first called "low" = describes a low mutation rate. the second "middle" = and the third "high" = describes a middle and a high mutation rate. the second input dimension is the length of the dna sequence containing the secret message. the triangular sets are "short" =, "middle" = and "long" =. the third input dimension is the stability over time, which is represented by the number of generations. it is separated into "low" =, "middle" = and "high" =. the three input dimensions are linked through a set of rules based on heuristics to one output dimension. the maximum of each correction code means a cut on the y axis. in the next step the fuzzy controller decides, whether to use an 8/ hamming-code, a wdh-code or no mutation correction by using the first-maximum method and recommends it to the user.  the program described above was tested by in silico experiments using the dna sequence encoding the ypt in saccharomyces cerevisiae. ypt7 the small gtpases termed ypt in yeast and rab in higher eukaryotes are molecular switches in cellular transport processes. each ypt protein is localized to the membrane of specific intracellular compartments and highly specific for a particular transport step. the ypt gtpase from s. cerevisiae is involved in late endosome-to-vacuole transport and vacuole fusion events. ypt is one of the members of the s. cerevisiae ypt family and is homologous to mammalian rab analysis of the ypt dna sequence showed that 32% of the codons allow synonymous substitutions, resulting in bytes, which could be encrypted. the first steganogram contains the message "this is a test" and the second one "yet another test". the results of the analyses of these steganograms with the fuzzy controller are shown in table translation with dna-crypt and the expasy translate tool shows that the translated amino acid sequences are identical. the pairwise and the multiple sequence alignments show a few mismatches between the three sequences. the pairwise sequence alignment was performed with dotlet and the multiple sequence alignment was performed using clustalw of the european bioinformatics institute with standard settings. discussion dna-crypt produces few sequence mismatches similar to the low noise in image steganography. in case of image steganography one can look at the least significant bits to attack the steganographic algorithms. to attack dna steganography one can perform pairwise or multiple sequence alignments with the original sequences.  the dna-crypt algorithm can encode cryptic messages into dna sequences, which can be used as watermarks for authentication. dna-crypt is a substantial extension to other steganographic algorithms based on dna, which can be used in combination with a binary encryption algorithm such as aes, rsa or blowfish and a mutation correction code such as the hamming-code or the wdh-code. the most appropriate code of these correction codes can be selected by a fuzzy controller, which uses three input dimensions. mutations, which cause changes in the reading frame, are problematic and are not appropriate for dna steganography. mutations, which change a non-synonymous codon to a synonymous codon or vice versa are more important as these mutations cause errors in the encrypted information. the relevance of these errors depends on the encrypted information. if the encrypted information is an image, e.g. a logo, there would be only a linear colour shift in the image, which is not very relevant and can be corrected very easily. however if the encrypted information must remain correct, e.g. a password, the wdh-code must be used to detect these mutations. we have not encoutered any problems so far performing our in silico analyses using dna-crypt watermarks in dna coding regions. the use of dna-crypt in non-coding sequences like a regulatory rna sequence or promoter, and enhancer sequences has to be tested in silico and in vivo. further analyses to clarify, whether alternative splicing events pose a problem for watermarks still have to be carried out. in conclusion dna-crypt algorithm represents an interesting tool for hiding authenticating watermarks within coding dna sequences in silico and most probably in living organisms without affecting the process of protein translation and protein function. availability and requirements project name: dna-crypt project homepage: operating systems: cross-platform programming language: java or higher authors' contributions dh: conception, software development, sequence alignments, figure preparation, manuscript preparation ab: conception, design, manuscript preparation, coordination, research funds collection. the authors read and approved the final manuscript. supplementary material additional file 1 the dna-crypt v. click here for file additional file 2 the fuzzy controller. click here for file additional file 3 the set of rules for the fuzzy-controller. click here for file additional file 4 the dna sequences of the ypt and the two steganograms. click here for file acknowledgements the authors thank prof. dr. achim clausing and dr. mark kail for critical reading the manuscript. this work is part of the phd thesis of dh.
mutations which can occur infrequently may destroy the encrypted information, however an integrated fuzzy controller decides on a set of heuristics based on three input dimensions, and recommends whether or not to use a correction code. these three input dimensions are the length of the sequence, the individual mutation rate and the stability over time, which is represented by the number of generations. the dna-crypt algorithm and image steganography are based on the same watermark-hiding principle, namely using the least significant base in case of dna-crypt and the least significant bit in case of the image steganography. the aim of this paper is to demonstrate the application of watermarks based on dna sequences to identify the unauthorized use of genetically modified organisms protected by patents. existing dna cryptographic and steganographic algorithms use synthetic dna sequences to store binary information however, although these sequences can be used for authentication, they may change the target dna sequence when introduced into living organisms. pairwise or multiple sequence alignments show that dna-crypt produces few mismatches between the sequences similar to all steganographic algorithms. dna-crypt is able to correct mutations in the target dna with several mutation correction codes such as the hamming-code or the wdh-code. in silico experiments using the ypt in saccharomyces cerevisiae shows that the dna watermarks produced by dna-crypt do not alter the translation of mrna into protein.
 the aim of this paper is to demonstrate the application of watermarks based on dna sequences to identify the unauthorized use of genetically modified organisms protected by patents. predicted mutations in the genome can be corrected by the dna-crypt program leaving the encrypted information intact. existing dna cryptographic and steganographic algorithms use synthetic dna sequences to store binary information however, although these sequences can be used for authentication, they may change the target dna sequence when introduced into living organisms.  the dna-crypt algorithm and image steganography are based on the same watermark-hiding principle, namely using the least significant base in case of dna-crypt and the least significant bit in case of the image steganography. it can be combined with binary encryption algorithms like aes, rsa or blowfish. dna-crypt is able to correct mutations in the target dna with several mutation correction codes such as the hamming-code or the wdh-code. mutations which can occur infrequently may destroy the encrypted information, however an integrated fuzzy controller decides on a set of heuristics based on three input dimensions, and recommends whether or not to use a correction code. these three input dimensions are the length of the sequence, the individual mutation rate and the stability over time, which is represented by the number of generations. in silico experiments using the ypt in saccharomyces cerevisiae shows that the dna watermarks produced by dna-crypt do not alter the translation of mrna into protein.  the program is able to store watermarks in living organisms and can maintain the original information by correcting mutations itself. pairwise or multiple sequence alignments show that dna-crypt produces few mismatches between the sequences similar to all steganographic algorithms. 