CAREER: Exact and Approximate Algorithms for 3D Structure Modeling of Protein-Protein Interactions

职业：蛋白质-蛋白质相互作用 3D 结构建模的精确和近似算法

• 批准号: 1149811
• 负责人: Jinbo Xu
• 金额: $ 50万
• 依托单位: Toyota Technological Institute at Chicago
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2012
• 资助国家: 美国
• 起止时间: 2012-07-01 至 2018-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1149811&HistoricalAwards=false
• 关键词: CAREER; Exact; Approximate; Algorithms; 3D

Protein-protein interactions (PPIs) play fundamental roles in all biological processes including the maintenance of cellular integrity, metabolism, transcription/translation, and cell-cell communication. High-throughput experimental approaches have been developed to systematically identify PPIs. However, these methods cannot produce atomic 3D models of PPIs, which hinder studying PPI molecular mechanisms at atomic level and understanding cellular processes at molecular level. Atomic structures of PPIs are also important for rational drug design. High-resolution methods for PPI 3D structure determination such as X-ray or NMR are time-consuming and sometimes technically challenging, so computational method is urgently needed for PPI structure modeling. Intellectual Merit: This proposal studies exact/approximate algorithms for 3D structure modeling of PPIs, with the ultimate goal to enrich large-scale PPI networks with high-resolution 3D structure models. The proposal will study 1) simultaneous threading of all sequences of a target PPI to a complex template; 2) protein complex side-chain packing with a very large rotamer library and more realistic energy functions; and 3) simultaneous interface threading and side-chain packing to align distantly-related protein complexes. This proposal will apply several elegant and powerful techniques such as graph minor theory, probabilistic graphical models, dual relaxation and decomposition, which are not well-known in the field, to understanding the mathematical structure of the problem with more realistic and challenging settings and designing efficient algorithms. The expected outcome includes theoretical analysis of protein interfaces and complexes by graph theory, efficient algorithms for PPI structure modeling and publicly available software and servers. The resulting software can be used to verify experimental PPIs and even predict novel PPIs missed by experimental approaches. The software will benefit a broad range of biological and biomedical applications, such as gene functional annotation, better understanding of disease processes, design of novel diagnostics and drugs, personalized medicine and even bio-energy development. The resulting algorithms and software will be communicated to the broader community and also be further developed and disseminated to industry by two companies.Broader Impact: This work is expected to enrich and disseminate knowledge on systems biology and structure bioinformatics, machine learning, graph theory and optimization and further enrich the pedagogical literature. Contributions from this work to computer science are: understanding of protein graphs using graph minor theory and graph transformations and solving several computationally challenging problems by combining techniques from graph theory and continuous optimization. This research work will train minority students from two HBCU schools, future K-12 science teachers and students attending the first online bioinformatics program in Illinois. Students will receive training at the intersection of biology and computer science. The proposed course materials and book chapters will be freely available to the public.

蛋白质-蛋白质相互作用（PPI）在所有生物过程中起着重要作用，包括维持细胞完整性、代谢、转录/翻译和细胞-细胞通讯。高通量的实验方法已被开发，以系统地确定PPI。然而，这些方法不能产生PPI的原子3D模型，这阻碍了在原子水平上研究PPI分子机制和在分子水平上理解细胞过程。PPI的原子结构对于合理的药物设计也很重要。高分辨率的PPI三维结构测定方法，如X射线或核磁共振，是耗时的，有时在技术上具有挑战性，因此迫切需要计算方法的PPI结构建模。智力优势：该提案研究了PPI的3D结构建模的精确/近似算法，最终目标是用高分辨率的3D结构模型丰富大规模PPI网络。该提案将研究1）将目标PPI的所有序列同时穿线到复杂模板; 2）具有非常大的旋转异构体库和更现实的能量函数的蛋白质复合物侧链包装;以及3）同时界面穿线和侧链包装以对齐远距离相关的蛋白质复合物。该提案将应用几种优雅而强大的技术，如图子理论，概率图模型，对偶松弛和分解，这些技术在该领域并不知名，以更现实和更具挑战性的设置来理解问题的数学结构，并设计高效的算法。预期成果包括通过图论对蛋白质界面和复合物进行理论分析，PPI结构建模的有效算法以及公开可用的软件和服务器。由此产生的软件可用于验证实验PPI，甚至预测实验方法遗漏的新PPI。该软件将有利于广泛的生物和生物医学应用，如基因功能注释，更好地了解疾病过程，设计新的诊断和药物，个性化医疗，甚至生物能源开发。由此产生的算法和软件将被传达给更广泛的社区，并由两家公司进一步开发和传播到行业。更广泛的影响：这项工作预计将丰富和传播系统生物学和结构生物信息学，机器学习，图论和优化方面的知识，并进一步丰富教学文献。这项工作对计算机科学的贡献是：使用图子理论和图变换来理解蛋白质图，并通过结合图论和连续优化技术来解决几个计算上具有挑战性的问题。这项研究工作将培训来自两所HBCU学校的少数民族学生，未来的K-12科学教师和参加伊利诺伊州第一个在线生物信息学项目的学生。学生将在生物学和计算机科学的交叉点接受培训。拟议的课程材料和书籍章节将免费向公众提供。