文章基本信息

标题：Efficient bit-parallel multi-patterns approximate string matching algorithms
本地全文：下载
作者：Rajesh Prasad ; Anuj Kumar Sharma ; Alok Singh 等
期刊名称：Scientific Research and Essays
印刷版ISSN：1992-2248
出版年度：2011
卷号：6
期号：4
页码：876-881
DOI：10.5897/SRE10.895
语种：English
出版社：Academic Journals
摘要：Multi-patterns approximate string matching (MASM) problem is to find all the occurrences of set of patterns P0, P1, P2...Pr-1, r≥1, in the given text T[0…n-1], allowing limited number of errors in the matches. This problem has many applications in computational biology viz. finding DNA subsequences after possible mutations, locating positions of a disease(s) in a genome etc. The MASM problem has been previously solved by Baeza-Yates and Navarro by extending the bit-parallel automata (BPA) of approximate matching and using the concept of classes of characters. The drawbacks of this approach are: (a) It requires verification for the potential matches and, (b) It can handle patterns of length less than or equal to word length (w) of computer used. In this paper, we propose two new bit-parallel algorithms to solve the same problem. These new algorithms requires no verification and can handle patterns of length > w. These two techniques also use the same BPA of approximate matching and concatenation to form a single pattern from the set of r patterns. We compare the performance of new algorithms with existing algorithms and found that our algorithms have better running time than the previous algorithms.
关键词：Algorithm; finite automata; bit-parallelism; approximate matching; multiple patterns