LEAPING SEARCH ALGORITHM FOR SIMILAR SUB-SEQUENCES IN CHARACTER SEQUENCES AND APPLICATION THEREOF IN SEARCHING IN BIOLOGICAL SEQUENCE DATABASE

摘要

Disclosed is a leaping search algorithm for similar sub-sequences in character sequences and an application thereof in searching in a biological sequence database. The algorithm comprises: S0, constructing an FMD index and a lookup table for a database; S1, fetching, from the lookup table, a bi-interval of a sub-sequence with k characters in query sequences; S2, sequentially finding matching areas on the left of the k seed by using a backward search algorithm; S3, applying a forward search algorithm to an interval that has not been shrinked in step S2, to find matching areas on the right of the k seed; S4, checking whether the current detecting position is the end of the query sequence or not, and if yes, the algorithm ends, otherwise, proceeding to step S5; and S5, leaping forward w-k+1 positions from the current detecting position, and repeating steps S2 to S5. The lookup table proposed in the present invention features small memory space and a high access efficiency. According to the present invention, by combining the lookup table and an FMD index, all w seeds can be found quickly. In addition, the present invention has been successfully applied to biological sequence alignment.