Multi-patterns parameterised matching with application to computational biology
Swati Tevatia, Rajesh Prasad · International Journal of Information and Communication Technology · 2015
In the multi-pattern parameterised string matching problem, we are given a text T and pattern set P = {p1, p2, , pn{. The pattern pi, 1 ≤ i ≤ n, matches a substring t of the text T, if characters of the pattern pi can be transformed into the characters of the substring t with some bijective mapping. This problem has important application in computational biology, where two trends of DNA can be matched with some one-to-one mapping even they are not exactly same. In 2008, Salmela and Tarhio developed a fast parameterised Boyer-Moore-Horspool with hash algorithm, but it is unable to handle multiple patterns simultaneously. In this paper, we extend this algorithm for simultaneously searching the presence of more than one pattern in a large DNA text. Experimental results show that our algorithm is very fast in practice.