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

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