III: Small: Techniques for Integrated Analysis of Graphs with Applications to Cheminformatics and Bioinformatics

许多科学工作产生的数据可以建模为图表：蛋白质相互作用的高通量生物实验，化合物的高通量筛选，社交网络，生态网络和食物网，数据库模式和本体。 访问和分析所得到的注释和概率图对于推进科学研究、现有系统的准确建模和分析以及新系统的工程设计至关重要。 该项目旨在通过集成数据库和数据挖掘技术，开发一套可扩展的图数据库查询和挖掘工具。 本文的研究工作既是理论性的，也是实证性的。新的理论思想和算法正在开发中，这些都被应用到化学信息学和生物信息学领域。第一个研究重点是研究图形数据管理和图形挖掘的原语。一个声明性的查询语言的图形正在研究中。这种语言是基于一个正式的语言的图形和图代数，并分离的关注规范和实现。图上的相似性搜索和挖掘重要模式的技术的可扩展性正在研究作为这一推力的一部分。第二个研究推力将开发的技术应用到化学信息学领域。正在研究的具体任务是寻找相似的化合物，挖掘重要的基序，多样性分析和大分子复合物的分析。最后的研究重点是将开发的方法应用于生物信息学领域。已经出现了广泛多样的生物数据类型的数据爆炸，其产生于转录谱、蛋白质-蛋白质相互作用、基因组结构、遗传表型、基因相互作用、基因表达、蛋白质组学和其他技术的全基因组表征。正在开发的技术可以有效地集成和分析来自多个来源和模型的数据，同时加速（相互作用和功能）预测和途径发现。有关该项目的更多信息，请访问项目网页http://www.cs.ucsb.edu/~dbl/0917149.php。

A number of scientific endeavors generate data that can be modeled as graphs: high-throughput biological experiments on protein interactions, high throughput screening of chemical compounds, social networks, ecological networks and food-webs, database schemas and ontologies. Access and analysis of the resulting annotated and probabilistic graphs are crucial for advancing the state of scientific research, accurate modeling and analysis of existing systems, and engineering of new systems. This project aims to develop a set of scalable querying and mining tools for graph databases by integrating techniques from databases and data mining. The proposed research work is theoretical as well as empirical. New theoretical ideas and algorithms are being developed and these are being applied to the domains of Cheminformatics and Bioinformatics.The first research thrust examines primitives for graph data management and graph mining. A declarative query language for graphs is being investigated. This language is based on a formal language for graphs and a graph algebra, and separates the concerns of specification and implementation. Scalability of techniques for similarity search on graphs and mining for significant patterns is being investigated as a part of this thrust.The second research thrust applies the developed techniques to the domain of Cheminformatics. Specific tasks that are being examined are search for similar compounds, mining for significant motifs, diversity analysis, and analysis of macromolecular complexes.The final research thrust applies the developed methods to the domain of Bioinformatics. There has been an explosion of data of widely diverse biological data types, arising from genome-wide characterization of transcriptional profiles, protein-protein interactions, genomic structure, genetic phenotype, gene interactions, gene expression, proteomics, and other techniques. Techniques being developed can integrate and analyze data from multiple sources and models efficiently, while accelerating (interaction and function) prediction, and pathway discovery.Further information about the project can be found at the project web page http://www.cs.ucsb.edu/~dbl/0917149.php.