Biocomplexity: Polynomial Complexity Computation, Representation Construction, and the Genetic Code

Washington State University, Pullman WA

Investigators

Abstract

The gene expression process in nature evaluates the fitness of a DNA through the production of different proteins in different cells. The DNA sequence first produces the mRNA sequence. Next, the mRNA produces the protein sequence by using a transformation called the genetic code. Finally, the protein sequence folds into a 3D structure which determines the fitness of the genome. This project derives from the observation that genetic code-like transformations introduce interesting properties to the representation of a genetic fitness function. The PI recently showed that such transformations in binary sequence representations can convert some functions with an exponentially large description to an alternative form that is amenable to polynomial-size approximation under certain practical conditions. This project will extend this preliminary finding and explore the computation in richer genetic code-like transformations for non-binary representations that are used in natural DNA, mRNA, and proteins. The research will have the following primary components: theoretical exploration of the class of genetic code-like transformations from the function induction perspective; extension of the PI's preliminary findings for binary representation to non-binary representations; extension of the analysis to orthogonal bases other than Fourier and Walsh, in particular exploration of the invariance of the properties of genetic code-like transformations across different basis representations, exploration of biologically meaningful choice of basis and the properties of genetic code-like transformations in those representations, and identification of the class of functions for which such transformations can be used to construct efficient representations; development of a practical adaptive technique for constructing such representation transformations for non-binary representations. Because there currently exists no known strong technique to induce functions with exponentially large representation to functions with only a polynomial number of terms, if successful this research will have significant impact on the theory of computation, machine learning, data mining, automated program induction, optimization, etc.