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

EAGER：CCF-AF：生物问题的组合和概率方面

• 批准号: 1049902
• 负责人: Saad Mneimneh
• 金额: $ 20万
• 依托单位: CUNY Hunter College
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2010
• 资助国家: 美国
• 起止时间: 2010-09-01 至 2014-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1049902&HistoricalAwards=false
• 关键词: EAGER; CCF; AF; Combinatorial; Probabilistic

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.

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