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

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

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.