Comparison of methods for searching protein sequence databases
- 1 June 1995
- journal article
- research article
- Published by Wiley in Protein Science
- Vol. 4 (6), 1145-1160
- https://doi.org/10.1002/pro.5560040613
Abstract
We have compared commonly used sequence comparison algorithms, scoring matrices, and gap penalties using a method that identifies statistically significant differences in performance. Search sensitivity with either the Smith‐Waterman algorithm or FASTA is significantly improved by using modern scoring matrices, such as BLOSUM45–55, and optimized gap penalties instead of the conventional PAM250 matrix. More dramatic improvement can be obtained by scaling similarity scores by the logarithm of the length of the library sequence (ln()‐scaling). With the best modern scoring matrix (BLOSUM55 or J093) and optimal gap penalties (‐12 for the first residue in the gap and —2 for additional residues), Smith‐Waterman and FASTA performed significantly better than BLASTP. With ln()‐scaling and optimal scoring matrices (BLOSUM45 or Gonnet92) and gap penalties (‐12, ‐1), the rigorous Smith‐Waterman algorithm performs better than either BLASTP and FASTA, although with the Gonnet92 matrix the difference with FASTA was not significant. Ln()‐scaling performed better than normalization based on other simple functions of library sequence length. Ln()‐scaling also performed better than scores based on normalized variance, but the differences were not statistically significant for the BLOSUM50 and Gonnet92 matrices. Optimal scoring matrices and gap penalties are reported for Smith‐Waterman and FASTA, using conventional or ln()‐scaled similarity scores. Searches with no penalty for gap extension, or no penalty for gap opening, or an infinite penalty for gaps performed significantly worse than the best methods. Differences in performance between FASTA and Smith‐Waterman were not significant when partial query sequences were used. However, the best performance with complete query sequences was obtained with the Smith‐Waterman algorithm and ln()‐scaling.Keywords
This publication has 28 references indexed in Scilit:
- Sequence alignment and penalty choice: Review of concepts, case studies and implicationsJournal of Molecular Biology, 1994
- A Structural Basis for Sequence Comparisons: An Evaluation of Scoring MethodologiesJournal of Molecular Biology, 1993
- The rapid generation of mutation data matrices from protein sequencesBioinformatics, 1992
- Amino acid substitution matrices from an information theoretic perspectiveJournal of Molecular Biology, 1991
- A platform for biological sequence comparison on parallel computersBioinformatics, 1991
- Basic local alignment search toolJournal of Molecular Biology, 1990
- Flexible protein sequence patterns: A sensitive method to detect weak structural similaritiesJournal of Molecular Biology, 1990
- Optimal alignments in linear spaceBioinformatics, 1988
- An Extreme Value Theory for Sequence MatchingThe Annals of Statistics, 1986
- Identification of common molecular subsequencesJournal of Molecular Biology, 1981