Genome sequence search is useful, for example, in clinical applications where a care provider needs to select a treatment option for a patient based on the exact kind of cancer the patient might have. Homomorphic encryption is a desirable technology to be used for this application because it is non-interactive. However, privacy-preserving genome sequence search using homomorphic encryption has been a practical challenge because of scalability issues driven by the depth of computations that need to be supported for privacy-preserving genome sequence search. In this paper, we build off of earlier privacy-preserving genome sequence search results to design, implement and compare two approaches to a client-server style system for privacy-preserving genome sequence search. There is a myriad of options and design trade-offs associated with the application of homomorphic encryption in this domain driven, for example, by choices in data encoding, scheme selection, and even encryption software library. We particularly focus on the use of the BGV and BFV homomorphic encryption schemes provided by the HElib and PALISADE open-source homomorphic encryption software libraries. Our results show that using the BFV-based approach in PALISADE provides optimal results for this application over our sample data.