Position Sensitive P-Mer Frequency Clustering with Applications to Classification

描述(由申请人提供)： 位置敏感的P-Mer频率聚类及其在分类和区分方面的应用最近的基因组测序进展，如下一代测序，以及像人类微生物组计划这样的项目创建了极大的基因组数据库。尽管任何特定序列的长度可能比生物体的完整DNA序列短得多，但寻找巨大的序列文库，如16S rRNA，带来了同样(如果不是更大的)计算挑战。在传统的基因组分析中，一次只能分析一个序列。在处理元基因组学时，需要同时分析数千条(或更多)序列。然而，要研究环境生物多样性和人类微生物多样性等问题，这正是需要的。目前的技术有几个缺点需要解决。涉及序列比对的技术通常基于选择一个具有代表性的序列(正如在查看16S rRNA数据时通常所做的那样)，这引入了选择偏差。涉及数千个生物体中每个有机体的多个16S拷贝的基因组数据库很快就会变得太大，以至于仅仅使用计算昂贵的比对方法来匹配序列就无法实际处理，但更快的非比对方法目前无法提供所需的准确性和灵敏度。作为对现有方法的补充，我们引入了一类新的基于位置特定p-mer频率聚类的准对齐的快速高通量算法。生物体由有向图结构表示，该有向图结构总结了序列中不同位置处的p-mer频率直方图簇之间的排序。这个模型可以使用生物体的所有可用的16S拷贝来学习，从而消除了选择偏见。由于增加了位置信息，这些算法可以用于物种(甚至菌株)分类，便于研究物种内的菌株多样性。我们对这项新技术的原型实现表明，它能够产生紧凑的轮廓，可以有效地存储并用于大范围的分类和区分，一直到应变水平。由于该技术结合了高吞吐量数据流聚类，这是一种在高性能计算中得到验证的技术，它可以很好地扩展到超大规模DNA/RNA序列数据以及在元基因组研究期间收集的大量短序列片段集。在这个项目中，我们将开发一套工具、轮廓模型和评分技术来模拟RNA/DNA序列，提供生物分类和生物内/生物间相似性/多样性的应用。我们的方法既提供了执行菌株分类所需的特异性，又避免了比对的计算开销。值得注意的是，这是通过动态在线机器学习技术实现的，无需人工干预。 公共卫生相关性： 元基因组学和人类微生物组的最新进展为同时处理大量基因组提供了一个复杂的图景。这一领域的众多挑战之一是对样本中存在的基因组进行分类。有效的元基因组分类和多样性分析需要对分类群进行复杂的表示。我们研究的意义在于，我们开发了一套工具，基于新的无比对技术，将应用于环境元基因组学样本以及人类微生物组样本。使用我们的新方法在笔记本电脑上而不是在几个多处理器服务器上提供这种快速分类生物的方法，将有助于在不久的将来快速发展基于微生物组的健康筛查。

DESCRIPTION (provided by applicant): Position Sensitive P-Mer Frequency Clustering with Applications to Classification and Differentiation Recent genomic sequencing advances, such as next generation sequencing, and projects like the Human Microbiome Project create extremely large genomic databases. Even though the length of any specific sequence may be much shorter than that of the complete DNA sequence of an organism, looking at enormous libraries of sequences, such as 16S rRNA, presents an equally (if not greater) computational challenge. In traditional genomic analysis, only one sequence may be analyzed at a time. When dealing with metagenomics, thousands (or more) sequences need to be analyzed at the same time. However, to study such problems as environmental biological diversity and human microbiome diversity this is exactly what is needed. Current techniques have several shortcomings which need to be addressed. Techniques involving sequence alignment are typically based on selection of one representative sequence (as is typically done when looking at 16S rRNA data) which introduces selection bias. Genomic databases involving multiple copies of 16S per organism across thousands of organisms, will soon grow too large to practically process just using computationally expensive alignment methods to match sequences, but faster alignment-free methods currently do not provide the needed accuracy and sensitivity. As a complement to existing methods we introduce a novel class of fast high-throughput algorithms based on quasi-alignment using position specific p-mer frequency clustering. Organisms are represented by a directed graph structure that summarizes the ordering between clusters of p-mer frequency histograms at different positions in sequences. This model can be learned using all available 16S copies of an organism and thus eliminates selection bias. Due to the added position information, these algorithms can be used for species (and even strain) classification facilitating the study of strain diversity within species. Our prototype implementation of this new technique shows that it is able to produce compact profiles which can be efficiently stored and used for large scale classification and differentiation down to the strain level. Since the technique incorporates high-throughput data stream clustering, a proven technique in high performance computing, it scales well for very large scale DNA/RNA sequence data as well as massive sets of short sequence snippets collected during metagenomic research. In this project we will develop a suite of tools, profile models, and scoring techniques to model RNA/DNA sequences providing applications of organism classification, and intra/inter-organism similarity/diversity. Our approach provides both the specificity needed to perform strain classification and still avoid the computational overhead of alignment. It is important to note that this is accomplished through dynamic online machine learning techniques without human intervention. PUBLIC HEALTH RELEVANCE: Recent advances in Metagenomics and the Human Microbiome provide a complex landscape for dealing with a multitude of genomes all at once. One of the many challenges in this field is classification of the genomes present in the sample. Effective metagenomic classification and diversity analysis require complex representations of taxa. The significance of our research is that we develop a suite of tools, based on novel alignment free techniques that will be applied to environmental metagenomics samples as well as human microbiome samples. Providing such methods to rapidly classify organisms using our new approach on a laptop computer instead of several multi-processor servers will facilitate the rapid development of microbiome-based health screening in the near future.