Fast and simple character classes and bounded gaps pattern matching, with applications to protein searching
Fast and simple character classes and bounded gaps pattern matching, with applications to protein searching
复制标题
DOI：
10.1089/106652703322756140
复制
发表时间：
2003-01-01
影响因子：
1.7
通讯作者：
Raffinot, M
中科院分区：
文献类型：
--
作者：
Navarro, G;Raffinot, M
快速精确和近似搜索文本中包含字符类别和有界大小间隙 (CBG) 的模式的问题具有广泛的应用，其中一个非常重要的应用是蛋白质模式匹配（例如，一个 PROSITE 蛋白质位点与 CBG [RK] - x(2, 3) - [DE] - x(2, 3) - Y 关联，其中括号匹配内部的任何字母，而 x(2, 3) 是长度在 2 和 2 之间的间隙。 3）。目前，在文本中搜索 CBG 的唯一方法是将其转换为完整的正则表达式 (RE)。然而，RE 比 CBG 更复杂，使用 RE 模式匹配算法搜索它会使搜索变得复杂并且速度变慢。这就是我们在本文中设计两种新的实用 CBG 匹配算法的原因，它们比所有 RE 搜索技术更简单、更快。第一个对每个文本字符只查看一次。第二个不需要考虑所有文本字符，因此它通常比第一个更快，但在糟糕的情况下可能必须多次读取相同的文本字符。然后，我们提出一个基于 CBG 形式的标准，以先验地选择两者之间最快的。我们还展示了如何在允许出现一些错误的情况下进行搜索。我们使用 PROSITE 数据库进行了许多实际实验，所有实验都表明我们的算法几乎在所有情况下都是最快的。
The problem of fast exact and approximate searching for a pattern that contains classes of characters and bounded size gaps (CBG) in a text has a wide range of applications, among which a very important one is protein pattern matching (for instance, one PROSITE protein site is associated with the CBG [RK] - x(2, 3) - [DE] - x(2, 3) - Y, where the brackets match any of the letters inside, and x(2, 3) a gap of length between 2 and 3). Currently, the only way to search for a CBG in a text is to convert it into a full regular expression (RE). However, a RE is more sophisticated than a CBG, and searching for it with a RE pattern matching algorithm complicates the search and makes it slow. This is the reason why we design in this article two new practical CBG matching algorithms that are much simpler and faster than all the RE search techniques. The first one looks exactly once at each text character. The second one does not need to consider all the text characters, and hence it is usually faster than the first one, but in bad cases may have to read the same text character more than once. We then propose a criterion based on the form of the CBG to choose a priori the fastest between both. We also show how to search permitting a few mistakes in the occurrences. We performed many practical experiments using the PROSITE database, and all of them show that our algorithms are the fastest in virtually all cases.