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

DNA测序领域已经从桑格测序（长度为700-1000个碱基对或bp）快速发展到短读段（100-200 bp）的大规模并行高通量测序，再到产生长读段（5，000 bp）和超长读段（50，000 bp）的最近进展。目前迫切需要开发有效的算法来分析长读数据集的背景下，他们使无数的生物应用。长读技术维持高错误率，但具有更有吸引力的错误分布特性，通常允许对结果质量的概率保证。该项目将导致在开发用于长读序的生物信息学算法方面的基础研究进展，沿着可分发的开源软件产品，以促进生命科学界立即采用这些软件产品。该项目旨在通过设计可证明有效的算法、对结果质量进行正式表征、开发可扩展到更大数据集的方法以及对长读序测序持续发展所带来的变化具有鲁棒性的方法，来推进长读序测序的映射、组装和生物应用。所解决的问题包括（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.