New algorithms and tools for large-scale genomic analyses

描述（由申请人提供）：大型复杂数据集的探索和解释对于基因组学的发现至关重要。然而，研究人员现在面临着一个根本性的限制;由于现代DNA测序技术，前所未有的实验是可能的，但现有的“基因组算术”技术用于比较和解剖所产生的数据集无法跟上数据集大小和复杂性的不可阻挡的增长。基因组算术（GA）代表了一组强大且广泛使用的技术，其允许人们探索基因组特征组之间的关系（例如，基因、序列比对、ChIP-seq峰或可以用染色体坐标描述的任何东西）。GA用于广泛的分析，包括：交叉/重叠特征的检测（例如，序列比对和外显子），描述数据集之间的特征覆盖，以及特征数据集的合并、减法和互补。GA功能被所有基因组浏览器和数据可视化工具以及分析软件（如GATK和SAMTOOLS）使用。由于它们的能力和灵活性，现有的GA工具（即，银河，UCSC基因组浏览器，和我们自己的BEDTOOLS）是非常受欢迎的，并用于广泛的复杂基因组分析。然而，虽然GA是基因组分析和发现的核心，但所有现有工具所采用的核心算法本质上无法扩展到现代基因组数据集的规模和多样性。由于受到这些方法的限制，目前的分析瓶颈将变得日益严重。 因此，该提案的总体目标是为基因组学界提供创新的新算法和软件，以跟上现代基因组学实验的步伐，并促进未来的发现。具体目标是：（1）设计新的高效的大规模基因组算术分析算法。我们将开发创新的GA算法，可扩展到现代基因组学实验，并能够整合许多不同的基因组数据集。我们将设计新的算法，并适应证明，可扩展的方法从计算几何领域。(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.