Improvements and Extensions to the BLAST Algorithms

BLAST 算法的改进和扩展

• 批准号: 9555732
• 负责人: STEPHEN F ALTSCHUL
• 金额: $ 2.14万
• 依托单位: NATIONAL LIBRARY OF MEDICINE
• 依托单位国家: 美国
• 资助国家: 美国
• 起止时间: 至
• 项目状态: 未结题
• 来源: https://reporter.nih.gov/project-details/9555732
• 关键词: Algorithms; Bioinformatics; Boston; Collaborations; Complex; DNA Databases; Data Set; Databases; Distant; Educational workshop; Evolution; Investigation; Label; Maryland; Mathematics; Metagenomics; Methods; Modeling; Organism; Phylogenetic Analysis; Protein Databases; Protein Family; Ribosomal RNA; Running; Sampling; Sequence Alignment; Services; Taxon; Taxonomy; Time; Universities; Work; base; combinatorial; experimental study; handbook; improved; programs; rapid technique

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.

与大学的Nidhi Shah和Mihai Pop合作 马里兰州，我为这个项目开设了新的调查途径。 宏基因组分析中的一个重要任务是分配 分类标记样品中的序列。 最广泛使用的方法 对于分类学分配，将样本中的序列与数据库进行比较 已知序列。 许多方法都使用最佳的爆炸击中 分配分类标签。 但是，众所周知，最好 爆炸击中可能并不总是与最佳分类匹配相对应。 另一种方法涉及系统发育方法 考虑到一致性和进化模型，以便更多 准确定义序列的分类来源。 相似性 - 基于搜索的方法通常比系统发育方法更快 当样本中的生物很好地表示时，工作良好 在数据库中。 另一方面，系统发育方法具有 在样本中识别新生物的能力，但 计算上很昂贵。 我们提出了一种两步的方法 用于宏基因组分类单元鉴定；即，快速使用 使用参考准确对序列进行准确分类的方法 数据库（这是一个过滤步骤），然后使用更复杂的 用于未分类的序列的系统发育方法 上一步。 我们探索了是否以及使用Top Blast命中 产生正确的分类标签。 我们开发了一种检测方法 爆炸命中的离群值以分离系统发育 从匹配到序列的最紧密相关的匹配来自更多 遥远相关的生物。 我们使用了修改后的Bild（贝叶斯人 积分log赔率）得分，一个多重对准评分函数， 在顶部爆炸命中的子集中定义异常值并分配 分类标签。 我们将方法的准确性与RDP进行了比较 分类器并表明我们的方法产生的错误分类较少 虽然正确分类了不存在的生物 数据库。 最后，我们评估了方法的使用作为预先 处理更昂贵的系统发育分析（在我们的 案例tipp）在实际16S rRNA数据集的上下文中。 我们的实验 证明了我们方法成为过滤步骤的潜力 在使用系统发育方法之前。 这项工作是在 八月在17日。关于生物信息学算法的研讨会， 在马萨诸塞州波士顿。 与Mihai Pop合作，我还写了一个说明性 有关CRC离散手册的序列对齐方式的文章 和组合数学。