An Efficient Hardware Implementation of Smith-Waterman Algorithm Based on the Incremental Approach

• Autorzy: Pułka A. , Milik A.
• Języki publikacji: EN

Abstrakty

EN

The paper presents optimized hardware structure applied to genome alignment search. The proposed methodology is based on dynamic programming. The authors show how starting from the original Smith-Waterman approach, the algorithm can be optimized and the evaluation process simplified and speeded-up. The main idea is based on the observations of growth trends in the adjacent cells of the systolic array, which leads to the incremental approach. Moreover various coding styles are discussed and the best technique allowing further reduction of resources is selected. The entire processing unit utilizes fully pipelined structure that is well balanced trade-off between performance and resource requirements. The proposed technique is implemented in modern FPGA structures and obtained results proved efficiency of the methodology comparing to other approaches in the field.

Słowa kluczowe

EN

DNA-tiles; pattern routing; pipelining; FPGA synthesis; parallelism and concurrency; reconfigurable systems; dynamic programming; systolic arrays

• Wydawca: Polish Academy of Sciences, Committee of Electronics and Telecommunication
• Czasopismo: International Journal of Electronics and Telecommunications
• Rocznik: 2011
• Tom: Vol. 57, No. 4
• Strony: 489--496
• Opis fizyczny: Bibliogr. 23 poz., wykr.

Twórcy

autor

Pułka A.

autor

Milik A.

• Institute of Electronics, Silesian University of Technology, Gliwice, Poland,

Bibliografia

• [1] GenBank. (2011) The official web of national center for biotechnology information. [Online]. Available: http://www.ncbi.nlm.nih.gov/
• [2] E. Pettersson, J. Lundeberg, and A. Ahmadian, “Generations of sequencing technologies,” Genomics, vol. 93, pp. 105–111, 2009.
• [3] H. S. Xu, W. K. Ren, X. H. Liu, and X. Q. Li, “Improving sequence alignment using class-specific score matrices,” in Proceedings of ICBBE 2008, The 2nd International Conference on Bioinformatics and Biomedical Engineering, 2008, pp. 70–73.
• [4] D. Gusfield, Algorithms on strings, trees and sequences. Cambridge University Press, 1997.
• [5] T. F. Smith and M. S. Waterman, “Identification of common molecular sub-sequences,” Journal of Molecular Biology, vol. 147, pp. 195–197, 1981.
• [6] FASTA. (2011) Sequence comparison at the university of virginia. [Online]. Available: http://fasta.bioch.virginia.edu/
• [7] M. C. Herbordt, J. Model, Y. Gu, B. Sukhwani, and T. VanCourt, “Single pass, blast-like, approximate string matching on fpgas,” in Proceedings of the 14th Annual IEEE Symposium on Field-Programmable Custom Computing Machines, Washington, DC, USA, 2006, pp. 217–226.
• [8] Y. Liu, D. Maskell, and B. Schmidt, “Cudasw++: optimizing smithwaterman sequence database searches for cuda-enabled graphics processing units,” BMC Research Notes, vol. 2, no. 1, p. 73, 2009.
• [9] S. A. Manavski and G. Valle, “Cuda compatible gpu cards as efficient hardware accelerators for smith-waterman sequence alignment,” BMC Bioinformatics, p. S10, 2008.
• [10] K. Benkrid, Y. Liu, and A. Benkrid, “High performance biosequence database scanning using fpgas,” in Processing of 2007 ICASSP, IEEE International Conference on Acoustics, Speech and Signal, vol. 1, april 2007, pp. 361–364.
• [11] B. Buyukkurt and W. A. Najj, “Compiler generated systolic arrays for wavefront algorithm acceleration on fpgas,” in Proceedings of FPL 2008, International Conference on Field Programmable Logic and Applications, sep 2008, pp. 655–658.
• [12] I. T. S. Li, W. Shum, and K. Truong, “160-fold acceleration of the smithwaterman algorithm using a field programmable gate array (fpga).” BMC Bioinformatics, vol. 8, p. 185, 2007.
• [13] T. Oliver and B. Schmidt, “High performance biosequence database scanning on reconfigurable platforms,” in Proceedings of 18th International of Parallel and Distributed Processing Symposium 2004, april 2004, pp. 192–199.
• [14] Y. Yamaguchi, T. Maruyama, and A. Konagaya, “High speed homology search with fpgas,” in Proceedings of Pacific Symposium on Biocomputing02, 2002, pp. 271–282.
• [15] N. Hireche, J. M. P. Langlois, and G. Nicolescu, “A systolic array for sequence comparison based on two-logic-levels processing element,” in Proceedings of NEWCAS 2007, IEEE Northeast Workshop on Circuits and Systems, aug 2007, pp. 73–76.
• [16] R. Lipton and D. Lopresti, “A systolic array for rapid string comparison,” in Proceedings of Chapel Hill Conference on VLSI, 1985, pp. 363–376.
• [17] R. Sastry and N. Ranganathan, “A systolic array for approximate string matching,” in ICCD ’93, Proceedings of 1993 IEEE International Conference on Computer Design: VLSI in Computers and Processors, oct 1993, pp. 402–405.
• [18] F. Zhang, X.-Z. Qiao, and Z.-Y. Liu, “A parallel smith-waterman algorithm based on divide and conquer,” in Proceedings of Fifth International Conference on Algorithms and Architectures for Parallel Processing 2002, 2002, pp. 162–169.
• [19] TimeLogic. (2011) Decypher fpga biocomputing systems. [Online]. Available: http://www.timelogic.com/
• [20] Xilinx. (2011) The official web site of the xilinx company. [Online]. Available: http://www.xilinx.com/
• [21] A. Milik and A. Pułka, “Hardware oriented optimization of smithwaterman algorithm,” in Proceedings of ICSES 2010, IEEE International Conference on Signals and Electronic Systems, Gliwice, Poland, sep 2010, pp. 319–322.
• [22] S. Dydel, K. Benedyczak, and P. Bala, “Enabling reconfigurable hardware accelerators for the grid,” in Proceedings of PAR ELEC 2006, International Symposium on Parallel Computing in Electrical Engineering, sep 2006, pp. 145–152.
• [23] B. Phoophakdee and M. J. Zaki, “Genome-scale disk-based suffix tree indexing,” in Proceedings of the 2007 ACM SIGMOD International Conference on Management of Data. New York, USA: ACM, 2007, pp. 833–844.