Skip Navigation

This Article
Right arrow Full Text Freely available
Right arrow Print PDF (460K) Freely available
Right arrow Alert me when this article is cited
Right arrow Alert me if a correction is posted
Services
Right arrow Email this article to a friend
Right arrow Similar articles in this journal
Right arrow Similar articles in ISI Web of Science
Right arrow Similar articles in PubMed
Right arrow Alert me to new issues of the journal
Right arrow Add to My Personal Archive
Right arrow Download to citation manager
Right arrow Search for citing articles in:
ISI Web of Science (18)
Right arrowRequest Permissions
Right arrow Commercial Re-use Guidelines
for Open Access NAR Content
Google Scholar
Right arrow Articles by Rognes, T.
Right arrow Search for Related Content
PubMed
Right arrow PubMed Citation
Right arrow Articles by Rognes, T.
Social Bookmarking
Add to CiteULike   Add to Connotea   Add to Del.icio.us  
What's this?

Nucleic Acids Research, 2001, Vol. 29, No. 7 1647-1652
© 2001 Oxford University Press

ParAlign: a parallel sequence alignment algorithm for rapid and sensitive database searches

Torbjørn Rognes*

Department of Molecular Biology, Institute of Medical Microbiology, University of Oslo, The National Hospital, NO-0027 Oslo, Norway

There is a need for faster and more sensitive algorithms for sequence similarity searching in view of the rapidly increasing amounts of genomic sequence data available. Parallel processing capabilities in the form of the single instruction, multiple data (SIMD) technology are now available in common microprocessors and enable a single microprocessor to perform many operations in parallel. The ParAlign algorithm has been specifically designed to take advantage of this technology. The new algorithm initially exploits parallelism to perform a very rapid computation of the exact optimal ungapped alignment score for all diagonals in the alignment matrix. Then, a novel heuristic is employed to compute an approximate score of a gapped alignment by combining the scores of several diagonals. This approximate score is used to select the most interesting database sequences for a subsequent Smith–Waterman alignment, which is also parallelised. The resulting method represents a substantial improvement compared to existing heuristics. The sensitivity and specificity of ParAlign was found to be as good as Smith–Waterman implementations when the same method for computing the statistical significance of the matches was used. In terms of speed, only the significantly less sensitive NCBI BLAST 2 program was found to outperform the new approach. Online searches are available at http://dna.uio.no/search/

* Tel: +47 23074067; Fax: +47 23074061; Email: torbjorn.rognes{at}labmed.uio.no


Add to CiteULike CiteULike   Add to Connotea Connotea   Add to Del.icio.us Del.icio.us    What's this?


This article has been cited by other articles:


Home page
 Nucleic Acids ResHome page
R. Weel-Sneve, M. Bjoras, and K. I. Kristiansen
Overexpression of the LexA-regulated tisAB RNA in E. coli inhibits SOS functions; implications for regulation of the SOS response
Nucleic Acids Res., November 1, 2008; 36(19): 6249 - 6259.
[Abstract] [Full Text] [PDF]

Home page
 Nucleic Acids ResHome page
K. Lagesen, P. Hallin, E. A. Rodland, H.-H. Staerfeldt, T. Rognes, and D. W. Ussery
RNAmmer: consistent and rapid annotation of ribosomal RNA genes
Nucleic Acids Res., May 14, 2007; 35(9): 3100 - 3108.
[Abstract] [Full Text] [PDF]

Home page
 Nucleic Acids ResHome page
P. E. Saebo, S. M. Andersen, J. Myrseth, J. K. Laerdahl, and T. Rognes
PARALIGN: rapid and sensitive sequence similarity searches powered by parallel computing technology
Nucleic Acids Res., July 1, 2005; 33(suppl_2): W535 - W539.
[Abstract] [Full Text] [PDF]

Home page
 Nucleic Acids ResHome page
I. Morland, V. Rolseth, L. Luna, T. Rognes, M. Bjoras, and E. Seeberg
Human DNA glycosylases of the bacterial Fpg/MutM superfamily: an alternative pathway for the repair of 8-oxoguanine and other oxidation products in DNA
Nucleic Acids Res., November 15, 2002; 30(22): 4926 - 4936.
[Abstract] [Full Text] [PDF]


Disclaimer: Please note that abstracts for content published before 1996 were created through digital scanning and may therefore not exactly replicate the text of the original print issues. All efforts have been made to ensure accuracy, but the Publisher will not be held responsible for any remaining inaccuracies. If you require any further clarification, please contact our Customer Services Department.