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

职业：群体基因组学中高通量测序相关问题的高效、准确计算

• 批准号: 0953563
• 负责人: Yufeng Wu
• 金额: $ 49.64万
• 依托单位: University of Connecticut
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2010
• 资助国家: 美国
• 起止时间: 2010-07-01 至 2017-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0953563&HistoricalAwards=false
• 关键词: CAREER; Efficient; Accurate; Computation; Throughput

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.

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