A fast word search algorithm for the representation of sequence similarity in genomic DNA

Open Access
Publisher Website
Google Scholar
Abstract
Representation of sequence similarity by dot matrix plots is a method widely used for comparing biological sequences. The user Is presented with an overall view of similarity between two sequences. Computation of this plot has been reconsidered here. An improvement Is proposed through the preprocessing of the data into an automaton recognizing the word structure of a sequence. The main advantage of this approach is to systematically eliminate the repetitions during word comparison. Simple heuristics are also considered to greatly speed up pattern matching. As a result, large sequences are handled very efficiently. This is illustrated by a comparison of large genomic DNA. The algorithm has been implemented in an interactive application on a microcomputer.