TY - JOUR

T1 - Computing alignment plots efficiently

AU - Krusche, Peter

AU - Tiskin, Alexander

PY - 2010/1/1

Y1 - 2010/1/1

N2 - 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/γ/p) using vector operations that work on γ values in parallel and p processors. © 2010 The authors and IOS Press. All rights reserved.

AB - 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/γ/p) using vector operations that work on γ values in parallel and p processors. © 2010 The authors and IOS Press. All rights reserved.

UR - http://www.scopus.com/inward/record.url?scp=84870682946&partnerID=8YFLogxK

U2 - 10.3233/978-1-60750-530-3-158

DO - 10.3233/978-1-60750-530-3-158

M3 - Article

AN - SCOPUS:84870682946

VL - 19

SP - 158

EP - 165

JO - Advances in Parallel Computing

JF - Advances in Parallel Computing

SN - 0927-5452

ER -