Collaborative Research: ASES: An Approximate Search Engine for Structure

该研究项目的目标是能够以快速(即，相对于被搜索对象的数量亚线性)和高效的方式处理对诸如树和图的组合结构的近似查询。最终目标是与文本文档中的近似关键字搜索一样快。该方法包括：(1)发现在多项式时间内高质量地回答这些NP-完全问题的最佳启发式；(2)发现数据结构以快速地对数千或数百万这样的对象进行查询。该项目的成果将提供在图形和树形结构数据中搜索模式的技术和软件。这种搜索引擎的可能应用包括在蛋白质、化合物、神经解剖结构、Web/文本过滤器和XML文档中进行搜索。这项研究中开发的技术特别适用于生物信息学和生物计算应用。沙沙教授和王教授计划在这些领域与另外五名研究人员合作：国家癌症研究所的杰克·柯林斯，致力于药物设计的小分子-蛋白质对接；生物学教授和哈佛大学草药研究所所长迈克尔·多诺霍，计划将这项研究应用于系统发生树；国家癌症研究所的布鲁斯·夏皮罗，正在开发确定核酸结构/功能的算法和计算系统；国家生物医学研究基金会的凯西·吴，从事蛋白质序列分析和分类的研究；以及丹尼尔·扎哈雷维兹，国家癌症研究所的目标是通过更好的搜索能力，使生物和结构数据更容易为研究界所获得。这些合作者帮助激励和验证用于生物applications.http://www.cis.njit.edu/~jason/sigmod.html的树和图形匹配工具和算法开发

The goal of this research project is to make it possible to process approximate queries on combinatorial structures such as trees and graphs in a fast (i.e., sublinear with respect to the number of objects being searched) and efficient manner. The ultimate goal is to be as fast as approximate keyword search in text documents. The approach consists of: (1) discovering the best heuristics for answering these NP-complete problems in polynomial time with high quality, and (2) discovering data structures to make queries on thousands or millions of such objects fast. The results of this project will provide techniques and software to search for patterns among graph and tree structured data. Possible applications of such a search engine include searches among proteins, chemical compounds, neuroanatomical structures, Web/text filters and XML documents. The techniques developed in this research are in particular suitable for bioinformatics and biocomputing applications. Professors Shasha and Wang plan to collaborate with five additional researchers in these areas: Jack Collins, National Cancer Institute working in small molecule-protein docking for drug design; Michael Donohue, Professor of Biology and Director of the Harvard University Herbaria planning to apply this research to phylogenic trees; Bruce Shapiro, National Cancer Institute developing algorithms and computational systems for determining structure/function of nucleic acids; Cathy Wu, National Biomedical Research Foundation doing research in analysis and classification of protein sequences; and Daniel Zaharevitz, National Cancer Institute whose goal is to make biological and structural data more available to the research community via better search capabilities. These collaborators help to motivate and validate the tree and graph matching tools and algorithms development for biological applications.http://www.cis.njit.edu/~jason/sigmod.html