Coding Theory and Protein Synthesis Avogadro Scale Engineering Form and Function November 18 19 2003 Elebeoba E May Computational Biology Department Sandia National Laboratories eemay sandia gov Sandia is a multiprogram laboratory operated by Sandia Corporation a Lockheed Martin Company for the United States Department of Energy under contract DE AC04 94AL85000 Agenda It is the glory of God to conceal a matter to search out a matter is the glory of kings Proverbs 25 2 NIV Error Control at Diverse Molecular Scales Coding Theory Models of Protein Synthesis Gatlin Yockey May et al Applications of Coding Theory to Genetic Classification Molecular Computation Construction and Control in Protein Synthesis Nucleotides Did nature select a parity check code D A Mac D naill Numerical Interpretation of nucleotides depicted as positions on a B 4 hypercube a even parity nucleotides b odd parity nucleotides The natural alphabet is structured as an error checking code D A Mac D naill A parity code interpretation of nucleotide alphabet composition Chem Comm 2002 2062 2063 and http www tcd ie Chemistry People macdonaill Protein Degeneracy of the genetic code http www people virginia edu rjh9u code html B Hayes how quickly a biochemical puzzle was reduced to an abstract problem in symbol manipulation B Hayes The Invention of the Genetic Code Sc Am 1998 Physicist George Gamow and coding theorist Solomon W Golomb Experimental evidence from Marshall W Nirenberg and J Heinrich Matthaei NIH Protein Information theory and binding sites T D Schneider Strong minor groove base conservation in sequence logos implies DNA distortion or base flipping during replication and transcription initiation Nucleic Acids Research 2001 Vol 29 No 23 4881 4891 Genome Increased length increased fidelity Mutation Rates RNA viruses 1 0 1 DNA microbes 1 300 Higher eukaryotes 1 300 EfGn Comparison of microbial genome base mutation rate to genome size exhibits power law behavior inverse relation between genome size and base mutation rate G Battail increasing the codeword length results in a decreasing probability of error Comparison of higher eukaryotic genome base mutation rate to genome size inverse relation between genome size and base mutation rate Evidence Is there evidence of error control in protein synthesis process Liebovitch et al 1996 Rosen and Moore 2003 computational experiments did not find evidence for linear block codes Approach not comprehensive did not consider convolutional coding or noise May et al Looked for optimal generator for translation initiation sites Highly probable for encoding model not to conform to known error control codes Agenda It is the glory of God to conceal a matter to search out a matter is the glory of kings Proverbs 25 2 NIV Error Control at Diverse Molecular Scales Coding Theory Models of Protein Synthesis Gatlin Yockey May et al Applications of Coding Theory to Genetic Classification Molecular Computation Construction and Control in Protein Synthesis Central Dogma of Genetics Genetic Information Transmission A Encode eukaryotes Channel Decode B http www stat stanford edu susan courses s166 central gif Coding Theory Models of Protein Synthesis Gatlin LL Information theory and the Living System 1972 Yockey Hubert Information Theory and Molecular Biology 1992 Coding Theory View of Protein Synthesis May et al JFI 2004 Genetic Genetic Encoder Channel Genetic Information Errors Principal Hypothesis If mRNA is viewed as a noisy encoded signal it is feasible to use Genetic Decoder principles of error control coding theory to interpret the genetic translation initiation mechanism mRNA AUG UAA 3 Engineering Communication System B A Error Control Encoder n bit Information 111 000 000 111 111 000 000 111 k bit 1 0 0 1 Information Channel 111 001 000 110 Errors Decoder Noise n bit Information 111 001 000 110 1 0 0 1 k bit 1 0 0 1 Information Engineering Communication System B A Error Control Encoder n bit Information 111 000 000 111 111 000 000 111 k bit 1 0 0 1 Information Channel 111 001 000 110 Errors Decoder Noise n bit Information 111 001 000 110 1 0 0 1 k bit 1 0 0 1 Information Agenda It is the glory of God to conceal a matter to search out a matter is the glory of kings Proverbs 25 2 NIV Error Control at Diverse Molecular Scales Coding Theory Models of Protein Synthesis Gatlin Yockey May et al Applications of Coding Theory to Genetic Classification Molecular Computation Construction and Control in Protein Synthesis Biological Coding Theory David Loewenstern et al Compression for DNA sequence classification Leonard Adleman et al Lila Kari et al Molecular computation Encoding for DNA computing Error control coding Thomas Schneider et al Biological information theory Error control via sphere packing Storage Transmission Error Control Coding Based Methods Efficient Coding for the Desoxyribonucleic Channel S W Golomb 1962 Applied Biorthogonal codes to genetic coding problem the codon to amino acid mapping challenge Andrzej K Konopka 1984 Gerard Battail Table Based Convolutional Code for E coli Promoter P Bermel Based on the informational content of E coli promoter approximates the coding rate for promoter region as 1 9 Developed a possible 1 5 binary code for E coli promoter region Coding Theory in RBS Classification DB NRD SD AUG Horizontal axis is position relative to the first base of the initiation codon Vertical axis is the mean of the aligned minimum Hamming distance values by position for the 3 sequence groups Hamming distance of positions where two vectors differ May et al BioSystems 2004 Coding Theory in RBS Classification PDF PDF p 0 5 CDF CDF p 0 5 b 15 b 14 b 11 b 1 A U G 80 73 81 70 b 15 b 14 b 13 b 12 b 11 b 10 b 9 b 8 b 7 60 50 59 065 62 105 50 50 40 935 40 Davg 15 Davg 14 Davg 11 37 895 26 19 30 20 10 0 Correct Classification s Incorrect Classification Coding Theory and Molecular Computation Leonard M Adleman et al Lila Kari et al Molecular computation Encoding for DNA computing Error control coding v 1 v v 2 1 v 2 ligase v v 1 M Stojanovic and D Stefanovic A deoxyribozyme based molecular automaton Nature Biotech 2003 Can achieve computational robustness using coding theory http www scs uiuc edu scott index files ligation gif 2 Construction and control Quantify and Optimize Protein Translation Polypeptide Protein 50s sub unit Initiation Factors 5 UAA 3 AUG 5 30s sub unit Leader Messenger RNA mRNA AUG GUG UUG Coding Region UAA UAG UGA Ribosome binding site contained in leader