Title: Homology search with binary and trinary scoring matrices

Authors: Scott F. Smith

Addresses: Department of Electrical and Computer Engineering, Boise State University, 1910 University Ave., Boise ID 83725-2075, USA

Abstract: Protein homology search can be accelerated with the use of bit-parallel algorithms in conjunction with constraints on the values contained in the scoring matrices. Trinary scoring matrices (containing only the values –1, 0, and 1) allow for significant acceleration without significant reduction in the receiver operating characteristic (ROC) score of a Smith–Waterman search. Binary scoring matrices (containing the values 0 and 1) result in some reduction in ROC score, but result in even more acceleration. Binary scoring matrices and five-bit saturating scores can be used for fast prefilters to the Smith–Waterman algorithm.

Keywords: protein homology; protein database search; substitution matrices; Smith–Waterman algorithm; protein similarity; bit-parallel algorithms; bioinformatics; trinary scoring matrices; receiver operating characteristic; binary scoring matrices; prefilters; sequence alignment.

DOI: 10.1504/IJBRA.2006.009763

International Journal of Bioinformatics Research and Applications, 2006 Vol.2 No.2, pp.119 - 131

Published online: 09 May 2006 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article