Rapid analysis of DNA sequences is important in preventing the evolution of different viruses and bacteria during an early phase, early diagnosis of genetic predispositions to certain diseases (cancer, cardiovascular diseases), and in DNA forensics. However, real-world DNA sequences may comprise several Gigabytes and the process of DNA analysis demands adequate computational resources to be completed within a reasonable time. In this paper we present a scalable approach for parallel DNA analysis that is based on Finite Automata, and which is suitable for analyzing very large DNA segments. We evaluate our approach for real-world DNA segments of mouse (2.7GB), cat (2.4GB), dog (2.4GB), chicken (1GB), human (3.2GB) and turkey (0.2GB). Experimental results on a dual-socket shared-memory system with 24 physical cores show speed-ups of up to 17.6x. Our approach is up to 3x faster than a pattern-based parallel approach that uses the RE2 library.
presented in @cite_3 an implementation of the Aho-Corasick string matching algorithm using POSIX threads, which is based on the pattern partitioning approach. A replication of the Herath's study with the intention to improve the software implementation of the Aho-Corasick algorithm was conducted by @cite_26 .
@cite_26 @cite_3
2049650913 2011905634 2107670443 2046801051
The Aho-Corasick (AC) algorithm is a very flexible and efficient but memory-hungry pattern matching algorithm that can scan the existence of a query string among multiple test strings looking at each character exactly once, making it one of the main options for software-base intrusion detection systems such as SNORT. We present the Split-AC algorithm, which is a reconfigurable variation of the AC algorithm that exploits domain-specific characteristics of intrusion detection to reduce considerably the FSM memory requirements. SplitAC achieves an overall reduction between 28-75 compared to the best proposed implementation. Pattern matching has been one of the major operations in modern bioengineering especially in Bioinformatics. Prior work on this area have focus on either pursuing mathematically efficient matching algorithms or hardwired approach. As multicore processor are becoming mainstream, developers need to determine how to take advantage of multicore technology for pattern matching. In this paper, we propose a methodology to evaluate pattern search algorithms for DNA on Multiprocessor. Our evaluation methodology is an automatic simulation framework. Starting from a uniprocessor profiling, the framework constructs task graphs for string matching algorithms. Then task graphs are mapped onto multiprocessor. The system's performance is determined by the analytical performance model. With this framework, we can evaluate the performance of different algorithms on multiprocessor. Our case studies show that finite automaton based (Aho-Corasick) is more efficient than shift table based algorithms (SFKSearch and Wu-Manber) on uniprocessor, however, Wu-Manber is 3 times efficient than Aho-Corasick on multiprocessor due to its inherent parallelism. Multiple string matching is known as locating all the occurrences of a given number of patterns in an arbitrary string. It is used in bio-computing applications where the algorithms are commonly used for retrieval of information such as sequence analysis and gene protein identification. Extremely large amount of data in the form of strings has to be processed in such bio-computing applications. Therefore, improving the performance of multiple string matching algorithms is always desirable. Multicore architectures are capable of providing better performance by parallelizing the multiple string matching algorithms. The Aho-Corasick algorithm is the one that is commonly used in exact multiple string matching algorithms. The focus of this paper is the acceleration of Aho-Corasick algorithm through a multicore CPU based software implementation. Through our implementation and evaluation of results, we prove that our method performs better compared to the state of the art. Current text pattern-matching tools are based on regular expressions. However, pure regular expressions have proven too weak a formalism for the task: many interesting patterns either are difficult to describe or cannot be described by regular expressions. Moreover, the inherent non-determinism of regular expressions does not fit the need to capture specific parts of a match. Motivated by these reasons, most scripting languages nowadays use pattern-matching tools that extend the original regular-expression formalism with a set of ad hoc features, such as greedy repetitions, lazy repetitions, possessive repetitions, ‘longest-match rule,’ lookahead, etc. These ad hoc extensions bring their own set of problems, such as lack of a formal foundation and complex implementations. In this paper, we propose the use of Parsing Expression Grammars (PEGs) as a basis for pattern matching. Following this proposal, we present LPEG, a pattern-matching tool based on PEGs for the Lua scripting language. LPEG unifies the ease of use of pattern-matching tools with the full expressive power of PEGs. Because of this expressive power, it can avoid the myriad of ad hoc constructions present in several current pattern-matching tools. We also present a Parsing Machine that allows a small and efficient implementation of PEGs for pattern matching. Copyright © 2008 John Wiley & Sons, Ltd.