The article discusses the development and implementation of an accelerated profile hidden Markov model (HMM) search method, the "multiple segment Viterbi" (MSV) algorithm, and a method called "sparse rescaling" to speed up the standard profile HMM Forward/Backward algorithms. The MSV algorithm calculates optimal sums of multiple ungapped local alignment segments using a striped vector-parallel approach, allowing for rapid evaluation of significance and facilitating its use as a heuristic filter. The sparse rescaling method is used to accelerate the Forward/Backward algorithms, making them about 16 times faster than standard serial implementations. These methods are integrated into the HMMER3 software package, which is significantly more sensitive and 100 to 1000 times faster than the previous version, HMMER2, and is now comparable in speed to BLAST for protein searches. The article also includes a detailed technical analysis of the numerical precision and statistical properties of the MSV scores, as well as the implementation details of the sparse rescaling method.The article discusses the development and implementation of an accelerated profile hidden Markov model (HMM) search method, the "multiple segment Viterbi" (MSV) algorithm, and a method called "sparse rescaling" to speed up the standard profile HMM Forward/Backward algorithms. The MSV algorithm calculates optimal sums of multiple ungapped local alignment segments using a striped vector-parallel approach, allowing for rapid evaluation of significance and facilitating its use as a heuristic filter. The sparse rescaling method is used to accelerate the Forward/Backward algorithms, making them about 16 times faster than standard serial implementations. These methods are integrated into the HMMER3 software package, which is significantly more sensitive and 100 to 1000 times faster than the previous version, HMMER2, and is now comparable in speed to BLAST for protein searches. The article also includes a detailed technical analysis of the numerical precision and statistical properties of the MSV scores, as well as the implementation details of the sparse rescaling method.