Hybrid alignment: high-performance with universal statistics.
The score statistics of a recently introduced 'hybrid alignment' algorithm is studied in detail numerically. An extensive survey across the 2216 models of protein domains contained in the Pfam v5.4 database (Bateman et al., Nucleic Acids Res., 28, 263-266, 2000) verifies the theoretical predictions: For the position-specific scoring functions used in the Pfam models, the score statistics of hybrid alignment obey the Gumbel distribution, with the key Gumbel parameter lambda taking on the asymptotic value 1 universally for all models. Thus, the use of hybrid alignment eliminates the time-consuming computer simulations normally needed to assign p-values to alignment scores, freeing the users to experiment with different scoring parameters and functions. The performance of the hybrid algorithm in detecting sequence homology is also studied. For protein sequences from the SCOP database (Murzin et al., J. Mol. Biol., 247, 536-540, 1995) using uniform scoring functions, the performance is found to be comparable to the best of the existing methods. Preliminary results using the PfamA database suggest that the hybrid algorithm achieves similar performance as existing methods for position-specific scoring systems as well. Hybrid alignment is thereby established as a high performance alignment algorithm with well-characterized, universal statistics.
Yu
Yi-Kuo
YK
Department of Physics, Florida Atlantic University, 777 Glades Road, Boca Raton 33431-0991, USA. yyu@fau.edu
Bundschuh
Ralf
R
Hwa
Terence
T
D000465:Algorithms; D019295:Computational Biology; D003198:Computer Simulation; D030562:Databases, Protein; D012372:ROC Curve; D016415:Sequence Alignment / Q000706:statistics & numerical data*