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

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

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.