Hardware acceleration for multiple sequence alignment of proteins

Abstract

Uzun süredir aktif bir araştırma alanı olan Çoklu Dizi Hizalaması (MSA), biyoinformatik alanında kullanılan sayısal hesaplamaya dayalı bir yöntemdir. Proteinler için MSA, üç veya daha fazla amino asit dizisinin hizalanması işlemi anlamına gelmektedir. Bu işlemin çıktıları; homoloji aramaları, filogenetik analiz, protein yapısı tahmini gibi biyoinformatiğin başka alanları için girdi bilgilerini oluşturur. MSA için literatürdeki çözümler genel hatlarıyla üç gruba ayrılır: Doğrudan yaklaşım, gelişimsel yaklaşımlar ve yinelemeli yaklaşımlar. H4MSA, çok amaçlı eniyileme ve bir tür genetik algoritma içeren, mevcut yinelemeli yaklaşımlardan biridir. Bu çalışmada, MSA için bir donanım hızlandırması önerilmiş ve test algoritması olarak H4MSA kullanılmıştır. Hızlandırma, MSA uygulamalarında yaygın bir puanlama çeşidi olan ve ayrıca H4MSA algoritmasında bir amaç fonksiyonu olarak da kullanılan, ağırlıklı çiftler toplamı skoru (WSPS) hesabı için donanımsal bir yapı tasarlanarak geçekleştirilmiştir. Tüm uygulama, bir SOC (tek yonga üzerinde sistem) cihazı içine kurulmuş olup; cihazın FPGA bölümünde donanım bloğu inşa edilmiş ve test algoritması cihazın merkezi işlem biriminde (CPU) çalıştırılmıştır. Tasarımın testi için iyi bilinen bir veri tabanından 12 farklı dizi seti kullanılmış olup, sonuçlar donanımsal hızlandırılmış versiyonun, CPU versiyonuna oranla 1.7x ile 20x arasında hız artırımlarına ulaştığını göstermiştir.

Multiple Sequence Alignment (MSA), which has been an active research area for a long time, is a computational task that is used in the field of bioinformatics. MSA for proteins involves the process of aligning three or more amino acid sequences. The outputs of this task provide further information for other areas in bioinformatics such as homology searches, phylogenetic analysis and protein structure prediction. The algorithmic solutions for MSA can mainly be split into three groups: Direct approach, progressive approaches and iterative approaches. H4MSA is one of the iterative approaches in the literature, that uses multi-objective optimization and a type of genetic algorithm (GA) to solve the MSA problem. In this work, a hardware acceleration is proposed for the MSA tasks and H4MSA is selected as the test algorithm. The acceleration is accomplished by designing a hardware block for the evaluation of weighted sum of pairs score (WSPS), which is a commonly used scoring function in MSA applications and also used as an objective function in the H4MSA algorithm. The entire application is built in a CYCLONE V SOC device, where the hardware is implemented in the FPGA fabric and the test algorithm is run on the CPU core of the device. For testing the design, 12 different sequence sets from a well-known database are used, and the results show that the accelerated version of the algorithm achieves speedups of 1.7x to 20x over the CPU version.