The Library
Computing alignment plots efficiently
Tools
Krusche, Peter and Tiskin, Alexander (2010) Computing alignment plots efficiently. In: Chapman, Barbara and Desprez, Frédéric and Joubert, Gerhard R. and Lichnewsky, Alain and Peters, Frans and Priol, Thierry, (eds.) Parallel Computing: From Multicores and GPU's to Petascale. Advances in Parallel Computing, Volume 19 . IOS Press, pp. 158-165. ISBN 9781607505297
PDF
0909.pdf Embargoed item. Restricted access to Repository staff only - Requires a PDF viewer. Download (168Kb) |
Official URL: http://dx.doi.org/10.3233/978-1-60750-530-3-158
Abstract
Dot plots are a standard method for local comparison of biological sequences. In a dot plot, a substring to substring distance is computed for all pairs of fixed-size windows in the input strings. Commonly, the Hamming distance is used since it can be computed in linear time. However, the Hamming distance is a rather crude measure of string similarity, and using an alignment-based edit distance can greatly improve the sensitivity of the dot plot method. In this paper, we show how to compute alignment plots of the latter type efficiently. Given two strings of length m and n and a window size w, this problem consists in computing the edit distance between all pairs of substrings of length w, one from each input string. The problem can be solved by repeated application of the standard dynamic programming algorithm in time O(mnw^2). This paper gives an improved data-parallel algorithm, running in time $O(mnw/\gamma/p)$ using vector operations that work on $\gamma$ values in parallel and $p$ processors. We show experimental results from an implementation of this algorithm, which uses Intel's MMX/SSE instructions for vector parallelism and MPI for coarse-grained parallelism.
Item Type: | Book Item | ||||
---|---|---|---|---|---|
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||
Series Name: | Advances in Parallel Computing | ||||
Publisher: | IOS Press | ||||
ISBN: | 9781607505297 | ||||
Book Title: | Parallel Computing: From Multicores and GPU's to Petascale | ||||
Editor: | Chapman, Barbara and Desprez, Frédéric and Joubert, Gerhard R. and Lichnewsky, Alain and Peters, Frans and Priol, Thierry | ||||
Official Date: | 2010 | ||||
Dates: |
|
||||
Volume: | Volume 19 | ||||
Page Range: | pp. 158-165 | ||||
Status: | Peer Reviewed | ||||
Publication Status: | Published | ||||
Access rights to Published version: | Restricted or Subscription Access | ||||
Funder: | Engineering and Physical Sciences Research Council (EPSRC), University of Warwick. Centre for Discrete Mathematics and Its Applications | ||||
Conference Paper Type: | Paper | ||||
Title of Event: | Proceedings of ParCo | ||||
Type of Event: | Conference | ||||
Related URLs: | |||||
Open Access Version: |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |