Multiple Matching of Biological Patterns

Local alignment of DNA sequences is a common problem in biological computing, with many known solutions and popular implementations. Similarly, the general problem of multiple pattern matching is one of the basic problems in string algorithm research. In this thesis common local alignment tools are benchmarked against multiple pattern matching tools designed and implemented at Helsinki University of Technology. The considered problems are matching general DNA patterns obtained from mouse and human chromosomes against the mouse DNA, and the special case with SAGE tags, where the pattern set consists of sequences with the same prefix. Local alignment tools prove to be a competitive option for exact pattern matching with some restrictions. All matches are not guaranteed to be found, and some approximate matches are usually among the results, but they can be filtered from the output of most algorithms. In the end, specialised exact pattern matching tools are the best solution from a purely technical viewpoint, based on their performance and accuracy