Pattern Discovery in Combinatorial Databases: Algorithms, Applications, and Software for the Scientific Community

这是一个机构间的合作项目。由序列、树和图组成的组合数据出现在许多科学学科中。例如，蛋白质的一级结构是一个序列，而三级结构是一个图形。比较这些数据以找到相似之处需要使用“距离度量”来测量两个数据项之间的差异。有多种距离度量是可能的。这项工作主要包括：(I)发明计算已知距离度量的有效方法；(Ii)开发数据结构以确定一组数据项中的哪一项(根据给定距离度量)与新数据项最接近；(Iii)用于发现相对于给定距离度量具有到给定数据项集合的最小或接近最小距离的模式的技术和S软件；以及(Iv)用于在偶尔空闲的工作站的网络上解决此类发现问题的软件。这项工作将帮助每个领域的近似匹配是重要的。在分子生物学和合理的药物设计以及在语言串中寻找模式方面都有重要的应用。

This is an interinstitutional collaborative project. Combinatorial data consisting of sequences, trees, and graphs arise in many scientific disciplines. For example, the primary structure of proteins is a sequence, whereas the tertiary structure is a graph. Comparing such data to find similarities entails the use of a "distance metric" that mea sures the difference between two data items. Numerous distance metrics are possible. This work consists primarily of (i) inventing efficient ways to compute known distance metrics; (ii) developing a data structure to decide which of a set of data items is "closest" (according to a given distance metric) to a new data item; (iii) techniques and s oftware for discovering patterns with minimum or near-minimum distance to a given set of data items with respect to a given distance metric; and (iv) software to solve such discovery problems on networks of occasionally idle workstations. This work will help every field in which approximate matching is important. Significant applications are expe cted to molecular biology and rational drug design, as well as to finding patterns in linguistic strings.