Efektywna implementacja algorytmu wyszukiwania wzorców genetycznych

• Autorzy: Milik A. , Pułka A.

Warianty tytułu

EN

On efficient implementation of the search algorithm for genome patterns

• Języki publikacji: PL

Abstrakty

PL

W artykule zaprezentowano implementację algorytmu obliczającego stopień podobieństwa sekwencji znaków (genów) do zadanego wzorca. Algorytm wywodzi się z biologii obliczeniowej. Rozwiązania programowe wymagają znacznych zasobów sprzętowych oraz czasu. W badaniach nad algorytmem główny nacisk położono na poznanie jego własności i ich wykorzystanie przy implementacji. Pozwoliło to stworzyć bardzo oryginalna implementację zapewniającą niezwykle oszczędne gospodarowanie zasobami w układzie programowalnym jak i uzyskanie bardzo wysokich częstotliwości pracy.

EN

The paper describes implementation of the computation algorithm in modern, complex programmable hardware devices. The presented algorithm originates from computation biology and works on very long chains of symbols which come from reference patterns of the genome. The software solutions in this field are very limited and need large time and space resources. The main research efforts were aimed at investigating the properties of the searching algorithm. Especially, the influence of the penalty values assigned to the mismatch, insertion and deletion on the algorithm was analysed. This allowed obtaining a completely new algorithm offering extremely efficient implementation and exhibiting the outstanding performance. The Virtex 5 FPGA family was considered to be a target family for the searching algorithm based on the dynamic programming idea. The obtained results are very promising and show the dominance of the dedicated platform over the general purpose PC-based systems.

Słowa kluczowe

PL

programowanie dynamiczne; identyfikacja wzorców; rozpoznawanie wzorców; przetwarzanie równoległe; przetwarzanie potokowe

EN

dynamic programming; computational methods; pattern identification; pattern recognition; parallel processing; pipeline processing

• Wydawca: Wydawnictwo PAK
• Czasopismo: Pomiary Automatyka Kontrola
• Rocznik: 2011
• Tom: R. 57, nr 1
• Strony: 15--18
• Opis fizyczny: Bibliogr. 8 poz., rys., wzory

Twórcy

autor

Milik A.

autor

Pułka A.

• Politechnika Śląska, Instytut Elektroniki, ul. Akademicka 16, 44-100 Gliwice,

Bibliografia

• [1] Smith T. F. and Waterman M.S.: Identification of Common Molecular Sub-sequences, Journal of Molecular Biology 147 (1981), pp. 195–197.
• [2] Gusfield D.: Algorithms on strings, trees and sequences, Cam-bridge University Press, 1997.
• [3] Yamaguchi Y., Maruyama T.: High Speed Homology Search with FPGAs, Proceedings of Pacific Symposium on Biocomputing 2002, pp. 271–282.
• [4] Zhang F., Qiao X., Liu Z.: A Parallel Smith-Waterman Algorithm Based on Divide and Conquer, Proceedings of Fifth International Conference on Algorithms and Architectures for Parallel Processing (ICA3PP'02), 2002.
• [5] Benkrid K., Liu Y., Benkrid A.: High Performance Biosequence Database Scanning Using FPGAs, Proceedings of IEEE In-ternational Conference on Acoustics, Speech and Signal Processing ICASSP Honolulu, Hawaii, USA 2007, pp. 361–364.
• [6] Phoophakdee B. and Zaki M. J. (2007): Genome-scale disk-based suffix tree indexing”, Proceedings of 2007 ACM SIGMOD international conference on Management of data, Beijing, China. pp. 833–844.
• [7] Milik A., Pułka A.: The Reconfigurable Hardware Accelerator for Searching Genome Patterns, Proceedings of the IFAC Workshop on Programmable Devices and Embedded Systems PDeS 2009, Roznov pod Radhostem, Czech Rep. Feb. 10-12, 2009, pp. 33–38.
• [8] Xilinx, Virtex-5 User Guide, Xilinx, 2007.