Efficient Pattern Matching Algorithms for DNA Sequences
Peyman Neamatollahi, Montassir Hadi, Mahmoud Naghibzadeh · 2020
The considerable growth of biological data motivates the researchers to solve the different problems in computational bioinformatics. Pattern matching is applied as an important operation in different phases of the computational pipelines. For instance, by pattern matching, the users are enabled to find the locations of particular DNA subsequences in a DNA sequence or biological database. In addition, some patterns of these expanding biological databases are updated over time. Quick pattern matching algorithms are required to perform faster searches. To speed up searches on large DNA sequences, this paper proposes two pattern matching algorithms. The proposed algorithms raise performance by finding the windows of the sequence via the first and last characters of the pattern and also by employing word-based processing instead of the characterbased processing presented in previous works. The experimental results reveal the superiority of the presented algorithms over the other simulated algorithms in terms of time cost.