Method and system for faster and more sensitive homology searching

Abstract

An area of research in the field of bioinformatics deals with the identification of similarities within one, or between two DNA sequences. Current techniques are quite slow and many matches are missed. The invention provides a faster and more sensitive solution, by using “optimised spaced seeds” to perform these biological sequence homology searches. Various techniques are shown for identifying seeds which are optimized to improve the sensitivity or speed of the searching. In the preferred embodiment, optimized spaced seeds are determined by the parameters of the search and independent of the actual databases being searched (for example, using the length and weight of the spaced seed, as well as the probability of a hit in a similar region). Thus, these optimized seeds can be stored in libraries which are accessed as required.

What is claimed is:  
     
         1 . A method of performing biological sequence homology searches comprising the steps of: 
 generating one or more optimized spaced seeds, by identifying optimized spaced seeds with a high likelihood of having hits in similar regions; and    performing a Blast-type search using said one or more optimized spaced seeds; thereby improving speed and sensitivity of said homology search.    
     
     
         2 . The method of  claim 1  where said step of generating comprises the steps of: 
 randomly generating a plurality of proposed test seeds;  
 for each of said plurality of proposed test seeds, calculating the likelihood that said each of said proposed test seeds will have hits in a random pair of similar regions; and  
 identifying the proposed test seed or seeds with the highest likelihood of having hits, said identified seed or seeds being defined as said one or more optimized spaced seeds.  
 
     
     
         3 . The method of  claim 1  where said step of generating comprises the step of identifying an optimized spaced seed with a high likelihood of having hits in a random pair of similar regions.  
     
     
         4 . The method of  claim 3  where said step of generating comprises the steps of: 
 generating all possible test seeds of a given weight and length;  
 for each of said test seeds, calculating the likelihood that said each of said test seeds will have hits in a random pair of similar regions; and  
 identifying the test seed or seeds with the highest likelihood of having hits, said identified seed or seeds being defined as said one or more optimized spaced seeds.  
 
     
     
         5 . The method of  claim 3  where said optimized spaced seed is optimized to increase the sensitivity of the homology search.  
     
     
         6 . The method of  claim 3  where said optimized spaced seed is approximately optimized to increase the sensitivity of the homology search.  
     
     
         7 . The method of  claim 3  where said optimized spaced seed is optimized to increase the speed of the homology search.  
     
     
         8 . The method of  claim 3  where said optimized spaced seed is approximately optimized to increase the speed of the homology search.  
     
     
         9 . The method of  claim 1  where said sequences comprise DNA sequences.  
     
     
         10 . The method of  claim 1  where said sequences comprise amino acid sequences.  
     
     
         11 . The method of  claim 1  further comprising the step of: 
 performing multiple-hit extensions, in combination with a spaced model, to increase speed while keeping relatively high sensitivity in homology search.  
 
     
     
         12 . The method of  claim 11  further comprising the step of: 
 triggering extension not only on multiple hits on the same diagonal, but also on multiple hits on nearby diagonals.  
 
     
     
         13 . The method of  claim 12  wherein said step of performing comprises the step of: 
 indexing a banded hit table to efficiently find multiple hits on nearby diagonals.  
 
     
     
         14 . The method of  claim 1  wherein said step of performing comprises the step of: 
 extending across gaps using local hit generation with a small-weight spaced model and multiple-hit extension.  
 
     
     
         15 . The method of  claim 14 , using a spaced seed model of weight 3, with 3 hits triggering an extension.  
     
     
         16 . The method of  claim 1  wherein dynamic programming is used at the level of HSPs to compute the best alignment ending at any HSP.  
     
     
         17 . The method of  claim 1  further comprising the step of: 
 storing recently found HSPs in an ordered data structure.  
 
     
     
         18 . The method of  claim 17  further comprising the step of: 
 storing recently found HSPs in an ordered tree data structure sorted by diagonal, allowing for fast lookup of nearby HSPs.  
 
     
     
         19 . The method of  claim 18  further comprising the step of: 
 removing HSPs from the ordered tree data structure when their ending position is more than some threshold away from the current seeding position.  
 
     
     
         20 . The method of  claim 1  wherein said step of performing comprises the step of: 
 using k non-consecutive characters as a seed and then extending the match.  
 
     
     
         21 . The method of  claim 1  wherein said “Blast-type” program comprises one using the strategy of finding short seed matches which are then extended.  
     
     
         22 . The method of  claim 1  employing a scoring scheme as follows: reward a match with 1, penalize a mismatch with −1, open gap −5, and gap extension −1.  
     
     
         23 . The method of  claim 1  further comprising the step of computing the probability that a spaced seed model hits a random pair of similar sequences using dynamic programming.  
     
     
         24 . The method of  claim 18  wherein said step of generating comprises the step of: 
 extending hits of a spaced seed only if multiple hits occur close together on the nearby diagonals.  
 
     
     
         25 . A system for performing biological sequence homology searches comprising: 
 a computer operable to: 
 generate one or more optimized spaced seeds, by identifying optimized spaced seeds with a high likelihood of having hits in similar regions; and  
 performing a Blast-type search using said one or more optimized spaced seeds;  
   thereby improving speed and sensitivity of said homology search.    
     
     
         26 . A memory medium storing software code executable to perform biological sequence homology searches, said software code being executable to perform the steps of: generating one or more optimized spaced seeds, by identifying optimized spaced seeds with a high likelihood of having hits in similar regions; and  
       performing a Blast-type search using said one or more optimized spaced seeds; thereby improving speed and sensitivity of said homology search.