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

Torbjørn Rognes | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

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

Author(s) -

Torbjørn Rognes

Publication year - 2001

Publication title -

nucleic acids research

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 9.008

H-Index - 537

eISSN - 1362-4954

pISSN - 0305-1048

DOI - 10.1093/nar/29.7.1647

Subject(s) - smith–waterman algorithm , computer science , simd , speedup , multiple sequence alignment , sequence alignment , algorithm , parallel computing , heuristics , computation , similarity (geometry) , heuristic , sequence (biology) , diagonal , biology , artificial intelligence , mathematics , biochemistry , genetics , geometry , gene , peptide sequence , image (mathematics) , operating system

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/

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research