SALoBa: Maximizing Data Locality and Workload Balance for Fast Sequence Alignment on GPUs

Sequence alignment forms an important backbone in many sequencing applications. A commonly used strategy for sequence alignment is an approximate string matching with a two-dimensional dynamic programming approach. Although some prior work has been conducted on GPU acceleration of a sequence alignment, we identify several shortcomings that limit...

On Hardware-Accelerated Maximally-Efficient Systolic Arrays: Acceleration and Optimization of Genomics Pipelines Through Hardware/Software Co-Design

Developments in sequencing technology have drastically reduced the cost of DNA sequencing. The raw sequencing data being generated requires processing through computationally demanding suites of bioinformatics algorithms called genomics pipelines. The greatly decreased cost of sequencing has resulted in its widespread adoption, and the amount of...

Exploring Multicore Architectures For Streaming Applications

The Smith Waterman algorithm is used to perform local alignment on biological sequences by calculating a similarity matrix. This process is computation-intensive. Only the elements along the minor diagonal of the matrix can be calculated in parallel, due to the nature of dependencies present in the algorithm. In the past, CPUs, GPUs and FPGAs...

Acceleration of read alignment with coherent attached FPGA coprocessors

With the advent of Next Generation Sequencing (NGS), the cost of sequencing human DNA has decreased significantly over the past decade. This decrease in cost has attracted a great deal of attention from medical research and is now transitioning to clinical practice. Precision medicine, tailored to a persons's genetic profile, is becoming a...

Accelerating Protein Sequence Alignment with Different Parallel Hardware Platforms

Detecting similarities between (RNA, DNA, and protein) sequences is an important part of bioinformatics. Among the algorithms used to accomplish this, the Smith-Waterman algorithm is very popular. A sequential implementation of Smith-Waterman requires quadratic running time with respect to the length of the sequences. As the amount of data in...

Low-Cost Smith-Waterman Acceleration

Due to advancing technology, genetic sequencing has become cheaper over the years. This has caused the demand for computational power to grow even faster than Moore's law. To remedy this problem, we analyzed low-cost hardware solutions to parallelize the computational part of the genetic sequencing. We proposed a novel method for calculating the...

Acceleration of the Smith-Waterman algorithm for DNA sequence alignment using an FPGA platform

With the sequencing of DNA becoming cheaper and the resulting stack of data growing bigger, there is a big challenge for both engineer and biologist. Researchers are limited by their computational power. In this thesis, first an overview of sequence alignment algorithms will be given. Then a method to store the values of the similarity score...

Recursive variable expansion: A transformation for reconfigurable computing

Reconfigurable computing, in which general purpose processor (GPP) is augmented with one or more FPGAs, is increasingly used for high-performance computing where massive fine-grain parallelism and pipelining can be exploited. A challenge is to exploit such massive parallelism on FPGAs and more specifically how to map an application on the...

Biological Sequence Alignment Using Graphics Processing Units

Alignment algorithms are used to find similarity between biological sequences, such as DNA and proteins. By aligning a sequence with a database, similar sequences can be found. These can be used to identify the source of a query sequence, to find commonalities between organisms, or to infer an ancestral relation. Various methods of performing...

An Efficient and High Performance Linear Recursive Variable Expansion Implementation of the Smith-Waterman Algorithm

In this paper, we present an efficient and high performance linear recursive variable expansion (RVE) implementation of the Smith-Waterman (S-W) algorithm and compare it with a traditional linear systolic array implementation. The results demonstrate that the linear RVE implementation performs up to 2.33 times better than the traditional linear...