ALIGNMENT ALGORITHMS REVISITED: ALIGNMENT ALGORITHMS FOR LOW SIMILARITY PROTEIN SEQUENCE COMPARISONS

The Smith-Waterman local alignment algorithm is the method of choice for protein database searches because it is often able to detect remote homologues for a query protein sequence. However, it is also well known that the reliability of this algorithm degrades sharply for proteins with low similarity to a given query- so-called "twilight zone " matches. In these situations, global alignments are often employed, based largely on anecdotal evidence. This study re-examines the efficacy of local versus global alignment algorithms to answer a different question than the direct search for homologues: which of a range of global and local alignment algorithms is most likely to predict whether two proteins share a common domain, based on structure, structure-class, or function. Among other results, the Smith-Waterman algorithm is found to be most effective when two proteins have a common domain (i.e. belong to the same subgroup) or have the same function. However, when only weak relationships exist, global methods are more effective than local ones. In addition, global methods are shown to provide a somewhat different point of view to local methods, and can therefore be used in addition to local methods to improve search accuracy, even when higher level matches are possible. The study also examines the role of scaling and particularly an alternative to Pearson’s scaling formula, and examines the use of both "percent-identity " and the Sander-Schneider rule for deciding whether two proteins may be homologous. 1