Improved Pattern Matching to Find DNA Patterns
László Dudás · 2006
The process of finding given patterns in DNA sequences is widely used in modern biological sciences. This paper shows an algorithmic improvement for exact pattern matching introducing a new heuristic. For implementation the author created an application that uses three well-known heuristics to ensure the O(n) worst case time, the O(n logsigma(m)/m) average case time and the O(n/m) best case time of searching for an m length pattern in an n length text that use a sigma letter alphabet. This application served as a testbed for the new H4 heuristic. The novelty is in optimization of the direction of text window movement in the preprocessing phase. The idea takes advantages of RAM based searching: usually all the text resides in today's gigabyte memory so the opposite direction of searching window moving requires the same time as the usual. A new function predicts the better moving direction in preprocessing time, based on the unsymmetrical property of pattern. Tests proved that this heuristic may result in fewer jumps and tested characters in the search phase of pattern matching