CAREER: Efficient and Accurate Computation for High Throughput Sequencing Related Problems in Population Genomics

高通量测序正在改变种群基因组学领域。在过去十年中，通过测序获得个人基因组的成本已经下降了几个数量级，并可能在未来几年内达到所谓的1000美元基因组目标。现在很多注意力都转移到了种群规模的测序上。已经产生了大量的种群测序数据。因此，迫切需要开发新的计算方法来处理嘈杂的、高通量的测序数据，为重要的群体基因组学问题提供高效、准确的分析。这项工作的智力优点包括开发了精确的计算方法，能够分析几个种群基因组学问题的大规模高通量测序数据。感兴趣的问题包括推断基因型，纠正测序错误和检测减数分裂重组，以及寻找引起疾病的罕见基因变异和其他高通量测序的新兴应用。所提出的研究与许多现有方法之间的关键区别在于，所提出的方法是为处理大量高通量测序数据而明确设计的。一个特别的焦点是应用组合优化技术，如整数线性规划，这是不为人所知的生物学家。概率模型也将被使用，并与优化方法相结合，以提供有效和准确的解决方案。预期的项目成果包括针对上述种群基因组问题的高效算法，相关的开源软件工具，以及对算法进行理论和实证评估的严格方法。这项工作对计算机科学的部分贡献是，处理短序列读取的算法的研究可能有助于字符串匹配算法的研究，这是计算机科学中普遍感兴趣的问题。有噪声的测序数据自然地激发了近似字符串匹配，并可能导致新的基于字符串的问题公式。由于效率的需要，算法字符串处理技术可能在拟议的研究中发挥重要作用。所提出的工作的其他方面与系统发育问题有关，这在计算机科学中已经得到了积极的研究。将对这些算法问题进行理论研究，以获得计算机科学研究界可能感兴趣的严谨结果。该项目的更广泛影响包括跨学科合作和培训，以及教育影响。开发的软件工具将免费提供给多学科研究界，并有望实现高通量测序的新生物学应用。该项目将在康涅狄格大学开发跨学科的本科和研究生教育课程。拟议的教育和推广活动包括接触不同背景的学生，以及培养具有独特跨学科技能的未来研究人员。

High-throughput sequencing is transforming the field of population genomics. The cost of obtaining an individual's genome via sequencing has dropped several orders of magnitude during the past decade, and may reach the so-called $1,000 genome target within the next few years. Now much attention has shifted to sequencing on a population scale. Large amount of population sequencing data has already been generated. Therefore, there is an urgent need for the development of new computational methods that work with noisy, high-throughput sequencing data to provide efficient and accurate analysis for important population genomics problems. The intellectual merits of the work include the development of accurate computational methods that are capable of analyzing large-scale high-throughput sequencing data for several population genomics problems. Problems of interest include inferring genotypes, correcting sequencing errors and detecting meiotic recombination, as well as searching for disease-causing rare gene variants and other emerging applications of high-throughput sequencing. A key difference between the proposed research and many existing methods is that the proposed approaches are explicitly designed for processing large amount of high-throughput sequencing data. One particular focus is on applying combinatorial optimization techniques such as integer linear programming, which is not well-known to biologists. Probabilistic models will also be used and integrated with optimization approaches to provide efficient and accurate solutions. The expected project outcome includes efficient algorithms for the above population genomics problems, related open-source software tools, and rigorous methodologies for both theoretical and empirical evaluation of the algorithms.Part of the contribution of this work to computer science is that the study of algorithms for handling short sequencing reads may contribute to the research of string matching algorithms, a problem of general interests in computer science. Noisy sequencing data motivates naturally approximate string matching and may lead to new string-based problem formulations. Due to the need of efficiency, algorithmic string processing techniques may play an important role in the proposed research. Other aspects of the proposed work are related to phylogenetic problems, which have been actively studied in computer science. Theoretical study on these algorithmic problems will be conducted to obtain rigorous results that may be of interest to computer science research community.The broader impacts of the project include interdisciplinary collaboration and training, as well as educational impacts. The developed software tools will be made available freely to the multi-disciplinary research community, and are expected to enable novel biological applications of high-throughput sequencing. The PI will develop an interdisciplinary undergraduate and graduate educational curriculum at University of Connecticut. The proposed educational and outreach activities include reaching out to students with various backgrounds, and training of future researchers with unique interdisciplinary skills.