Collaborative Research: ASES: An Approximate Search Engine for Structure

合作研究：ASES：结构近似搜索引擎

• 批准号: 9988636
• 负责人: Jason Wang
• 金额: $ 19.47万
• 依托单位: New Jersey Institute of Technology
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2000
• 资助国家: 美国
• 起止时间: 2000-09-15 至 2004-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9988636&HistoricalAwards=false
• 关键词: Collaborative; Research; ASES; Approximate; Search

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

该研究项目的目的是使在诸如树木和图形之类的组合结构上的近似查询（即有关被搜索的对象数量）和高效方式处理。最终目标是与文本文档中的近似关键字搜索一样快。该方法包括：（1）在多项式时间内以高质量回答这些NP完整问题的最佳启发式方法，以及（2）发现数据结构以快速对数千或数百万此类对象进行查询。该项目的结果将提供技术和软件，以在图和树结构化数据之间搜索模式。这种搜索引擎的可能应用包括蛋白质，化合物，神经解剖结构，Web/文本过滤器和XML文档之间的搜索。这项研究中开发的技术特别适合生物信息学和生物计算应用。 Shasha教授和Wang计划与这些领域的五个其他研究人员合作：杰克·柯林斯（Jack Collins），国家癌症研究所（National Cancer Institute）从事小分子 - 蛋白质对象进行药物设计；生物学教授兼哈佛大学草药主任迈克尔·多诺休（Michael Donohue）计划将这项研究应用于系统发育； Bruce Shapiro，国家癌症研究所开发算法和计算系统，用于确定核酸的结构/功能； Cathy Wu，国家生物医学研究基金会进行蛋白质序列分析和分类研究；国家癌症研究所（National Cancer Institute）的丹尼尔·扎哈里维茨（Daniel Zaharevitz）的目标是通过更好的搜索能力使研究界更能为研究社区提供。这些合作者有助于激励和验证生物应用的树和图形匹配工具以及算法开发.http：//www.cis.njit.edu/~jason/~jason/sigmod.html