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

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

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.