MULTIPLE FILTRATION AND APPROXIMATE PATTERN-MATCHING
MULTIPLE FILTRATION AND APPROXIMATE PATTERN-MATCHING
复制标题
DOI：
10.1007/bf01188584
复制
发表时间：
1995-01-01
期刊：
影响因子：
1.1
通讯作者：
WATERMAN, MS
中科院分区：
文献类型：
--
作者：
PEVZNER, PA;WATERMAN, MS
给定长度为n和长度Q查询的文本，我们提出了一种算法，用于查找文本中M-Tuplace的所有位置以及大多数K不匹配的查询中的所有位置。该问题是由序列比较的点矩阵构建体激励的，并且通常用于分子生物学中的最佳寡核苷酸探针选择。在情况下，q = m问题与经典的近似字符串与K不匹配问题匹配。我们基于多个哈希介绍了一种新的方法来解决此问题，这可能比提出的一些复杂且理论上有效的方法具有优势。本文描述了一个两个阶段的过程。第一阶段（多重过滤）使用一种新技术来预选大致相似的M-Tuplace。第二阶段使用准确的方法比较了这些企业。与其他技术相比，我们证明了多种过滤的优势，以进行近似模式匹配。
Given a text of length n and a query of length q, we present an algorithm for finding all locations of m-tuples in the text and in the query that differ by at most k mismatches. This problem is motivated by the dot-matrix constructions for sequence comparison and optimal oligonucleotide probe selection routinely used in molecular biology. In the case q = m the problem coincides with the classical approximate string matching with k mismatches problem. We present a new approach to this problem based on multiple hashing, which may have advantages over some sophisticated and theoretically efficient methods that have been proposed. This paper describes a two-stage process. The first stage (multiple filtration) uses a new technique to preselect roughly similar m-tuples. The second stage compares these In-tuples using an accurate method. We demonstrate the advantages of multiple filtration in comparison with other techniques for approximate pattern matching.