III: Small: Reconstructing viral population without using a reference genome

新一代测序技术（NGS）可以从基因组中提取数百万个短DNA序列，这使基因组学领域发生了革命性的变化。一个特别重要的领域是从病毒种群中重建基因组（单倍型），这是病毒学、进化生物学和人类健康的一个基本问题。虽然已经开发了几种方法来利用NGS数据，但这些方法仅限于可获得参考基因组的人群。这排除了许多重要病例，如RNA病毒或某些HIV/HCV病毒群。在这种情况下，单倍型是足够的分歧，使参考毫无意义。此外，大多数算法在存在重组的情况下不具有鲁棒性，而重组在许多病毒种群中是常见的。该项目目标的实现将使NGS数据在病毒学领域的全部潜力得以实现。特别是，它将有助于推动对病毒种群动态的理解，并为生物学家提供强大的工具来了解疾病进展并实现新的治疗和预防策略。开发的算法和软件将通过GitHub或Galaxy等软件共享平台免费提供。pi将提供强大的教育组成部分，包括(a)使用拟议研究成果的研究生和本科生课程，以及(b)开发一系列研讨会。pi将(a)培训未来一代的科学家和工程师，以增强和使用生物信息学/基因组网络资源；(b)促进创造性的、基于网络的跨界合作，包括具有行业和国际层面的合作，以推进科学和工程领域的前沿，并扩大STEM领域的参与。这个项目吗?我们的目标是在没有参考资料的情况下，发展概率德布鲁因图和这种图上的网络流，以重建病毒种群。给定NGS数据，算法应该确定单倍型的数量、序列和相对频率。这个项目提出的算法是基于一种独特的组合，既有技术（如最大似然、期望最大化、聚类、Lander Waterman统计），也有关于概率德布鲁因图、机器学习和网络流的新命题，这些都是其他应用中感兴趣的。PI和co -PI在病毒学、机器学习、网络流和基因组重建问题方面具有互补的背景。

Next-generation sequencing (NGS), which allows sampling millions of short DNA sequences from a genome, has revolutionized the field of genomics. One area of particular importance is the reconstruction of genomes (haplotypes) from a viral population, which is a fundamental problem in virology, evolutionary biology, and human health. Though there have been several methods developed to take advantage of NGS data, those are limited to populations for which a reference genome is available. This excludes many important cases, such as RNA viruses or certain HIV/HCV viral populations. In such situations, the haplotypes are sufficiently divergent as to render the reference meaningless. Moreover, most algorithms are not robust in the presence of recombination, which is a common occurrence in many viral populations. The achievement of this project's aims will allow for the full potential of NGS data to be realized in the field of virology. In particular, it will help to propel the understanding of viral population dynamics and give biologists powerful tools to understand disease progression and enable novel treatment and prevention strategies. The algorithms and software developed will be made freely available for use through software sharing platforms like GitHub or Galaxy. The PIs will offer a strong educational component including (a) graduate and undergraduate classes that use the output of the proposed research, and (b) development of a seminar series. The PIs will (a) train future generations of scientists and engineers to enhance and use bioinformatic/genomic cyber resources; (b) facilitate creative, cyber-enabled boundary-crossing collaborations, including those with industry and international dimensions, to advance the frontiers of science and engineering and broaden participation in STEM fields.This project?s aim is to develop probabilistic De Bruijn graphs and network flow on such graphs for the reconstruction of viral population when a reference is not available. Given NGS data, the algorithms should determine the number, sequences, and relative frequencies of the haplotypes. This project's proposed algorithms are based on a unique combination of established techniques (e.g. maximum likelihood, expectation-maximization, clustering, Lander Waterman statistics) with novel propositions for probabilistic De Bruijn graphs, machine learning, and network flows that are of interest in other applications. The PI and Co-PIs have complementary backgrounds in virology, machine learning, network flow, and genome reconstruction problems.