Improvements and Extensions to the BLAST Algorithms

在与尼泊尔大学的Nidhi Shah和Mihai Pop合作下， 马里兰州，我为这个项目开辟了一条新的调查途径。 宏基因组分析中的一个重要任务是分配 分类标签到样品中的序列。 最广泛使用的方法 对于分类分配，将样本中的序列与数据库进行比较 已知的序列。 许多方法使用最佳BLAST命中来 赋予分类标签。 然而，众所周知， BLAST命中可能并不总是对应于最佳分类学匹配。 另一种方法涉及系统发育方法， 考虑到路线和进化模型， 准确定义序列的分类学起源。 相似之处- 基于搜索的方法通常比系统发育方法运行得更快 当样本中的有机体被充分代表时， 数据库中 另一方面，系统发育方法 鉴定样品中新生物体的能力，但 在计算上非常昂贵。 我们提出了一个两步走的方法 用于宏基因组分类群鉴定;即，使用快速 一种使用参照物对序列进行准确分类的方法 数据库（这是一个过滤步骤），然后使用更复杂的 系统发育方法的序列中未分类的， 前一步。 我们探讨了是否以及何时使用顶级BLAST命中 产生正确的分类标签。 我们开发了一种方法来检测 BLAST命中中的离群值，以分离遗传学上的 从匹配到序列的最密切相关匹配 远亲生物。 我们使用改进的BILD（贝叶斯 积分对数几率）得分，多重比对得分函数， 在最高BLAST命中的子集内定义离群值，并分配 分类标签 我们比较了我们的方法的准确性RDP 分类器，并表明我们的方法产生更少的错误分类 同时对不存在于生物体中的生物体进行适当分类， 数据库 最后，我们评估了使用我们的方法作为一个预- 在更昂贵的系统发育分析之前的处理步骤（在我们的 例TIPP）在真实的16 S rRNA数据集的背景下。 我们的实验 证明了我们的方法是过滤步骤的潜力 在使用系统发育方法之前。 这项工作是在 8月，在第17届生物信息学算法国际研讨会上， 波士顿，MA。 与米哈伊·波普合作，我还写了一本 关于序列比对的文章，发表在《CRC离散序列比对手册》上。 和组合数学

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.