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.