Sequence analysis
H-BLAST: a fast protein sequence alignment
toolkit on heterogeneous computers with GPUs
Weicai Ye
1
, Ying Chen
1
, Yongdong Zhang
1,
* and Yuesheng Xu
1,2,
*
1
School of Data and Computer Science, and Guangdong Province Key Laboratory of Computational Science, Sun
Yat-sen University, Guangzhou 510275, People’s Republic of China and
2
Professor Emeritus of Department of
Mathematics, Syracuse University, Syracuse, NY 13244, USA
*To whom correspondence should be addressed.
Associate Editor: John Hancock
Received on August 6, 2016; revised on November 7, 2016; editorial decision on November 29, 2016; accepted on December 12, 2016
Abstract
Motivation: The sequence alignment is a fundamental problem in bioinformatics. BLAST is a rou-
tinely used tool for this purpose with over 118 000 citations in the past two decades. As the size of
bio-sequence databases grows exponentially, the computational speed of alignment softwares
must be improved.
Results: We develop the heterogeneous BLAST (H-BLAST), a fast parallel search tool for a hetero-
geneous computer that couples CPUs and GPUs, to accelerate BLASTX and BLASTP—basic tools
of NCBI-BLAST. H-BLAST employs a locally decoupled seed-extension algorithm for better
performance on GPUs, and offers a performance tuning mechanism for better efficiency among
various CPUs and GPUs combinations. H-BLAST produces identical alignment results as NCBI-
BLAST and its computational speed is much faster than that of NCBI-BLAST. Speedups achieved
by H-BLAST over sequential NCBI-BLASTP (resp. NCBI-BLASTX) range mostly from 4 to 10 (resp. 5
to 7.2). With 2 CPU threads and 2 GPUs, H-BLAST can be faster than 16-threaded NCBI-BLASTX.
Furthermore, H-BLAST is 1.5–4 times faster than GPU-BLAST.
Availability and Implementation: https://github.com/Yeyke/H-BLAST.git
Contact: yux06@syr.edu
Supplementary information: Supplementary data are available at Bioinformatics online.
1 Introduction
In bioinformatics, the basic local alignment search tool (BLAST)
(Altschul et al., 1990, 1997) is not only a daily used algorithm iden-
tifying regions of local similarity between biological sequences, but
also ‘the principal means by which many other algorithms query
large genomic datasets’ (Loh et al., 2012). Hence, there are fruitful
applications of BLAST in inferring functional (Mackelprang et al.,
2011) and evolutionary (Huang et al., 2014) relationships between
the corresponding organisms. As the next generation sequencing
(NGS) technique advances, the size of sequence databases has expo-
nentially grown (Daniels et al., 2013) and the search speed of
BLAST is insufficient. Therefore, sequence alignment with BLAST
became a major bottleneck. To solve this problem, a number of
tools were developed in the literature.
There are two categories of methods to accelerate BLAST search-
ing against protein databases. Methods of category one change
indexing targets from query as in BLAST to database, and modify
the non-exact match seeding strategy with a reduced amino-acid al-
phabet and spaced seeds. Commonly used software tools of this cat-
egory include BLAT (Kent, 2002), USEARCH (Edgar, 2010),
RAPSearch2 (Zhao et al., 2012) and DIAMOND (Buchfink et al.,
2015). Methods of another category are parallel implementation on
various specific hardware, such as FPGAs (field-programmable gate
arrays) (Fei et al., 2008; Herbordt et al., 2006; Wienbrandta et al.,
2011), Cell Broadband Engines (Zhang et al., 2008), multi-core
CPUs (Camacho et al., 2008), graphic processing units (GPUs) only
(Cheng and Benkridb, 2010; Suzuki et al., 2012), heterogeneous
computers with GPUs (Liu et al.; Liu et al., 2011; Vouzis and
V
C
The Author 2017. Published by Oxford University Press. All rights reserved. For Permissions, please e-mail: journals.permissions@oup.com 1130
Bioinformatics, 33(8), 2017, 1130–1138
doi: 10.1093/bioinformatics/btw769
Advance Access Publication Date: 12 January 2017
Original Paper