CAREER: Addressing Algorithmic Challenges in Computational Genomic Epidemiology

抗击病毒性流行病是现代全球互联世界面临的主要挑战之一。最近的技术进步对我们应对这一挑战产生了深远影响。 它们允许快速和成本有效的测序（即，阅读）病原体基因组，并且可以在几乎真实的时间内产生大量数据。基因组流行病学是一个跨学科的研究领域，它使用病毒基因组的大规模分析来了解病毒如何进化和传播。 基因组流行病学的方法目前不仅成为研究的主要工具，而且也成为具有广泛社会重要性的公共卫生决策的主要工具。然而，其计算工具包仍在开发中，这一过程面临着许多困难的算法挑战。 一些主要问题是：（i）如何从嘈杂和碎片化的测序数据中提取病毒遗传多样性的整个谱，包括新出现的突变和变体;（ii）如何使用基因组数据来调查疫情并重建病毒传播网络;以及（iii）如何识别高致病性或可传播的病毒变体。这些问题的算法应该是准确的，可重复的，可解释的和可扩展的，相对于现代测序平台产生的“大数据”的水平。开发此类算法并研究相应的算法问题正是本项目的目标。其他主要目标是帮助将计算基因组学带入高中和本科课堂，通过先进的教学技术扩大计算生物学的参与，并促进下一代跨学科研究人员的培训，他们将同时拥有计算机科学，流行病学和分子生物学的专业知识，本项目将从理论计算机科学的角度对基因组流行病学的基本计算问题进行系统研究。总体目标是开发基于算法图论，网络理论和数学（特别是组合）优化技术的跨学科融合的新方法。第一个主要的具体科学目标是开发使用统计学关联突变网络和图分解方法评估病毒遗传多样性的方法。第二个目标是开发一个家庭的组合算法，用于重建病毒传播网络，使用融合的遗传学和网络理论的方法，社交网络相关的感染传播。 最终的目标是设计可扩展的计算技术，用于使用组合和凸优化来量化病毒表型多样性。 研究者将与生物学家和流行病学家密切合作，以确保所开发算法的生物医学相关性和适用性。它也预计，一些新的机器将适用于非生物医学的图论和复杂网络的研究中出现的问题。这个奖项反映了NSF的法定使命，并已被认为是值得通过使用基金会的智力价值和更广泛的影响审查标准进行评估的支持。

Fighting viral epidemics is one of the major challenges faced by the modern globally connected world. Recent technological advances had a profound effect on our answers to that challenge. They allow for rapid and cost-effective sequencing (i.e., reading) of pathogen genomes and can generate enormous amounts of data in almost real time. Genomic epidemiology is an interdisciplinary research area that uses the large-scale analysis of viral genomes to understand how viruses evolve and spread. The methods of genomic epidemiology are currently becoming major instruments not only for research, but also for public-health decision making of broad societal importance. However, its computational toolkit is still developing, and this process faces many hard algorithmic challenges. Some of the major problems are: (i) how to extract the whole spectrum of viral genetic diversity, including newly emerging mutations and variants, from noisy and fragmented sequencing data; (ii) how to use genomic data to investigate outbreaks and reconstruct virus-transmission networks; and (iii) how to identify highly pathogenic or transmissible viral variants. The algorithms for these problems should be accurate, reproducible, interpretable and scalable with respect to the levels of "big data" produced by modern sequencing platforms. Development of such algorithms and study of the corresponding algorithmic problems is exactly the goal of this project. Other major objectives are to help to bring computational genomics into high-school and undergraduate classrooms, to broaden participation in computational biology via advanced pedagogical techniques, and to facilitate training of the next generation of interdisciplinary researchers, who will simultaneously possess an expertise in computer science, epidemiology, and molecular biology, and will be able to develop innovative algorithms and apply them to real-life problems.This project will undertake the systematic study of fundamental computational problems of genomic epidemiology from the theoretical computer-science perspective. The overarching objective is the development of new methods based on cross-disciplinary convergence of techniques from algorithmic graph theory, network theory and mathematical (and, particularly, combinatorial) optimization. The first major specific scientific goal is the development of methods for assessment of viral genetic diversity using networks of statistically linked mutations and a graph-decomposition approach. The second goal is the development of a family of combinatorial algorithms for reconstruction of viral transmission networks using the fusion of phylogenetics and a network-theory approach to social networks relevant to infection dissemination. The final goal is the design of scalable computational techniques for quantification of viral phenotypic diversity using combinatorial and convex optimization. The investigator will closely collaborate with biologists and epidemiologists to ensure biomedical relevance and applicability of the developed algorithms. It is also expected that some of the new machinery will be applicable to non-biomedical problems arising in graph theory and in studies of complex networks.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.