Measurement aspects of genome pattern investigations - hardware implementation

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

Abstrakty

EN

The work presented in the paper concerns a very important problem of searching for string alignments. The authors show that the problem of a genome pattern alignment could be interpreted and defined as a measuring task, where the distance between two (or more) patterns is investigated. The problem originates from modern computation biology. Hardware-based implementations have been driving out software solutions in the field recently. The complex programmable devices have become very commonly applied. The paper introduces a new, optimized approach based on the Smith-Waterman dynamic programming algorithm. The original algorithm is modified in order to simplify data-path processing and take advantage of the properties offered by FPGA devices. The results obtained with the proposed methodology allow to reduce the size of the functional block and radically speed up the processing time. This approach is very competitive compared with other related works.

Słowa kluczowe

EN

DNA-tiles; pattern recognition; pipelining; parallelism and concurrency; dynamic programming; systolic arrays; computational methods

• Wydawca: Komitet Metrologii i Aparatury Naukowej PAN
• Czasopismo: Metrology and Measurement Systems
• Rocznik: 2012
• Tom: Vol. 19, nr 1
• Strony: 49--62
• Opis fizyczny: Bibliogr. 22 poz., rys., tab., wzory

Twórcy

autor

Pułka A.

autor

Milik A.

• Silesian University of Technology, Faculty of Automatic Control, Electronics and Computer Science, Institute of Electronics, Akademicka 16, 44-100 Gliwice, Poland,

Bibliografia

• [1] GenBank (2010). http://www.ncbi.nlm.nih.gov/.
• [2] Pułka, A., Milik, A. (2008). A New Hardware Algorithm for Searching Genome Patterns. Proceedings of IEEE ICSES 2008, Kraków, Poland, 177-180.
• [3] Milik, A., Pułka, A. (2011). On Efficient Implementation of Search for Genome Patterns. PAK, 57(1), 15-18. (in Polish)
• [4] Gusfield, D. (1997). Algorithms on strings, trees and sequences. Cambridge University Press.
• [5] Smith, T.F., Waterman, M.S. (1981). Identification of Common Molecular Sub-sequences. Journal of Molecular Biology, 147, 195-197.
• [6] Yamaguchi, Y., Maruyama, T. (2002). High Speed Homology Search with FPGAs. Proceedings of Pacific Symposium on Biocomputing, 271-282.
• [7] Zhang, F., Qiao, X., Liu, Z. (2002). A Parallel Smith-Waterman Algorithm Based on Divide and Conquer. Proceedings of IEEE ICA3PP’02, 162-169.
• [8] Benkrid, K., Liu, Y., Benkrid, A. (2007). High Performance Biosequence Database Scanning Using FPGAs. Proceedings of IEEE ICASSP, Honolulu, Hawaii, USA, 361-364.
• [9] Xilinx, The official Web site of the Xilinx Company, http://www.xilinx.com/.
• [10] Zieliński, M. (2009). Review of Single-Stage Time-Interval Measurement Modules Implemented in FPGA Devices. Metrology and Measurement Systems, 16(4), 641-648.
• [11] Zhang, Ming, Li, Kaicheng, Hu, Yisheng. (2010). DSP-FPGA Based Real-Time Power Quality Disturbances Classifier. Metrology and Measurement Systems, 17(2), 205-216.
• [12] Buyukkurt, B., Najjar, W.A. (2008). Compiler generated systolic arrays for wavefront algorithm acceleration on FPGAs. Proceedings of IEEE ICFPLA 2008, 655-658.
• [13] Ashenden, P.J. (2008). Digital Design - An Embedded Systems Approach Using VERILOG. Morgan Kaufman Publishers.
• [14] Oliver, T., Schmidt, B. (2004). High Performance Biosequence Database Scanning on Reconfigurable Platforms. Proceedings of IPDPS, Santa Fe, New Mexico, USA, 192-199.
• [15] Lipton, R., Lopresti, D. (1985). A systolic array for rapid string comparison. Chapel Hill Conference on VLSI, 363-376.
• [16] Hoang. D.T. (1992). A Systolic Array for the Sequence Alignment Problem. Brown University, Providence, RI, Technical Report CS-92-22.
• [17] Li, T., Shum, W., Truong, K. (2007). 160-fold acceleration of the Smith-Waterman algorithm using a field programmable gate array (FPGA), BMC Bioinformatics 2007, 8, I85.
• [18] Hai Song Xu, Wen Ke Ren, Xiao Hui Liu, Xiao Qin Li (2008). Improving Sequence Alignment using Class-Specific Score Matrices, Bioinformatics and Biomedical Engineering, 2008. ICBBE 2008. The 2nd International Conference on, 70-73.
• [19] FASTA (2011). Sequence comparison at the University of Virginia. http://fasta.bioch.virginia.edu/.
• [20] BLAST (2011). Basic Local Alignment Search Tool. http://blast.ncbi.nlm.nih.gov/Blast.cgi.
• [21] Manavski, S.,A., Valle, G. (2008). CUDA compatible GPU cards as efficient hardware accelerators for Smith-Waterman sequence alignment. BMC Bioinformatics 2008, 9(Sup 2):S10.
• [22] Liu, Y., Maskell, D.L., Schmidt, B. (2009). CUDASW++: optimizing Smith-Waterman sequence database searches for CUDA-enabled graphics processing units. BMC Research Notes 2009, 2:73.