USE THE EDIT DISTANCE IN THE ND-TREE FOR EFFICIENT BIOINFORMATICS QUERIES

这个子项目是许多研究子项目中的一个 由NIH/NCRR资助的中心赠款提供的资源。子项目及 研究者（PI）可能从另一个NIH来源获得了主要资金， 因此可以在其他CRISP条目中表示。所列机构为 研究中心，而研究中心不一定是研究者所在的机构。 随着生物数据量的快速增长，基于索引的数据搜索方法变得比基于顺序扫描的方法更有利。该子项目研究了ND树的应用，ND树是一种多维结构，专门用于索引具有生物信息学数据典型的离散和无序组件的子串/q-gram，用于生物信息学查询。 这个子项目的目的是扩展ND树，以支持编辑距离，一个广泛使用的相似性度量同源区域查询。 该扩展的目标是提高生物信息学数据库查询过滤阶段的灵敏度。 为了结合编辑距离，它采用额外的插入和删除操作比汉明距离，ND树必须支持有效的相似性查询具有相对较大的搜索范围。在这个项目的第一阶段，我们将设计和评估新的算法，有效地处理查询ND树中相对较大的搜索范围。 我们计划研究基于近似的技术，可以通过修剪大量不太有前途的索引分支来提高查询性能。 在第二阶段，将开发基于编辑距离的查询算法。 为了进一步提高性能，ND树的构造和批量加载算法也将被检查和调整，以便索引中的数据组织变得更适合于编辑距离查询。 为了评估新算法的有效性，我们将实验比较它们与现有的算法。 该项目将导致一个新的生物信息学搜索引擎的设计基于ND树。

This subproject is one of many research subprojects utilizing the resources provided by a Center grant funded by NIH/NCRR. The subproject and investigator (PI) may have received primary funding from another NIH source, and thus could be represented in other CRISP entries. The institution listed is for the Center, which is not necessarily the institution for the investigator. As the volume of biological data increases rapidly, index-based approaches to searching the data becomes more favorable than sequential-scan-based approaches. This subproject investigates the application of the ND-tree, a multidimensional structure specifically designed to index substrings/q-grams with discrete and non-ordered components typical of bioinformatics data, to bioinformatics queries. The aim of this subproject is to extend the ND-tree to support the edit distance, a widely-used similarity measure for homologous region queries. The goal of the extension is to enhance the sensitivity in the filtering stage of a bioinformatics database query. To incorporate the edit distance which employs the extra insertion and deletion operations than the Hamming distance, the ND-tree must support efficient similarity queries with a relatively large search range. In the first phase of this project, we will design and evaluate novel algorithms that efficiently process queries with relatively large search ranges in the ND-tree. We plan to investigate approximation-based techniques that can improve query performance by pruning a large amount of less-promising index branches. In the second phase, a query algorithm based on the edit distance will be developed. To further enhance the performance, the construction and bulk-loading algorithms of the ND-tree will also be examined and adapted so that the data organization within the index becomes more suitable for edit distance queries. To evaluate the effectiveness of the new algorithms, we will experimentally compare them with existing algorithms. The project will lead to the design of a novel bioinformatics search engine based on the ND-tree.