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

自然界中的基因表达过程通过在不同细胞中产生不同的蛋白质来评估DNA的适应性。DNA序列首先产生mRNA序列。 接下来，mRNA通过使用称为遗传密码的转换产生蛋白质序列。 最后，蛋白质序列折叠成3D结构，这决定了基因组的适应性。 该项目源于观察到遗传密码样的转换引入有趣的属性的遗传适应度函数的表示。 PI最近表明，二进制序列表示中的这种变换可以将一些具有指数大描述的函数转换为在某些实际条件下适合多项式大小近似的替代形式。 该项目将扩展这一初步发现，并探索用于天然DNA，mRNA和蛋白质的非二进制表示的更丰富的遗传密码样变换的计算。 研究将包括以下主要组成部分： 从函数归纳的角度对遗传类密码变换类进行了理论探讨; 将PI对二进制表示的初步研究结果扩展到非二进制表示; 将分析扩展到除傅立叶和沃尔什之外的正交基，特别是探索跨不同基表示的遗传密码样变换的性质的不变性，探索生物学上有意义的基选择和那些表示中的遗传密码样变换的性质，以及识别这样的变换可以用于构建有效表示的函数类; 开发一种实用的自适应技术，用于构建非二进制表示的这种表示变换。 由于目前还没有已知的强有力的技术来诱导函数与指数大的表示，只有一个多项式数量的条款，如果成功的这项研究将产生重大影响的理论计算，机器学习，数据挖掘，自动程序归纳，优化等。

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.