Fast: a novel protein structure alignment algorithm

ABSTRACT We present a novel algorithm named FAST for aligning protein three-dimensional structures. FAST uses a directionality-based scor-ing scheme to compare the intra-molecular residue– residue relationships in two structures. It employs an elimination heuristic to promote sparseness in the residue-pair graph and facilitate the detection of the global optimum. In order to test the overall accuracy of FAST, we determined its sensitivity and specificity with the SCOP classification (version 1.61) as the gold standard. FAST achieved higher sensitivities than several existing methods (Da-liLite, CE, and K2) at all specificity levels. We also tested FAST against 1033 manually curated align-ments in the HOMSTRAD database. The overall agreement was 96%. Close inspection of examples from broad structural classes indicated the high quality of FAST alignments. Moreover, FAST is an order of magnitude faster than other algorithms that attempt to establish residue–residue correspon-dence. Typical pairwise alignments take FAST less than a second with a Pentium III 1.2GHz CPU. FAST software and a web server are available a