Simplified decoding techniques for linear block codes

Error correcting codes are combinatorial objects, designed to enable reliable transmission of digital data over noisy channels. They are ubiquitously used in communication, data storage etc. Error correction allows reconstruction of the original data from received word. The classical decoding algorithms are constrained to output just one codeword. However, in the late 50’s researchers proposed a relaxed error correction model for potentially large error rates known as list decoding. The research presented in this thesis focuses on reducing the computational effort and enhancing the efficiency of decoding algorithms for several codes from algorithmic as well as architectural standpoint. The codes in consideration are linear block codes closely related to Reed Solomon (RS) codes. A high speed low complexity algorithm and architecture are presented for encoding and decoding RS codes based on evaluation. The implementation results show that the hardware resources and the total execution time are significantly reduced as compared to the classical decoder. The evaluation based encoding and decoding schemes are modified and extended for shortened RS codes and software implementation shows substantial reduction in memory footprint at the expense of latency. Hermitian codes can be seen as concatenated RS codes and are much longer than RS codes over the same aphabet. A fast, novel and efficient VLSI architecture for Hermitian codes is proposed based on interpolation decoding. The proposed architecture is proven to have better than Kötter’s decoder for high rate codes. The thesis work also explores a method of constructing optimal codes by computing the subfield subcodes of Generalized Toric (GT) codes that is a natural extension of RS codes over several dimensions. The polynomial generators or evaluation polynomials for subfield-subcodes of GT codes are identified based on which dimension and bound for the minimum distance are computed. The algebraic structure for the polynomials evaluating to subfield is used to simplify the list decoding algorithm for BCH codes. Finally, an efficient and novel approach is proposed for exploiting powerful codes having complex decoding but simple encoding scheme (comparable to RS codes) for multihop wireless sensor network (WSN) applications.

Recoding: reprogrammed genetic decoding with an emphasis on antizyme regulatory frameshifting

Recoding embraces mechanisms that augment the rules of standard genetic decoding. The deviations from standard decoding are often purposeful and their realisation provides diverse and flexible regulatory mechanisms. Recoding events such as programed ribosomal frameshifting are especially plentiful in viruses. In most organisms only a few cellular genes are known to employ programed ribosomal frameshifting in their expression. By far the most prominent and therefore well-studied case of cellular +1 frameshifting is in expression of antizyme mRNAs. The protein antizyme is a key regulator of polyamine levels in most eukaryotes with some exceptions such as plants. A +1 frameshifting event is required for the full length protein to be synthesized and this requirement is a conserved feature of antizyme mRNAs from yeast to mammals. The efficiency of the frameshifting event is dependent on the free polyamine levels in the cell. cis-acting elements in antizyme mRNAs such as specific RNA structures are required to stimulate the frameshifting efficiency. Here I describe a novel stimulator of antizyme +1 frameshifting in the Agaricomycotina class of Basidiomycete fungi. It is a nascent peptide that acts from within the ribosome exit tunnel to stimulate frameshifting efficiency in response to polyamines. The interactions of the nascent peptide with components of the peptidyl transferase centre and the protein exit tunnel emerge in our understanding as powerful means which the cell employs for monitoring and tuning the translational process. These interactions can modulate the rate of translation, protein cotranslational folding and localization. Some nascent peptides act in concert with small molecules such as polyamines or antibiotics to stall the ribosome. To these known nascent peptide effects we have added that of a stimulatory effect on the +1 frameshifting in antizyme mRNAs. It is becoming evident that nascent peptide involvement in regulation of translation is a much more general phenomenon than previously anticipated.

Gröbner basis techniques for certain problems in coding and systems theory

There is much common ground between the areas of coding theory and systems theory. Fitzpatrick has shown that a Göbner basis approach leads to efficient algorithms in the decoding of Reed-Solomon codes and in scalar interpolation and partial realization. This thesis simultaneously generalizes and simplifies that approach and presents applications to discrete-time modeling, multivariable interpolation and list decoding. Gröbner basis theory has come into its own in the context of software and algorithm development. By generalizing the concept of polynomial degree, term orders are provided for multivariable polynomial rings and free modules over polynomial rings. The orders are not, in general, unique and this adds, in no small way, to the power and flexibility of the technique. As well as being generating sets for ideals or modules, Gröbner bases always contain a element which is minimal with respect tot the corresponding term order. Central to this thesis is a general algorithm, valid for any term order, that produces a Gröbner basis for the solution module (or ideal) of elements satisfying a sequence of generalized congruences. These congruences, based on shifts and homomorphisms, are applicable to a wide variety of problems, including key equations and interpolations. At the core of the algorithm is an incremental step. Iterating this step lends a recursive/iterative character to the algorithm. As a consequence, not all of the input to the algorithm need be available from the start and different "paths" can be taken to reach the final solution. The existence of a suitable chain of modules satisfying the criteria of the incremental step is a prerequisite for applying the algorithm.

Ribosomal frameshifting and transcriptional slippage: from genetic steganography and cryptography to adventitious use

Genetic decoding is not ‘frozen’ as was earlier thought, but dynamic. One facet of this is frameshifting that often results in synthesis of a C-terminal region encoded by a new frame. Ribosomal frameshifting is utilized for the synthesis of additional products, for regulatory purposes and for translational ‘correction’ of problem or ‘savior’ indels. Utilization for synthesis of additional products occurs prominently in the decoding of mobile chromosomal element and viral genomes. One class of regulatory frameshifting of stable chromosomal genes governs cellular polyamine levels from yeasts to humans. In many cases of productively utilized frameshifting, the proportion of ribosomes that frameshift at a shift-prone site is enhanced by specific nascent peptide or mRNA context features. Such mRNA signals, which can be 5′ or 3′ of the shift site or both, can act by pairing with ribosomal RNA or as stem loops or pseudoknots even with one component being 4 kb 3′ from the shift site. Transcriptional realignment at slippage-prone sequences also generates productively utilized products encoded trans-frame with respect to the genomic sequence. This too can be enhanced by nucleic acid structure. Together with dynamic codon redefinition, frameshifting is one of the forms of recoding that enriches gene expression.

Novel ciliate genetic code variants including the reassignment of all three stop codons to sense codons in Condylostoma magnum

mRNA translation in many ciliates utilizes variant genetic codes where stop codons are reassigned to specify amino acids. To characterize the repertoire of ciliate genetic codes, we analyzed ciliate transcriptomes from marine environments. Using codon substitution frequencies in ciliate protein-coding genes and their orthologs, we inferred the genetic codes of 24 ciliate species. Nine did not match genetic code tables currently assigned by NCBI. Surprisingly, we identified a novel genetic code where all three standard stop codons (TAA, TAG, and TGA) specify amino acids in Condylostoma magnum. We provide evidence suggesting that the functions of these codons in C. magnum depend on their location within mRNA. They are decoded as amino acids at internal positions, but specify translation termination when in close proximity to an mRNA 3' end. The frequency of stop codons in protein coding sequences of closely related Climacostomum virens suggests that it may represent a transitory state.mRNA translation in many ciliates utilizes variant genetic codes where stop codons are reassigned to specify amino acids. To characterize the repertoire of ciliate genetic codes, we analyzed ciliate transcriptomes from marine environments. Using codon substitution frequencies in ciliate protein-coding genes and their orthologs, we inferred the genetic codes of 24 ciliate species. Nine did not match genetic code tables currently assigned by NCBI. Surprisingly, we identified a novel genetic code where all three standard stop codons (TAA, TAG, and TGA) specify amino acids in Condylostoma magnum. We provide evidence suggesting that the functions of these codons in C. magnum depend on their location within mRNA. They are decoded as amino acids at internal positions, but specify translation termination when in close proximity to an mRNA 3' end. The frequency of stop codons in protein coding sequences of closely related Climacostomum virens suggests that it may represent a transitory state.

Comparative survey of the relative impact of mRNA features on local ribosome profiling read density

Ribosome profiling (Ribo-seq), a promising technology for exploring ribosome decoding rates, is characterized by the presence of infrequent high peaks in ribosome footprint density and by long alignment gaps. Here, to reduce the impact of data heterogeneity we introduce a simple normalization method, Ribo-seq Unit Step Transformation (RUST). RUST is robust and outperforms other normalization techniques in the presence of heterogeneous noise. We illustrate how RUST can be used for identifying mRNA sequence features that affect ribosome footprint densities globally. We show that a few parameters extracted with RUST are sufficient for predicting experimental densities with high accuracy. Importantly the application of RUST to 30 publicly available Ribo-seq data sets revealed a substantial variation in sequence determinants of ribosome footprint frequencies, questioning the reliability of Ribo-seq as an accurate representation of local ribosome densities without prior quality control. This emphasizes our incomplete understanding of how protocol parameters affect ribosome footprint densities.