New algorithms and tools for large-scale genomic analyses

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