Bioinformatics Vol. 18 no. 9 2002
Pages 1236-1242
© 2002 Oxford University Press
The correlation error and finite-size correction in an ungapped sequence alignment
1 National Center for Biotechnology Information, National Library of Medicine, Bethesda, MD 20894, USA
Received on October 15, 2001
; revised on January 18, 2002
; accepted on December 3, 2002
Motivation: The BLAST program for comparing two sequences assumes independent sequences in its random model. The resulting random alignment matrices have correlations across their diagonals. Analytic formulas for the BLAST p-value essentially neglect these correlations and are equivalent to a random model with independent diagonals. Progress on the independent diagonals model has been surprisingly rapid, but the practical magnitude of the correlations it neglects remains unknown. In addition, BLAST uses a finite-size correction that is particularly important when either of the sequences being compared is short. Several formulas for the finite-size correction have now been given, but the corresponding errors in the BLAST p-values have not been quantified. As the lengths of compared sequences tend to infinity, it is also theoretically unknown whether the neglected correlations vanish faster than the finite-size correction.
Results: Because we required certain analytic formulas, our study restricted its computer experiments to ungapped sequence alignment. We expect some of our conclusions to extend qualitatively to gapped sequence alignment, however. With this caveat, the finite-size correction appeared to vanish faster than the neglected correlations. Although the finite-size correction underestimated the BLAST p-value, it improved the approximation substantially for all but very short sequences. In practice, the Altschul–Gish finite-size correction was superior to Spouge's. The independent diagonals model was always within a factor of 2 of the true BLAST p-value, although fitting p-value parameters from it probably is unwise.
Contact: spouge{at}ncbi.nlm.nih.gov
* To whom correspondence should be addressed.
CiteULike 
Connotea 
Del.icio.us What's this?
This article has been cited by other articles:
|
|
 |
|
  A. Yu. Mitrophanov and M. Borodovsky Statistical significance in biological sequence analysis Brief Bioinform, March 1, 2006; 7(1): 2 - 24.
|
|
|
|
 |
|
 S. Karlin Colloquium Perspective: Statistical signals in bioinformatics PNAS, September 20, 2005; 102(38): 13355 - 13362. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 M. C. Frith, U. Hansen, J. L. Spouge, and Z. Weng Finding functional sequence elements by multiple local alignment Nucleic Acids Res., January 2, 2004; 32(1): 189 - 200. [Abstract] [Full Text] [PDF]
|
|