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.