Homology search with binary and trinary scoring matrices.
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.
Department of Electrical and Computer Engineering, Boise State University, 1910 University Avenue, Boise, ID 83725, USA. sfsmith@boisestate.edu
Scott F
SF
Smith
D000465:Algorithms; D019295:Computational Biology / Q000379:methods*; D030562:Databases, Protein; D005189:False Positive Reactions; D015233:Models, Statistical; D011506:Proteins / Q000737:chemistry*; D012372:ROC Curve; D012680:Sensitivity and Specificity; D016415:Sequence Alignment; D017421:Sequence Analysis; D020539:Sequence Analysis, Protein; D012984:Software
D011506:Proteins