SGER: Context Sensitive Hidden Markov Models and Application in Computational Biology

在过去的几年里，许多研究人员已经将数字信号处理的原理用于基因组学和蛋白质组学。数字滤波和隐马尔可夫模型（HMM）技术已被应用于DNA中蛋白质编码基因的识别。 近年来，非编码基因受到了许多研究人员的重视，现在人们认识到许多类型的非编码RNA（nc-RNA）在生物体中起着重要作用。 因此，这种RNA的计算鉴定变得非常重要。 这些RNA由DNA中的代码生成，不编码蛋白质。相反，它们折叠成二级结构，并凭借这些结构发挥其生物学功能。这使得ncRNA的计算识别非常具有挑战性：需要识别的是二级折叠结构，而不是一级序列结构。这样的识别不能用常规的HSPs来完成，因为它们对应于潜在地不能识别大多数二级结构的常规语法。上下文敏感的HMM（CS-HMM）的理论是最近朝着这个目标发展，有强有力的证据表明，这样的HMM有很大的潜力，以确定非常复杂的二级结构中发现的活生物体。因此，详细探讨这一想法是非常及时的。这是拟议研究的主要目标。对于简单的RNA结构，如茎环，tRNA三叶草结构，等等，cs-HMM为基础的算法最近已经开发出来。在所提出的工作中，将开发可用于解决更复杂的相关性的csHacking的对齐、评分和训练问题的算法。为了使这些算法在生物学中有用，还将对大量记录的序列进行广泛的测试。快速算法，寻找最佳状态序列的观察符号序列和训练过程。le-csHyndrome将开发。最近的研究结果表明，许多ncRNA在不同的基因调控网络中发挥重要作用。为了构建更真实的基因调控网络，将ncRNA基因整合到网络中至关重要。这是本研究的另一个重要方面，是一项探索性的、非常规的研究，处于信号处理理论和现代生物信息学的交叉点。它的智力价值来自于对上下文敏感隐马尔可夫模型理论的深入理解，并应用于分子生物学中一个实际有趣的问题。很明显，这一研究成果不仅会在理论信号处理领域产生影响，而且也会在生物学领域产生影响。在生物学领域，非编码基因在医学和基因调控方面表现出了极大的兴趣。至于更广泛的影响，预计这项研究成果将在国际期刊上发表学术论文。例如，生物信息学、BMC生物信息学、美国国家科学院学报、自然生物技术和IEEE/ACM计算生物学和生物信息学汇刊。许多会议演示也将出现，因此将教程文章在不同层次的深度和难度。其中一些工作将被纳入加州理工学院（Caltech）的研究生课程。

The principles of digital signal processing have been used in genomics and proteomics by a number of researchers in the past few years. Digital .filtering and Hidden Markov Model (HMM) techniques have been applied for the identification of protein coding genes in DNA. More recently non coding genes have been emphasized by many researchers and it is now recognized that many types of non coding RNA (nc-RNA) play a major role in living organisms. Computational identification of such RNA has therefore become of great importance. These RNAs are generated from codes in the DNA, and do not code for proteins. Instead they fold into secondary structures and perform their biological function by virtue of these structures. This is what makes the computational identification of ncRNAs very challenging: it is the secondary folding structures that need to be identified rather than primary sequence structures. Such identification cannot be done with conventional HMMs because they correspond to regular grammars which are potentially incapable of identifying most secondary structures. The theory of context sensitive HMMs (cs-HMM) was recently developed towards this goal and there is strong evidence that such HMMs have great potential to identify very complicated secondary structures found in living organisms. A detailed exploration of this idea is therefore extremely timely. This is the main goal of the proposed research. For simple RNA structures such as stem-loops, tRNA cloverleaf structures, and so on, cs-HMM based algorithms have recently been developed. Algorithms that can be used for solving the alignment, scoring and training problems of csHMMs for more complex correlations will be developed in the proposed work. In order for these algorithms to be useful in biology, extensive testing on a large variety of documented sequences will also be performed. Fast algorithms for finding the optimal state sequence of an observed symbol sequence and for training pro.le-csHMMs will be developed. Recent results show that many ncRNAs play important roles in diverse gene regulatory networks. In order to build a more realistic gene regulatory network it is crucial to incorporate ncRNA genes in the network. This is another important aspect of the proposed research.The research is exploratory and unconventional, and is at the cross roads of cutting edge signal processing theory and modern bioinformatics. Its intellectual merit comes from the fact that a deep understanding of the theory of context sensitive hidden Markov models is developed and applied to a practically interesting problem in molecular biology. The impact will clearly be in theoretical signal processing as well as in biology, where non coding genes have been shown to be of great interest in medicine and gene regulation.As for broader impact, it is expected that the proposed research will lead to scholarly journal publications in international journals. Examples include the journals Bioinformatics, BMC bioinformatics, Proc. of the National Academy of Sciences, Nature biotechnology, and IEEE/ACM Transactions on Computational Biology and Bioinformatics. Many conference presentations will also emerge, and so will tutorial articles at various levels of depth and difficulties. Some of the work will be incorporated into the graduate curricula at the California Institute of Technology (Caltech).