The rapid increase in the size of biological sequence data owing to the advancements in high-throughput sequencing techniques, and the increased complexity of hypothesis-driven exploration of this data requiring massive number of similarity queries call for new approaches for managing sequence databases and analysis of this information. The metric space representation for sequences is suitable for similarity search and provides several sophisticated metric-indexing techniques. In this work, we provide a thorough survey and analysis of the application of metric access methods to similarity search in protein sequence databases. A framework supporting application of different metric space indexing methods is developed and a non-redundant sequence database is used to benchmark different methods in terms of number of distance-computations incurred and the computation time required during database compilation and query phases. The parameters of each method are optimized on a subset of experimental conditions. We demonstrate that Onion-Tree, a hybrid metric access method, performs the best in both index building and querying phases for the protein database investigated, and scales well for large databases, incurring distance computations with 0.5% of the database sequences per query.