Improved genomic sketching for MUMmer and metagenomics

项目总结 提高计算方法的效率有助于从基因组中提取洞察力 数据。快速比对分子如木乃伊、快速k-分子计数器如水母、快速表达量子fi分子如 作为旗鱼和鲑鱼，以及高质量的高效fi基因组组装器，如Masurca，一直是至关重要的 以释放基因组和元基因组数据的潜力。尽管如此，计算仍然是一个时间和 在许多应用领域存在成本瓶颈。算法草图方法，如极小化方案，具有 是实现提高计算效率fi效率的有用技术。然而，尽管它们很重要， 这些素描技术从理论角度研究不足，从实践角度也没有得到充分利用。 透视。 我们建议设计、实现、测试和验证基于SignifiCant扩展的新的草图绘制方法 对于成功的极小化草图方案，极大地提高了这些方法的fl灵活性，并具有 将它们的使用扩展到新的领域，包括处理高方差或高度重复的序列，并提供 为基因组方法设计者和软件实施者提供一个新的、标准的草图工具包。这些扩展， 统称为标记选择方案，将实现更快的对齐、群集和组装 基因组序列，并将刺激基因组应用中的进一步计算创新。 为了告知和验证这一算法工作，我们建议增强基因组的三个重要和广泛的领域 计算方法。首先，我们将广泛使用的木乃伊校准器扩展到一些应用-- 利用这些新的和现有的草图方案来实现增强的效率和效率的特定fic“模式”和 敏感度更高。这将确保继续开发和增强对此的更多应用 重要的计算工具。第二，我们将通过更新in-in来增强Masurca基因组组装器- 与新的木乃伊融合在一起。第三，我们将使用开发的标记选择方案和额外的 基于序列几何嵌入的算法思想，以开发更准确、更快速的估计 基因组序列之间的距离。这些近似距离估计器对于许多 元基因组学应用包括物种分类fi阳离子、聚类和搜索。我们将推进计算机- 通过这些改进的估计器，这些任务的计算准确性。 这个项目将产生一个更深层次的基因组草图和距离估计算法工具箱，软件 编码这些新算法以供社区更广泛使用的文库，以及一套改进的基因组 软件，包括对广泛使用的校准器和汇编器的增强，以及提高现有的 和新的元基因组学软件。

PROJECT SUMMARY Increasing the efficiency of computational methods has been instrumental to extracting insight from genomic data. Fast aligners such as MUMMER, fast k-mer counters such as JELLYFISH, fast expression quantifiers such as SAILFISH and SALMON, and high-quality efficient genome assemblers such as MASURCA have been crucial to unlocking the potential of genomic and metagenomic data. Nevertheless, computation remains a time and cost bottleneck in many application areas. Algorithmic sketching methods, such as the minimizer schemes, have been a useful technique for achieving improved computational efficiency. However, despite their importance, these sketching techniques are understudied from a theoretical perspective and underused from a practical perspective. We propose to design, implement, test, and validate new sketching approaches based on significant extensions to the successful minimizers sketching schemes, greatly increasing the flexibility of these approaches and ex- panding their use into new areas including handling high-variance or highly repetitive sequences, and providing a new, standard sketching toolkit for genomic method designers and software implementors. These extensions, collectively referred to as marker selection schemes, will enable faster alignment, clustering, and assembly of genomic sequences, and will spur further computational innovation in genomic applications. To inform and validate this algorithmic work, we propose to enhance three important and broad areas of genomic computational methods. First, we will extend the widely-used MUMMER aligner with a number of application- specific “modes” that exploit these new and existing sketching schemes to achieve enhanced efficiency and greater sensitivity. This will ensure continued development and enhancement for additional applications of this important computational tool. Second, we will enhance the MASURCA genome assembler with updated in- tegration with the new MUMMER. Third, we will use the developed marker selection schemes and additional algorithmic ideas based on geometric embedding of sequences to develop more accurate, fast estimators of distances between genomic sequences. These approximate distance estimators are essential for a number of metagenomic applications including species classification, clustering, and search. We will advance the compu- tational accuracy of these tasks through these improved estimators. This project will result in a deeper toolbox of genomic sketching and distance estimation algorithms, software libraries encoding these new algorithms for wider use by the community, and an improved suite of genomic software, including enhancements to a widely used aligner and assembler and improved accuracy in existing and new metagenomic software.