For predicting subcellular localization of proteins, many methods exploit information of proteins having high sequence similarity to a query sequence. This paper proposes a fast sequence search method to find these highly similar proteins in database. For protein database search, we adopt enhanced suffix arrays which are used for finding the position of query DNA sequences in genome database. We use top-down traversal and reuse of previously searched results of enhanced suffix arrays for fast search. The time complexity for searching candidate proteins having many exact matches to the sub-sequences of a query protein is proportional only to the length of the query sequence, not dependent on database size. Smith-Waterman algorithm is applied to find the most similar protein in these candidate proteins. Comparing with most widely used search method BLAST, the proposed method shows 300 times faster search speed and gives higher prediction accuracies in protein subcellular localization prediction.