A fast and sensitive new biological sequence alignment and database search method has been invented specifically to exploit the advantages of the SIMD technology high sensitivity was reached by a combination of two main factors. First, the computation of the exact optimal un-gapped alignment score of each diagonal in the alignment was performed. Secondly, a novel heuristic for estimating a gapped alignment score taking into account the amount of sequence similarity on several diagonals in the alignment matrix was employed. This estimate is used to identify a 1% fraction of the most interesting database sequences that are subsequently aligned with the query sequence by the Smith-Waterman method. The rapidity of the method was achieved using a very efficient computation of the ungapped alignment scores of all diagonals. The heuristic for computing the estimated gapped alignment score is also fast.
展开▼