AF: Small: Algorithmic Techniques for High-throughput Analysis of Long Reads

DNA测序领域已经从桑格测序（Sanger sequencing，长度为700-1000个碱基对，或bp）迅速发展到短读段（100-200 bp）的大规模平行高通量测序，再到最近的长读段（5000 bp）和超长读段（50,000 bp）测序。目前迫切需要开发有效的算法来分析长读数据集在无数生物应用的背景下。长读技术保持高错误率，但具有更有吸引力的错误分布特征，通常允许对结果质量的概率保证。该项目将在开发用于长读测序的生物信息学算法方面取得基础研究进展，并提供可分发的开源软件产品，以促进生命科学界立即采用这些算法。该奖项还将支持跨学科培训和本科生参与研究。该项目旨在通过设计可证明有效的算法、正式表征结果质量、开发可扩展到更大数据集的方法以及对长读测序持续发展所带来的变化具有稳健性的方法，来推进长读测序的制图、组装和生物应用。所解决的问题包括(i)超长读段的分读映射到参考基因组，（ii）基于布隆过滤器的数据结构的开发，以实现空间优化和完美的统计灵敏度，（iii）将长读段映射到以紧凑图为基础的结构表示的参考基因组集合的算法，（iv）划分长读段的算法，以促进鉴定二倍体组合中的单倍型。(v)用于基因组间比较的长读启发比对自由算法，以及由此实现的重要生物学应用。该研究将强调对真实数据集的利用，与实际遇到的问题和应用的相关性，以及合作者和其他专家的独立验证。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

The field of DNA sequencing has rapidly evolved from Sanger sequencing (700-1000 base pairs, or bp, in length) to massively parallel high-throughput sequencing of short reads (100-200 bp) to the more recent advances in generating long ( 5,000 bp) and ultra-long ( 50,000 bp) reads. There is currently an urgent need to develop efficient algorithms for analyzing long-read datasets in the context of the myriad biological applications they enable. Long read technologies sustain high error rates but with more attractive error distribution characteristics that often permit probabilistic guarantees on the quality of results. This project will result in fundamental research advances in developing bioinformatics algorithms for long-read sequencing, along with distributable open-source software products to facilitate their immediate adoption by the life sciences community. The award will also support interdisciplinary training, and undergraduate participation in research.The project seeks to advance mapping, assembly, and biological applications of long-read sequencing through the design of provably efficient algorithms, formal characterization of the quality of results, development of methods that scale to larger datasets, and methods that are robust to changes brought about by continued developments in long read sequencing. Problems addressed include (i) split-read mapping of ultra-long reads to a reference genome, (ii) development of data structures based on bloom filters to achieve space optimization and perfect statistical sensitivity, (iii) algorithms for mapping long reads to a collection of reference genomes represented by compact graph-based structures, (iv) algorithms for partitioning long reads to facilitate identification of haplotypes in diploid assemblies, and (v) long-read inspired alignment free algorithms for genome-to-genome comparison, as well as important biological applications enabled by these. The research will emphasize utilization of real datasets, relevance to practically encountered problems and applications, and independent validation by collaborators and other experts.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.