Prefix Tree Indexing for Similarity Search and Similarity Joins on Genomic Data
Prefix Tree Indexing for Similarity Search and Similarity Joins on Genomic Data
复制标题
用于基因组数据相似性搜索和相似性连接的前缀树索引
DOI：
10.1007/978-3-642-13818-8_36
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
Hochmuth
中科院分区：
文献类型：
--
作者：
Rheinländer;Knobloch;Hochmuth
字符串的相似性搜索和相似性连接对于重复检测、错误检测、数据清理或生物序列比较等应用非常重要。特别是DNA测序产生大量的错误字符串，需要进行搜索，比较和合并。然而，目前的关系数据库管理系统提供的相似性操作，只有在一个非常有限的和低效的形式，不扩展到生命科学projects.PETER产生的数据量，我们提出了一个前缀树为基础的索引算法，支持近似搜索和近似连接。我们的工具支持汉明和编辑距离作为相似性度量，并可作为C++库，作为Unix命令行工具，并作为商业数据库的墨盒。它将压缩前缀树的有效实现与提前排除许多候选字符串的高级预过滤技术相结合。所实现的加速是戏剧性的，特别是对于字母表很小的DNA。我们评估我们的工具上的几个集合的长字符串包含多达5，000，000项的长度高达3，500。我们比较它的性能agrep，nrgrep，和用户定义的函数在关系数据库。我们的实验表明，与命令行工具相比，PETER的速度快了几个数量级。与RDBMS相比，它可以在几分钟内计算出UDF在一天内没有完成的相似连接，即使在确切的情况下，它也优于内置的连接方法。
Similarity search and similarity join on strings are important for applications such as duplicate detection, error detection, data cleansing, or comparison of biological sequences. Especially DNA sequencing produces large collections of erroneous strings which need to be searched, compared, and merged. However, current RDBMS offer similarity operations only in a very limited and inefficient form that does not scale to the amount of data produced in Life Science projects.We present PETER, a prefix tree based indexing algorithm supporting approximate search and approimate joins. Our tool supports Hamming and edit distance as similarity measure and is available as C++ library, as Unix command line tool, and as cartridge for a commercial database. It combines an efficient implementation of compressed prefix trees with advanced pre-filtering techniques that exclude many candidate strings early. The achieved speed-ups are dramatic, especially for DNA with its small alphabet. We evaluate our tool on several collections of long strings containing up to 5,000,000 entries of length up to 3,500. We compare its performance toagrep,nrgrep, and user-defined functions inside a relational database. Our experiments reveal that PETER is faster by orders of magnitudes compared to the command-line tools. Compared to RDBMS, it computes similarity joins in minutes for which UDFs did not finish within a day and outperforms the built-in join methods even in the exact case.
影响因子：
14.9
作者：
Altschul, SF;Madden, TL;Lipman, DJ
通讯作者：
Lipman, DJ
BFT：生物数据库中近似字符串连接的位过滤技术
DOI：
--
发表时间：
2003
期刊：
SPIRE
影响因子：
--
作者：
S. Aghili;D. Agrawal;A. El Abbadi
通讯作者：
A. El Abbadi