AF:III: small: Convex optimization for protein-protein interaction network alignment

高通量实验技术已经产生了大量的蛋白质-蛋白质相互作用（PPI）数据。PPI网络的比对分析（如比对）有助于理解物种间的进化关系，有助于识别功能模块，并为蛋白质功能注释提供信息。本提案的研究目标是研究能够比现有方法更准确地对齐PPI网络的优化方法。本提案将应用几种优雅而强大的优化技术来理解问题的数学结构并开发有效的对齐算法。本提案还将开发实现所提出算法的软件。所提出的算法将作为独立程序和Cytoscape插件实现，以便生物学家可以轻松使用它们。由此产生的软件和插件将有利于广泛的生物和生物医学应用，如蛋白质功能注释，疾病过程的理解，新型诊断和药物的设计，以及精准医疗。研究成果将通过各种渠道传播到优化、计算机视觉/图形学和生物界。源代码将被发布，以便它可以对其他想要为自己的研究项目调整代码的网络分析研究人员和其他想要从事生物网络分析的优化方法研究人员有用。该项目将培养少量博士生和暑期实习生，他们将接受优化技术、网络生物学和编程交叉的培训。本科生和未被充分代表的学生将通过我们的暑期实习项目，CRA-W和合作者招募。研究结果将被整合到课程材料中，并用于伊利诺伊州的一个在线生物信息学项目，该项目培养了许多代表性不足的学生。本提案将研究一种新的凸优化算法，用于对齐两个或多个PPI网络。这种凸方法与广泛使用的种子-扩展或渐进对齐策略的区别在于，它同时对齐所有输入网络和蛋白质，而后者使用贪婪策略来构建对齐。贪婪策略可能会在早期阶段引入无法修复的对齐错误，但这种凸方法可以避免这种情况。由于其同步比对策略，该凸方法将比现有方法检测到更多在所有输入PPI网络中功能保守的蛋白质，并产生更准确的多个网络成对比对。本文还将研究几种方法，通过利用PPI网络的特殊拓扑特性和探索蛋白质的低秩表示来加快所提出的凸对齐方法。最后，本提案将提出的算法作为一个独立的软件包和Cytoscape插件来实现，以极大地促进比较网络分析在生物和生物医学科学发现中的应用。

High-throughput experimental techniques have been producing a large amount of protein-protein interaction (PPI) data. Comparative analysis (e.g., alignment) of PPI networks greatly benefits the understanding of evolutionary relationship among species, helps identify functional modules and provides information for protein function annotations. The research goal of this proposal is to study optimization methods that can align PPI networks much more accurately than existing methods. This proposal will apply several elegant and powerful optimization techniques to understand the mathematical structure of the problem and develop efficient alignment algorithms. This proposal will also develop software implementing the proposed algorithms. The proposed algorithms will be implemented as both a standalone program and Cytoscape plugin so that they can be easily used by biologists. The resultant software and plugin shall benefit a broad range of biological and biomedical applications, such as protein functional annotation, understanding of disease processes, design of novel diagnostics and drugs, and precision medicine. The research results will be disseminated to the optimization, computer vision/graphics and biology communities through a variety of venues. The source code will be released so that it can be useful to other network analysis researchers who want to adapt the code for their own research projects and to other optimization method researchers who want to work on biological network analysis. This project will train a few PhD students and summer interns, who will receive training in the intersection of optimization techniques, network biology and programming. Undergraduate and underrepresented students will be recruited through our summer intern program, CRA-W and collaborators. The research results will be integrated into course materials and used in an Illinois online bioinformatics program that has trained many underrepresented students. This proposal will study a novel convex optimization algorithm for the alignment of two or multiple PPI networks. This convex method distinguishes itself from the widely-used seed-and-extension or progressive alignment strategy in that it simultaneously aligns all the input networks and proteins while the latter methods use a greedy strategy to build an alignment. A greedy strategy may introduce alignment errors at an early stage that cannot be fixed later, but this convex method can avoid this. Due to its simultaneous alignment strategy, this convex method shall detect many more proteins that are functionally conserved across all input PPI networks than existing methods and produce more accurate pairwise alignments of multiple networks. This proposal will also study a few methods to speed up the proposed convex alignment method, by making use of special topology properties of PPI networks and exploring low-rank representation of proteins. Finally, this proposal will implement the proposed algorithms as a standalone software package and Cytoscape plugin to greatly facilitate the application of comparative network analysis to biological and biomedical science discovery.