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. 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 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.