Improvements and Extensions to the BLAST Algorithms

与纽约大学的Nidhi Shah和Mihai Pop合作

In collaboration with Nidhi Shah and Mihai Pop of the University of Maryland, I opened a new avenue of investigation for this project. An important task in a metagenomic analysis is the assignment of taxonomic labels to sequences in a sample. Most widely used methods for taxonomy assignment compare a sequence in the sample to a database of known sequences. Many approaches use the best BLAST hit(s) to assign the taxonomic label. However, it is known that the best BLAST hit may not always correspond to the best taxonomic match. An alternative approach involves phylogenetic methods which take into account alignments and a model of evolution in order to more accurately define the taxonomic origin of sequences. The similarity- search based methods typically run faster than phylogenetic methods and work well when the organisms in the sample are well represented in the database. On the other hand, phylogenetic methods have the capability to identify new organisms in a sample but are computationally quite expensive. We proposed a two-step approach for metagenomic taxon identification; i.e., the use of a rapid method that accurately classifies sequences using a reference database (this is a filtering step) and then the use a more complex phylogenetic method for the sequences that were unclassified in the previous step. We explored whether and when using top BLAST hit(s) yields a correct taxonomic label. We develop a method to detect outliers among BLAST hits in order to separate the phylogenetically most closely related matches from matches to sequences from more distantly related organisms. We used modified BILD (Bayesian Integral Log Odds) scores, a multiple-alignment scoring function, to define the outliers within a subset of top BLAST hits and assign taxonomic labels. We compared the accuracy of our method to the RDP classifier and show that our method yields fewer misclassifications while properly classifying organisms that are not present in the database. Finally, we evaluated the use of our method as a pre- processing step before more expensive phylogenetic analyses (in our case TIPP) in the context of real 16S rRNA datasets. Our experiments demonstrated the potential of our method to be a filtering step before using phylogenetic methods. This work was presented in August at the 17th Int. Workshop on Algorithms in Bioinformatics, in Boston, MA. In collaboration with Mihai Pop, I also wrote an expository article on sequence alignment for the CRC Handbook of Discrete and Combinatorial Mathematics.