Bioinformatics and Computational Molecular Biology

Algorithms and Hardware

Test Code and Results for Constrained Bit-Parallel Smith-Waterman Homology Search Algorithm

This page contains support materials for the paper "Parallelization of Homology Search in Bioinformatics by Constraint of Substitution Matrices", which is currently under review.

Abstract: The effects of constraining substitution matrices used for database homology search to contain only the values -1, 0, and 1 are examined. Such a constraint is desirable for use in very fast software implementations of search algorithms using bit-parallel techniques on standard desktop computers and for creating compact special-purpose hardware implementations of the algorithms. Substitution matrix constraint is found to have a rather small effect on receiver operating characteristic (ROC) measures of algorithm sensitivity and specificity. The design of bit-parallel Smith-Waterman database search software using the constraints is shown and its performance analyzed.

SW_Test: The C-language source code for a program to test the speed of the standard Smith-Waterman algorithm for comparison with the Bit-parallel algorithm.

CSW_Test: The C-language source code for a program to test the speed of the bit-parallel algorithm for comparison with the standard Smith-Waterman algorihtm.

Results: An Excel spreadsheet with the full results for each of the 50 cases run to determine average ROC50 scores comparing use of constrained substitution matrices and gap penalties with the use of unconstrained values.

Boise State University College of Engineering

Boise State University Department of Electrical and Computer Engineering

This page created by Dr. Scott F. Smith

This page was last updated on 07 May 2006.