EAGER: Graph-Based Theoretical Models and Mining Algorithms for Bioinformatics Data Analysis

基于图的理论模型和挖掘算法用于生物信息学数据分析项目摘要图表出现在令人惊讶的多样化的学科集合中，从计算机网络到社会学、生物学、生态学等。近年来，在生物信息学应用中产生了海量的数据，并最终以图形的形式表示出来。其中一些被存储为单个大的图形，例如蛋白质-蛋白质相互作用网络，而另一些被存储为图形数据库中的一组图形对象，例如药物设计中的化合物和生物信息学中的蛋白质2D/3D结构。该方案的主要目标是开发新的基于图的理论模型和算法来分析以单个大型图或图形数据库表示的生物信息学数据集，重点是(1)开发基于图分解和压缩的高效图形数据库结构模式发现方法；(2)开发大规模无标度网络图的挖掘算法，重点是开发复杂网络中层次结构和缺失链接预测的混合模型和统计推理。这些算法将通过分析生物信息学研究中出现的数据集来验证。本文的研究将对生物信息学和图形数据集中数据挖掘算法的研究和开发有一定的促进作用。它还将扩大图论、生物信息学和数据挖掘的应用范围，推动新的前沿。这项研究工作被认为是高风险高回报吗？因为它需要开发新的理论图论模型和算法，与主流的随机图论模型和算法有着根本的不同智能优点：本提案中将要开发的技术和方法建立在生物信息学、图论、数据挖掘和数据库管理的最新方法基础上。这项研究将有助于更好地理解在科学数据集中设计有效的基于图形的模型、算法和方法所涉及的问题。该项目将设计和开发一系列新的数据分析算法和方法，包括结构模式匹配和发现，以及挖掘大规模无尺度网络图。更广泛的影响：该提案将解决生物信息学、药物设计、分子生物学等科学应用领域的数据分析中的广泛问题。根据这项研究开发的基于图表的模型和算法都是计算机科学的核心，可以推广并将公开用于其他领域，包括社会学和流行病学中的个人或社会联系、信息科学中的作者共同引用、计算机科学和信息技术中的互联网和万维网。该方案的研究成果可以使生物网络的建模和仿真机制更加高效有效，并具有先进的数学能力，可应用于其他科学和工程领域。该协会和合作协会致力于将研究与教育相结合，促进多样性，建立强有力的产业伙伴关系，并广泛传播研究成果。建议的研究领域有助于在多个层面上提高学生的科学好奇心。学生们将获得大量接触到最新研究的机会。该提案的研究和教育计划都是高度跨学科的，吸引了来自不同研究领域的学生和教职员工，并从许多研究领域的工作中吸取教训。特别是，这些计划旨在突出综合生物信息学、图论和数据挖掘在创建用于生物信息学研究的下一代基于图形的模型、算法和工具方面的好处。有了这些模型、算法和工具，生物信息学研究人员将发现更有意义和相关的知识/模式，并使他们能够更好地理解和解释他们在调查中收集的数据集。学生将获得对理解、分析和挖掘不断增长的生物信息学数据集的能力的欣赏。

EAGER: Graph-based Theoretical Models and Mining Algorithms for Bioinformatics Data Analysis Project SummaryGraphs show up in a surprisingly diverse set of disciplines, ranging from computer networks to sociology, biology, ecology and many more. In recent years, huge amounts of data are generated and ultimately represented in graph format in the bioinformatics applications. Some are stored as a single large graph such as a protein-protein interaction network, while others are stored as a set of graph objects in a graph database such as chemical compounds in drug design and protein 2D/3D structures in bioinformatics. The main goal of this proposal is to develop novel graph-based theoretical models and algorithms to analyze bioinformatics data sets represented as either a single large graph or a graph database, focusing on the (1) development of efficient structure pattern discovery methods in graph databases based on graph decomposition and compression, and (2) development of mining algorithms for large scale-free network graphs, focusing on developing mixture model and statistical inference of hierarchical structure and missing link prediction in complex network. These algorithms will be validated by analyzing data sets arising in bioinformatics research. The proposed research will advance the understanding of bioinformatics and data mining algorithm research and development in graph data sets. It will also expand the application scope and push new frontiers for graph theory, bioinformatics and data mining. This research work is considered ?high risk high payoff? because it needs to develop novel theoretical graph-model and algorithms, radically different from the dominant random graph theory models and algorithmsIntellectual merit: The techniques and methods to be developed in this proposal build on state-of-the-art methods in bioinformatics, graph theory, data mining and database management. The research will result in improved understanding of the issues involved in designing efficient graph-based models, algorithms and methods in scientific data sets. The proposed project will design and develop a wide-range of novel data analysis algorithms and methods including structure pattern matching and discovery, and mining large scale-free network graphs. Broader impacts: The proposal will address a broad range of problems in the data analysis of scientific application domains such as bioinformatics, drug design, molecular biology, etc. Both the graph-based models and algorithms developed from this research are central to the computer science, and are generalizable and will be made publicly available for use in other domains, including personal or social contacts in sociology and epidemiology, author-co-citations in information science, the Internet and the World Wide Web in computer science and information technology. Research outcomes from this proposal can lead to more efficient and effective modeling and simulation mechanism of the biological network and advanced mathematical capabilities that are applicable through other science and engineering domain. The PI and Co-PI have a strong commitment to the integration of research and education, promotion of diversity, strong industrial partnership and broad dissemination of research results. The proposed research area lends itself to raising the scientific curiosity of students at many levels. Students will obtain significant exposure to the latest research. Both the research and education plans of the proposal are highly interdisciplinary, engaging students and faculty from various research areas and drawing from work on numerous fields of study. In particular, the plans serve to highlight the benefits of synthesizing bioinformatics, graph theory and data mining in creating the next generation of graph-based models, algorithms and tools for bioinformatics research. Armed with these models, algorithms and tools, bioinformatics researchers will discover more meaningful and pertinent knowledge/patterns and enable them to have a better understanding and interpretation of the data sets collected in their investigation. Students will gain an appreciation for the ability to understand, analyze and mine the growing range of bioinformatics data sets.