Pattern Discovery for Combinatorial Databases

组合数据库的模式发现

• 批准号: 7049734
• 负责人: BRUCE A. SHAPIRO
• 金额: --
• 依托单位: DIVISION OF BASIC SCIENCES - NCI
• 依托单位国家: 美国
• 资助国家: 美国
• 起止时间: 至
• 项目状态: 未结题
• 来源: https://reporter.nih.gov/project-details/7049734
• 关键词: RNA; classification; computer data analysis; computer graphics /printing; computer program /software; conformation; information retrieval; molecular biology information system; nucleic acid structure; protein sequence; structural biology; RNA; classification; computer data analysis; computer graphics /printing; computer program /software; conformation; information retrieval; molecular biology information system; nucleic acid structure; protein sequence; structural biology

This work involves a form of datamining, including the determination of motifs that may exist in a database of objects and the fast determination of distances between objects which may be used for clustering and data visualization. This becomes more significant when one has minimal information concerning the motifs. Ultimately, one would like to determine whether or not the set of motifs and the clusters discovered can act as good classifiers. The data objects dealt with may consist of sequences, trees, graphs or records. Examples of the use of these methods include: 1) the determination of 3D motifs in bio-molecules. The motifs that the algorithms find are rigid substructures which may occur in a graph after allowing for an arbitrary number of rotations and translations as well as a small number of node insert/delete operations in the motifs or graphs. By combining a geometric hashing" technique and "block detection" algorithms for undirected graphs we are able to find motifs approximately in a set of graphs; 2) the determination of the largest approximately common substructures of two trees based on an edit distance metric. Using a method known as "selective memorization", the algorithm was used to discover motifs in multiple RNA secondary structures which can be represented as trees; 3) sequence data, as mentioned above, can also be used for pattern discovery. Protein sequences were classified with a 98% precision rate; 4) more recently, a new index structure has been developed that takes a set of objects and a distance metric and then maps those objects into a k-dimensional space in such a way that the distances are approximately preserved. This index structure is a useful tool for clustering and visualization in data-intensive applications. Thus clustering of large databases can be made practical as for example in the clustering RNA conformations.

这项工作涉及一种数据设计形式，包括确定对象数据库中可能存在的基序以及可以用于聚类和数据可视化的对象之间的距离的快速确定。当人们对主题的信息最少时，这将变得更加重要。最终，人们想确定图案集和发现的集群是否可以充当良好的分类器。处理的数据对象可能包括序列，树，图形或记录。 使用这些方法的示例包括：1）在生物分子中测定3D基序。算法发现的主题是刚性子结构，在允许任意数量的旋转和翻译以及少数节点插入/DELETE操作中，它们可能会在图形或图形中发生。通过将几何散列“技术和“块检测”算法相结合，我们能够在一组图中查找大约在图中找到图案； 2）确定基于编辑距离的两棵树的最大共同子结构的确定，基于一个编辑距离的公制。使用一个被称为“选择性记忆”的方法，该方法是“选择性记忆”，以“ algoriths”的构建方式，该序列是构造的三个序列。如上所述，还可以将蛋白质序列分类为98％的精度；例如，在聚类RNA构象中进行实用。