BFT: Bit Filtration Technique for Approximate String Join in Biological Databases
BFT: Bit Filtration Technique for Approximate String Join in Biological Databases
复制标题
BFT：生物数据库中近似字符串连接的位过滤技术
DOI：
--
复制
发表时间：
2003
期刊：
影响因子：
--
通讯作者：
A. El Abbadi
中科院分区：
文献类型：
--
作者：
S. Aghili;D. Agrawal;A. El Abbadi
在过去的十年中，在关系数据库中联接大量的表受到了极大的关注。已经提出了许多过滤和索引技术来减少维度灾难。本文提出了一种新的方法，在良好的关系数据库环境下，将成对全基因组比较问题映射为近似连接操作。提出了一种新的基于矢量变换的比特过滤技术(BFT)，并将DFT(离散傅立叶变换)和DWT(离散小波变换，Haar)降维技术应用于BFT(离散傅立叶变换)和DWT(离散小波变换，Haar)降维处理，有效地减少了连接操作的搜索空间和运行时间。我们在一些原核生物和真核生物DNA重叠群数据集上的经验结果表明，非常有效的过滤可以有效地修剪数据库的不相关部分，不会导致假阴性，与传统的动态规划和Q-gram方法相比，运行时间最多快50倍。BFT可以很容易地合并为任何众所周知的序列搜索启发式算法的前处理步骤，如BLAST、QUASAR和FASTA，以便进行成对的全基因组比较。我们分析了应用BFT和其他基于变换的降维技术的精度，最后讨论了强加的权衡。
Joining massive tables in relational databases have received substantial attention in the past decade. Numerous filtration and indexing techniques have been proposed to reduce the curse of dimensionality. This paper proposes a novel approach to map the problem of pairwise whole-genome comparison into an approximate join operation in the well-established relational database context. We propose a novel Bit Filtration Technique (BFT) based on vector transformation and furthermore conduct the application of DFT(Discrete Fourier Transformation) and DWT(Discrete Wavelet Transformation, Haar) dimensionality reduction techniques as a pre-processing filtration step which effectively reduces the search space and running time of the join operation. Our empirical results on a number of Prokaryote and Eukaryote DNA contig datasets demonstrate very efficient filtration to effectively prune non-relevant portions of the database, incurring no false negatives, with up to 50 times faster running time compared with traditional dynamic programming, and q-gram approaches. BFT may easily be incorporated as a pre-processing step for any of the well-known sequence search heuristics as BLAST, QUASAR and FastA, for the purpose of pairwise whole-genome comparison. We analyze the precision of applying BFT and other transformation-based dimensionality reduction techniques, and finally discuss the imposed trade-offs.