FastLSA: A Fast, Linear-Space, Parallel and Sequential Algorithm for Sequence Alignment
- Adrian Driga
- Paul Lu, Department of Computing Science
- Jonathan Schaeffer, Department of Computing Science, University of Alberta
- Duane Szafron, UofA CS
- Kevin Charter
- Ian Parsons
Pairwise sequence alignment is a fundamental operation for homology search in bioinformatics. For two DNA or protein sequences of length m and n, full-matrix(FM), dynamic programming alignment algorithms such as Needleman-Wunsch and Smith-Waterman take O(m*n) time and use a possibly prohibitive O(m*n)space. Hirschberg’s algorithm reduces the space requirements to O(min(m,n))but requires approximately twice the number of operations required by the FM algorithms. The Fast Linear Space Alignment (FastLSA) algorithm adapts to the amount of space available by trading space for operations. FastLSA can effectively adapt to use either linear or quadratic space, depending on the amount of available memory. Our experiments show that, in practice, due to memory caching effects, FastLSA is always as fast or faster than Hirschberg and the FM algorithms. We have also parallelized FastLSA using a simple but effective form of wavefront parallelism. Our experimental results show that Parallel FastLSA exhibits good speedups.
Citation
A. Driga, P. Lu, J. Schaeffer, D. Szafron, K. Charter, I. Parsons. "FastLSA: A Fast, Linear-Space, Parallel and Sequential Algorithm for Sequence Alignment". International Conference on Parallel Processing (ICPP), Kaohsiung, Taiwan, pp 48-57, January 2003.| Keywords: | |
| Category: | In Conference |
BibTeX
@incollection{Driga+al:ICPP03,
author = {Adrian Driga and Paul Lu and Jonathan Schaeffer and Duane Szafron
and Kevin Charter and Ian Parsons},
title = {FastLSA: A Fast, Linear-Space, Parallel and Sequential Algorithm for
Sequence Alignment},
Pages = {48-57},
booktitle = {International Conference on Parallel Processing (ICPP)},
year = 2003,
}Last Updated: June 05, 2007Submitted by Staurt H. Johnson
