New algorithms and tools for large-scale genomic analyses

描述（由申请人提供）：对大型复杂数据集的探索和解释对于基因组学的发现至关重要。然而，研究人员现在面临着一个基本的限制；由于现代DNA测序技术，前所未有的实验成为可能，然而现有的用于比较和剖析所得数据集的“基因组算法”技术无法跟上数据集规模和复杂性的不可阻挡的增长。基因组算法（GA）是一种强大而广泛使用的技术，它允许人们探索基因组特征集之间的关系（例如，基因，序列比对，ChIP-seq峰，或任何可以用染色体坐标描述的东西）。遗传算法用于广泛的分析，包括：检测交叉/重叠特征（例如，序列比对和外显子），描述数据集之间的特征覆盖，以及特征数据集的合并，减去和补充。所有基因组浏览器和数据可视化工具以及分析软件（如GATK和SAMTOOLS）都使用GA功能。由于它们的功能和灵活性，现有的遗传工具（即Galaxy， UCSC基因组浏览器和我们自己的BEDTOOLS）非常受欢迎，并用于广泛的复杂基因组分析。然而，虽然遗传算法是基因组分析和发现的核心，但所有现有工具所采用的核心算法都无法适应现代基因组数据集的规模和多样性。由于这些方法的限制，目前的分析瓶颈将变得越来越尖锐。因此，本提案的总体目标是为基因组学社区提供创新的新算法和软件，以跟上现代基因组学实验的步伐，并促进未来的发现。具体目标是：(1)为大规模基因组算法分析设计高效的新算法。我们将开发创新的遗传算法，扩展到现代基因组学实验，并能够整合许多不同的基因组数据集。我们将设计新的算法，并从计算几何领域采用经过验证的可扩展方法。(2)开发有助于创新分析和新工具开发的软件和库。我们将把我们的算法作为开源软件库和工具发布给社区，这将促进新的工具开发，并为探索大规模数据集提供创新的方法。(3)将我们的工具扩展到可扩展的计算框架，以实现未来的基因组发现。我们将使我们的软件适应并行计算环境，从而能够在日益庞大和复杂的数据集上继续发现。这项提议的研究将为基因组算法设计出全新的、可扩展的方法。这将为社区探索和解释基因组学实验提供强大的新技术，并为工具开发人员提供可靠的软件开发和改进方法。

DESCRIPTION (provided by applicant): The exploration and interpretation of large, complex datasets is vital to discovery in genomics. However, researchers now confront a fundamental limitation; unprecedented experiments are possible thanks to modern DNA sequencing technologies, yet existing "genome arithmetic" techniques for comparing and dissecting the resulting datasets are incapable of keeping pace with inexorable growth in dataset size and complexity. Genome arithmetic (GA) represents a powerful and widely used set of techniques that allow one to explore relationships among sets of genome features (e.g., a gene, sequence alignment, ChIP-seq peak, or anything that can be described with chromosome coordinates). GA is used for a broad spectrum of analyses including: the detection of intersecting/overlapping features (e.g., sequence alignments and exons), describing feature coverage among datasets, and the merging, subtraction, and complementation of feature datasets. GA functionality is used by all genome browsers and data visualization tools, and by analysis software such as GATK and SAMTOOLS. Owing to their power and flexibility, existing GA tools (i.e., Galaxy, the UCSC Genome Browser, and our own BEDTOOLS) are extremely popular and are used in a broad range of complex genomic analyses. However, while GA is central to genomic analysis and discovery, the core algorithms employed by all existing tools are inherently incapable of scaling to the scale and diversity of modern genomic datasets. Restricted to these approaches, the present analytic bottleneck will become increasingly acute. Therefore, the overall objective of this proposal is to provide the genomics community with innovative new algorithms and software that keep pace with modern genomics experiments and facilitate future discoveries. The Specific Aims are to: (1) Devise efficient new algorithms for large-scale genome arithmetic analyses. We will develop innovative GA algorithms that scale to modern genomics experiments and are capable of integrating many diverse genomic datasets. We will devise novel algorithms and adapt proven, scalable approaches from the field of computational geometry. (2) Develop software and libraries that facilitate innovative analyses and new tool development. We will release our algorithms to the community as open-source software libraries and tools that will foster new tool development and provide innovative approaches for exploring large-scale datasets. (3) Extend our tools to scalable computing frameworks in order to enable future genomic discovery. We will adapt our software to parallel computing environments and thereby enable continued discovery on increasingly massive and complex datasets. The proposed research will devise entirely new, scalable approaches for genome arithmetic. This will provide the community with powerful new techniques for exploring and interpreting genomics experiments and provide tool developers with robust approaches for software development and improvement.