Fast and simple character classes and bounded gaps pattern matching, with application to protein searching
Fast and simple character classes and bounded gaps pattern matching, with application to protein searching
复制标题
快速、简单的字符类和有界间隙模式匹配，应用于蛋白质搜索
DOI：
10.1145/369133.369220
复制
发表时间：
2001
期刊：
影响因子：
--
通讯作者：
M. Raffinot
中科院分区：
文献类型：
--
作者：
G. Navarro;M. Raffinot
在文本中快速搜索包含字符类和有界长度间隔（CBG）的模式有着广泛的应用，其中一个重要的应用就是蛋白质模式匹配（例如，一个PROSITE蛋白位点与CBG [RK] - x（2，3）- [DE] - x（2，3）- Y相关，其中括号与内部的任何字母匹配，以及x（2，3）长度在2和3之间的间隙）。目前，在文本中搜索CBG的唯一方法是将其转换为完整的正则表达式（RE）。然而，RE比CBG更复杂，并且用RE模式匹配算法搜索它使搜索复杂化并且使其变慢。这就是为什么我们在这篇文章中设计了两个新的实用CBG匹配算法，比所有的RE搜索技术更简单，更快。第一个方法对每个文本字符只查找一次。第二个不需要考虑所有的文本字符，因此它通常比第一个更快，但在坏的情况下可能需要多次读取相同的文本字符。然后，我们提出了一个标准的基础上的形式的CBG选择先验两者之间最快的。我们使用PROSITE数据库进行了许多实际实验，所有这些实验表明，我们的算法在几乎所有情况下都是最快的。
The problem of fast searching of 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 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 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 performed many practical experiments using the PROSITE database, and all them show that our algorithms are the fastest in virtually all cases.
影响因子：
14.9
作者：
Hofmann, K;Bucher, P;Bairoch, A
通讯作者：
Bairoch, A