EAGER: CCF-AF: Combinatorial and Probabilistic Aspects of Biological Problems

提出了一种基于组合数学和概率的方法来解决计算生物学中的一些问题。这是一项探索性研究的一部分，旨在提取简单而优雅的数学抽象，而不是专注于？真相生物学问题的细节。基本原理如下：（1）组合对象的属性直接导致用于解决产生它们的问题的算法，以及（2）组合和概率方法提供了许多分析工具，可以用于确定这些算法的最坏情况和预期性能。为了建立该方法的有效性，PI通过考虑三个示例问题允许一定的广度。然而，这与他们的长期目标是一致的，即开发数学模型，从而产生可行的计算算法，并可以在聚合水平上解释生物学行为。RNA相互作用：一种基于siRNA（小干扰RNA）的治疗方法可能最终抵消HIV，现在已经不遥远了。siRNA是与另一种RNA（例如HIV的RNA）相互作用的RNA分子的特殊实例，在这种情况下敲除HIV基因。由于其在基因调控机制中的作用，RNA相互作用有可能成为一类新的药物。PI将根据RNA-RNA相互作用图进行研究，以预测两种RNA相互作用产生的RNA复合物。虽然这个预测问题是NP完全的，但PI已经提出了新的有效的近似算法来预测E.杆菌PI将提高算法的运行时间/逼近能力，将算法应用于广泛的RNA复合物，并使用RNA-RNA相互作用图和随机搜索的组合研究算法的扩展以处理多个RNA（而不仅仅是两个）。蛋白质相互作用位点：同样，蛋白质相互作用对于确定蛋白质复合物的功能至关重要。然而，相互作用图在这里并不能提供一个合适的模型，因为蛋白质相互作用更为复杂。相反，预测蛋白质的相互作用位点成为一项中心任务。PI将实施组合方法，该方法基于将蛋白质折叠在环面（闭合螺旋）上并对具有某些特性（例如疏水性）的氨基酸进行几何分组以获得簇。簇代表潜在的相互作用位点。这种方法的一个动机是疏水螺旋倾向于远离溶剂，因此相互作用。结合随机环面的数学模型，（也将开发），这种新方法将可能消除预测蛋白质3D折叠的需要。（高度棘手的问题），并克服了简单的方法，否则，是完全基于序列低复杂度序列LCS：虽然由折叠和/或相互作用产生的结构是一个重要方面，但蛋白质中结构的缺乏引起了关于其序列功能的重要问题，特别是当这些序列被保留时。真菌的细胞壁基因含有丰富的LCS，它们大多是无结构的。了解LCS的功能将有助于指导任何有效的医学治疗，例如针对子宫感染，必须通过其细胞壁界面靶向真菌。PI认为LCS使用类似于DNA复制错误的机制进化，导致序列长度偏差很大（幂律分布）。PI提出了一个概率模型的进化，明确占长度，并表现出类似的分布。这个模型将有助于解释LCS经历的进化类型，并将阐明它们在细胞壁中的功能。该模型还将提供一种替代的方法，基于遗传算法的方法，尽管有许多现有的努力，通常失败的存在LCS.该建议的智力价值在于提供必要的基础，为一些组合/概率问题，需要强大的数学和算法的各个领域的知识，并提供激进的方法来捕捉生物学的不同方面。因此，虽然这项研究植根于组合数学和概率，但它同时对生物科学产生了更广泛的影响。尽管生物学是驱动力，但这些公式足够通用，并将研究扩展到其生物学意义之外：RNA相互作用引入了一个有趣的几何图形问题，避免了边缘的交叉。蛋白质相互作用位点导致了正则图上的一个优雅问题。LCS的演化是通过一般的随机游走来捕获的，该随机游走适用于许多随时间表现出随机伸长和缩短的系统，例如句子中的单词（语言学）。该提案还对亨特学院的Qu Bi（定量生物学）计划产生了更广泛的影响，它可以为新开发的Qu Bi课程提供大量的项目材料。

An approach based on combinatorics and probability is proposed to tackle a number of problems in computational biology. This is part of an exploratory research for an EAGER grant that aims at extracting simple and elegant mathematical abstractions rather than focusing on the ?nitty-gritty? details of the biological problem. The rationale is the following: (1) Properties of combinatorial objects lead directly to algorithms for solving the problems that generate them and (2) combinatorial and probabilistic methods provide many analytical tools that can be used for determining the worst-case and expected performance of these algorithms. To establish the validity of the approach, the PIs allow some breadth by considering three exemplar problems. This, however, is consistent with their long term goal to develop mathematical models that lead to viable computational algorithms and that can explain biological behavior at an aggregate level.RNA interaction: An siRNA-based (small interfering RNA) treatment that may ultimately counteract HIV is now not far fetched. An siRNA is a special example of an RNA molecule that interacts with another RNA (e.g. that of HIV), in this case to knockout the HIV gene. Because of its role in gene regulation mechanisms, RNA interaction has a potential to become a new class of drugs. The PIs will conduct a research based on RNA-RNA interaction graphs to predict RNA complexes resulting from the interaction of two RNAs. While this prediction problem is NP-complete, the PIs have proposed novel and efficient approximation algorithms that predict known and unusual RNA complexes in E. Coli. The PIs will improve the running time/approximation capability of the algorithms, apply the algorithms to a wide range of RNA complexes, and study the extension of the algorithms to handle multiple RNAs (not just two) using a combination of RNA-RNA interaction graphs and random search.Protein interaction sites: Similarly, protein interaction is crucial for determining the function of protein complexes. Interaction graphs, however, do not provide a suitable model here because protein interaction is more complex. Instead, predicting the interaction sites of a protein becomes a central task. The PIs will implement a combinatorial approach based on folding the protein on a torus (closed helix) and geometrically grouping amino acids with certain properties (e.g. hydrophobic) to obtain clusters. The clusters represent potential interaction sites. One motivation for this approach is that hydrophobic helices tend to stay away from the solvent and, hence, to interact. Together with a mathematical model of random tori (that will also be developed), this new approach will potentially eliminate the need to predict the 3D folding of the protein (highly intractable problem) and overcomes the simplicity of methods that, otherwise, are entirely sequences based (ignore the geometry).Low complexity sequences LCS: While structure resulting from folding and/or interaction is an important aspect, the lack of structure in proteins raises an important question about the function of their sequences, especially when those sequences are preserved. The cell wall genes of fungi contain an abundance of LCS that are mostly structure-free. Understanding the function of LCS will help guide any effective medical treatment, for instance against uterine infections, that must target the fungus through its cell wall interface. The PIs believe that LCS evolve using a mechanism similar to DNA replication error, resulting in sequences with large deviations in length (a power law distribution). The PIs propose a probabilistic model of evolution that explicitly accounts for lengths and exhibits a similar distribution. This model will help explain the type of evolution that LCS undergo and will shed light on their function in the cell wall. The model will also provide an alternative to alignment-based methods which, despite many existing efforts, usually fail in the presence of LCS.The intellectual merit of the proposal lies in providing essential foundation for a number of combinatorial/probabilistic problems that require a strong knowledge of various fields of mathematics and algorithms, and provide radical ways to capture different aspects of Biology. Therefore, while the research has roots in combinatorial mathematics and probability, it has simultaneously a broader impact on biological sciences. Despite Biology being the driving force, the formulations are general enough and extend the research beyond its biological significance: RNA interaction introduces an interesting geometric graph problem that avoids intersection of edges. Protein interaction sites lead to an elegant problem on regular graphs. Evolution of LCS is captured by a general random walk that is applicable for many systems that exhibits random elongation and shortening over time, e.g. words in a sentence (linguistics). The proposal has also a broader impact on the Hunter College QuBi (Quantitative Biology) initiative where it could provide substantial projects material for the newly developed QuBi courses.