Cache-Oblivious parallel SIMD Viterbi decoding for sequence search in HMMER

BMC Bioinformatics

Miguel Ferreira¹  Nuno Roma¹  Luis MS Russo¹ 

[1] INESC-ID, Rua Alves Redol, 9, 1000-029 Lisboa, Portugal

关键词: Streaming SIMD Extensions (SSE);    Parallelization;    HMMER;    Viterbi;    Hidden Markov model;    Sequences alignment;   

Others  :  1087569
DOI  :  10.1186/1471-2105-15-165

 received in 2013-10-22, accepted in 2014-04-04,  发布年份 2014

【 摘 要 】

Background

HMMER is a commonly used bioinformatics tool based on Hidden Markov Models (HMMs) to analyze and process biological sequences. One of its main homology engines is based on the Viterbi decoding algorithm, which was already highly parallelized and optimized using Farrar’s striped processing pattern with Intel SSE2 instruction set extension.

Results

A new SIMD vectorization of the Viterbi decoding algorithm is proposed, based on an SSE2 inter-task parallelization approach similar to the DNA alignment algorithm proposed by Rognes. Besides this alternative vectorization scheme, the proposed implementation also introduces a new partitioning of the Markov model that allows a significantly more efficient exploitation of the cache locality. Such optimization, together with an improved loading of the emission scores, allows the achievement of a constant processing throughput, regardless of the innermost-cache size and of the dimension of the considered model.

Conclusions

The proposed optimized vectorization of the Viterbi decoding algorithm was extensively evaluated and compared with the HMMER3 decoder to process DNA and protein datasets, proving to be a rather competitive alternative implementation. Being always faster than the already highly optimized ViterbiFilter implementation of HMMER3, the proposed Cache-Oblivious Parallel SIMD Viterbi (COPS) implementation provides a constant throughput and offers a processing speedup as high as two times faster, depending on the model’s size.

【 授权许可】

   
2014 Ferreira et al.; licensee BioMed Central Ltd.

【 图 表 】

Figure 1.

Figure 2.

Figure 3.

Figure 4.

Figure 5.

Figure 6.

Figure 7.

Figure 8.

Figure 9.

Figure 10.

Figure 11.

Figure 12.

【 参考文献 】

• [1]Smith TF, Waterman MS: Identification of common molecular subsequences. J Mol Biol 1981, 147:195-197.
• [2]Altschul S, Gish W, Miller W, Myers E, Lipman D: Basic local alignment search tool. J Mol Biol 1990, 215(3):403-410.
• [3]Farrar M: Striped Smith-Waterman speeds database searches six times over other SIMD implementations. Bioinformatics 2007, 23(2):156-161.
• [4]Rognes T: Faster Smith-Waterman database searches with inter-sequence SIMD parallelisation. BMC Bioinformatics 2011, 12:221. BioMed Central Full Text
• [5]Ganesan N, Chamberlain RD, Buhler J, Taufer M: Accelerating HMMER on GPUs by implementing hybrid data and task parallelism. In Proceedings of the First ACM International Conference on Bioinformatics and Computational Biology. New York: ACM; 2010:418-421.
• [6]Derrien S, Quinton P: Hardware acceleration of HMMER on FPGAs. Sci J Circ Syst Signal Process 2010, 58:53-67.
• [7]Karplus K, Barrett C, Hughey R: Hidden Markov models for detecting remote protein homologies. Bioinformatics 1998, 14(10):846-856.
• [8]Krogh A, Brown M, Mian IS, Sjolander K, Haussler D: Hidden Markov models in computational biology: Applications to protein modeling. J Mol Biol 1994, 235(5):1501-1531.
• [9]Eddy SR: Profile Hidden Markov models. Bioinformatics 1998, 14(9):755-763.
• [10]Eddy SR: Accelerated profile HMM searches. PLoS Comput Biol 2011, 7(10):e1002195.
• [11]Wheeler TJ, Clements J, Eddy SR, Hubley R, Jones TA, Jurka J, Smit AF, Finn RD: Dfam: a database of repetitive DNA based on profile hidden Markov models. Nucleic Acids Res 2013, 41(D1):D70-D82.
• [12]Bateman A, Coin L, Durbin R, Finn RD, Hollich V, Jones SG, Khanna A, Marshall M, Moxon S, Sonnhammer ELL, Studholme DJ, Yeats C, Eddy SR: The Pfam protein families database. Nucleic Acids Res 2004, 32(suppl 1):D138-D141.
• [13]Holm L, Sander C: Removing near-neighbour redundancy from large protein sequence collections. Bioinformatics 1998, 14(5):423-429.
• [14]Browne S, Dongarra J, Garner N, Ho G, Mucci P: A portable programming interface for performance evaluation on modern processors. Int J High Perform Comput Appl 2000, 14(3):189-204.