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

这是一个跨机构合作项目。由序列、树和图组成的组合数据出现在许多科学学科中。例如，蛋白质的一级结构是一个序列，而三级结构是一个图。比较这些数据以发现相似性需要使用“距离度量”，即测量两个数据项之间的差异。许多距离度量是可能的。这项工作主要包括(i)发明计算已知距离度量的有效方法；（ii）发展一种数据结构，以决定在一组数据项中，哪一项与新数据项“最接近”（按给定的距离量度）；（iii）在给定的距离度量中，发现与一组给定数据项的距离最小或接近最小的模式的技术和软件；以及（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.