A FAST SEARCH METHOD FOR DNA SEQUENCE DATABASE USING HISTOGRAM INFORMATION

DNA sequence search is a fundamental topic in bioinformatics. The Smith-Waterman algorithmachieved highest accuracy among various sequence alignment tools, but it usually spends much computationaltime to search on large DNA sequence database. On the contrary, BLAST and FASTA have improved the searchspeed by using heuristic approaches, by there is a possibility of missing an alignment or giving inaccurate output.This paper presents an efficient hierarchical method to improve the search speed while the accurate is being keptconstant. For a given query sequence, firstly, a fast histogram based method is used to scan the sequences in thedatabase. A large number of DNA sequences with low similarity will be excluded for latter searching. The Smith-Waterman algorithm is then applied to each remainder sequences. Experimental results show the proposedmethod combining histogram information and Smith-Waterman algorithm is a more efficient algorithm for DNAsequence search