↓ Skip to main content

Accelerating the Smith-Waterman algorithm with interpair pruning and band optimization for the all-pairs comparison of base sequences

Overview of attention for article published in BMC Bioinformatics, October 2015
Altmetric Badge

About this Attention Score

  • Average Attention Score compared to outputs of the same age

Mentioned by

twitter
4 X users

Citations

dimensions_citation
17 Dimensions

Readers on

mendeley
30 Mendeley
You are seeing a free-to-access but limited selection of the activity Altmetric has collected about this research output. Click here to find out more.
Title
Accelerating the Smith-Waterman algorithm with interpair pruning and band optimization for the all-pairs comparison of base sequences
Published in
BMC Bioinformatics, October 2015
DOI 10.1186/s12859-015-0744-4
Pubmed ID
Authors

Daiki Okada, Fumihiko Ino, Kenichi Hagihara

Abstract

The Smith-Waterman algorithm is known to be a more sensitive approach than heuristic algorithms for local sequence alignment algorithms. Despite its sensitivity, a greater time complexity associated with the Smith-Waterman algorithm prevents its application to the all-pairs comparisons of base sequences, which aids in the construction of accurate phylogenetic trees. The aim of this study is to achieve greater acceleration using the Smith-Waterman algorithm (by realizing interpair block pruning and band optimization) compared with that achieved using a previous method that performs intrapair block pruning on graphics processing units (GPUs). We present an interpair optimization method for the Smith-Waterman algorithm with the aim of accelerating the all-pairs comparison of base sequences. Given the results of the pairs of sequences, our method realizes efficient block pruning by computing a lower bound for other pairs that have not yet been processed. This lower bound is further used for band optimization. We integrated our interpair optimization method into SW#, a previous GPU-based implementation that employs variants of a banded Smith-Waterman algorithm and a banded Myers-Miller algorithm. Evaluation using the six genomes of Bacillus anthracis shows that our method pruned 88 % of the matrix cells on a single GPU and 73 % of the matrix cells on two GPUs. For the genomes of the human chromosome 21, the alignment performance reached 202 giga-cell updates per second (GCUPS) on two Tesla K40 GPUs. Efficient interpair pruning and band optimization makes it possible to complete the all-pairs comparisons of the sequences of the same species 1.2 times faster than the intrapair pruning method. This acceleration was achieved at the first phase of SW#, where our method significantly improved the initial lower bound. However, our interpair optimization was not effective for the comparison of the sequences of different species such as comparing human, chimpanzee, and gorilla. Consequently, our method is useful in accelerating the applications that require optimal local alignments scores for the same species. The source code is available for download from http://www-hagi.ist.osaka-u.ac.jp/research/code/ .

X Demographics

X Demographics

The data shown below were collected from the profiles of 4 X users who shared this research output. Click here to find out more about how the information was compiled.
Mendeley readers

Mendeley readers

The data shown below were compiled from readership statistics for 30 Mendeley readers of this research output. Click here to see the associated Mendeley record.

Geographical breakdown

Country Count As %
Germany 2 7%
Unknown 28 93%

Demographic breakdown

Readers by professional status Count As %
Student > Master 5 17%
Student > Postgraduate 4 13%
Student > Ph. D. Student 4 13%
Researcher 2 7%
Student > Bachelor 2 7%
Other 3 10%
Unknown 10 33%
Readers by discipline Count As %
Computer Science 8 27%
Biochemistry, Genetics and Molecular Biology 5 17%
Engineering 3 10%
Agricultural and Biological Sciences 2 7%
Neuroscience 1 3%
Other 1 3%
Unknown 10 33%
Attention Score in Context

Attention Score in Context

This research output has an Altmetric Attention Score of 1. This is our high-level measure of the quality and quantity of online attention that it has received. This Attention Score, as well as the ranking and number of research outputs shown below, was calculated when the research output was last mentioned on 27 April 2016.
All research outputs
#15,348,067
of 22,829,683 outputs
Outputs from BMC Bioinformatics
#5,375
of 7,287 outputs
Outputs of similar age
#162,898
of 277,991 outputs
Outputs of similar age from BMC Bioinformatics
#102
of 139 outputs
Altmetric has tracked 22,829,683 research outputs across all sources so far. This one is in the 22nd percentile – i.e., 22% of other outputs scored the same or lower than it.
So far Altmetric has tracked 7,287 research outputs from this source. They typically receive a little more attention than average, with a mean Attention Score of 5.4. This one is in the 18th percentile – i.e., 18% of its peers scored the same or lower than it.
Older research outputs will score higher simply because they've had more time to accumulate mentions. To account for age we can compare this Altmetric Attention Score to the 277,991 tracked outputs that were published within six weeks on either side of this one in any source. This one is in the 32nd percentile – i.e., 32% of its contemporaries scored the same or lower than it.
We're also able to compare this research output to 139 others from the same source and published within six weeks on either side of this one. This one is in the 20th percentile – i.e., 20% of its contemporaries scored the same or lower than it.