Mathematically Rigorous Results In Sequence Matching.

National Library Of Medicine

Investigators

Linked publications, trials & patents

Abstract

The NCBI CoreTools now contains code from us, code that calculates to practical accuracies, and in less than 1 sec, all parameters of the modified Gumbel distribution (the Gumbel scale parameter, λ, pre-factor k, and finite-size correction). The BLAST group has implemented our faster calculations to generate the modified Gumbel parameters for several new DNA scoring schemes and incorporated our finite-size correction into BLAST. Our code enables a real-time composition correction to BLAST searches, so it solves a fundamental open bioinformatics problem, one recognized by researchers since the late 90's. Implemented as a switch in BLAST for compositionally-skewed queries, the code could improve retrieval results for medically important queries such as malaria and tuberculosis, with arbitrarily small costs in computational speed. BLAST searches have yet to incorporate our code for real-time composition corrections, however. Our collaboration with Dr. Martin Frith has extended our methods to next-generation sequence matching, including frameshifts in DNA, a subject of relevance to the NCBI BLAST services. In a practical test of our methods, our frameshift statistics approximately doubled the number of known human pseudogenes. Dr. Frith has incorporated our program FALP into his genomic alignment program, LAST, so that it can handle frameshifts in next-generation sequence matches. We have made our results available to the NCBI BLAST group.