Block Sorting Index-based Techniques for Local Alignment Searches on Biological Sequences
Li Yong · 2005
A common query against large protein and gene sequence data sets is to locate targets that are similar to an input query sequence.The current set popular search tools,such as BLAST,employ heuristics to improve the speed of such searches.However,such heuristics can sometimes miss targets,which in many cases is undesirable.The alterna- tive to BLAST is to use an accurate algorithm,Such as Smith-Waterman(S-W) algorithm.However,these accurate al- gorithms are computationaUy very expensive.Recently,a new technique,OASIS,has been proposed to improve the ef- ficiency and accuracy by employing dynamical programming during traversing suffix tree and its speed is comparable to BLAST.But its main drawback is too much memory consuming.We propose an efficient and accurate algorithm for lo- cally aligning genome sequences.We construct a block sorting index structure for the large sequence.The index struc- ture is less than the suffix tree index and can be fit for large data size.Experimental results show that our algorithm has better performance than OASIS.