POSITIONAL HASHING METHOD FOR PERFORMING DNA SEQUENCE SIMILARITY SEARCH

Positional Hashing, a novel method for detecting similarities between texts such as DNA sequences, amino acid sequences, and texts in natural language is disclosed. The method is particularly well suited for large-scale comparisons such as that of mutual comparisons of millions of sequence fragments that result from mammalian-scale sequencing projects and for whole-genome comparisons of multiple mammalian genomes. Positional Hashing is carried out by breaking the sequence comparison problem along its natural structure, solving the subproblems independently, and then collating the solutions into an overall result. The decomposition of the problem into subproblems enables parallelization, whereby a large number of nodes in a computer cluster or a computer farm are concurrently employed on solving the problem without incurring the quadratic time performance penalty characteristic of prior art. Positional Hashing may be used by itself or as a filtering step in conjunction with a variety of sequence comparison algorithms.