III: Small: Computational Methods for Analyzing Complex Genomes with Sequence Data

III：小：用序列数据分析复杂基因组的计算方法

• 批准号: 1526415
• 负责人: Yufeng Wu
• 金额: $ 42.63万
• 依托单位: University of Connecticut
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2015
• 资助国家: 美国
• 起止时间: 2015-09-01 至 2020-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1526415&HistoricalAwards=false
• 关键词: III; Small; Computational; Methods; Analyzing

High-throughput sequencing is one of the most important technologies in biological research. While many species have been sequenced and analyzed, there are still many species whose genomes are not well studied. One reason is that some species have more complex genomes than others. For example, it is well-known that there are many species with large amount of repeats in their genomes. At present, many such highly repetitive genomes do not have good reference genomes. There are few existing computational tools for analyzing highly repetitive genomes from raw sequence reads when there are no reference genomes. Also, even when reference genomes are available, there may still be complex genomic regions not present in the reference genome. Methods relying on reference genomes may not work well on these regions.The broader impacts of the project include interdisciplinary collaboration between a computer scientist and a population biologist. Software to facilitate the analysis of complex genomes may have impact outside of computer science, by being of significant use to geneticists. 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. Research results will be integrated into classroom teaching. We will ensure broad dissemination of our research results and teaching materials. The intellectual merits include the development of new computational tools for analyzing highly repetitive genomes from sequence reads directly. Our methods do not assume the existence of reference genomes. Instead, we plan to develop methods that perform de novo assembly of highly repetitive genomic regions from the sequence reads, and estimate the number of repeat copies. We also plan to investigate the impact of repeats on the quality of reference genomes. At last, we plan to develop methods for studying the evolutionary history of repeats from sequence reads. The PI will leverage his previous experience with algorithm design for sequence analysis and population genomics problems. The expected project outcome includes efficient algorithms for the analysis of complex genome, related open-source software tools, and rigorous methodologies for both theoretical and empirical evaluation of the algorithms. Part of the contribution to computer science by this project is that the study of algorithms for handling large amount of sequence reads may contribute to string matching, which is a classic computer science problem. Due to the size of sequence data, algorithmic efficiency will be central to this project. Complex genome analysis provides new perspectives and formulations to various combinatorial algorithmic problems. Such formulations may raise interests in theoretical computer science community.

高通量测序是生物学研究中最重要的技术之一。虽然许多物种已被测序和分析，但仍有许多物种的基因组尚未得到很好的研究。原因之一是有些物种的基因组比其他物种更复杂。例如，众所周知，许多物种在其基因组中具有大量重复序列。目前，许多这样的高度重复的基因组没有良好的参考基因组。当没有参考基因组时，现有的用于从原始序列读数分析高度重复的基因组的计算工具很少。此外，即使当参考基因组可用时，仍可能存在参考基因组中不存在的复杂基因组区域。依靠参考基因组的方法在这些区域可能不起作用。该项目更广泛的影响包括计算机科学家和人口生物学家之间的跨学科合作。促进复杂基因组分析的软件可能对计算机科学之外的领域产生影响，因为它对遗传学家有重要作用。开发的软件工具将免费提供给多学科研究界，并有望实现高通量测序的新生物学应用。研究成果将融入课堂教学。我们将确保广泛传播我们的研究成果和教材。智力上的优点包括开发新的计算工具，用于直接从序列读数分析高度重复的基因组。我们的方法不假设参考基因组的存在。相反，我们计划开发从序列读数中重新组装高度重复的基因组区域的方法，并估计重复拷贝的数量。我们还计划研究重复序列对参考基因组质量的影响。最后，我们计划开发用于从序列读数研究重复序列的进化历史的方法。PI将利用他以前在序列分析和群体基因组学问题算法设计方面的经验。项目的预期成果包括复杂基因组分析的有效算法、相关的开放源码软件工具以及对算法进行理论和经验评估的严格方法。该项目对计算机科学的部分贡献是，处理大量序列读取的算法的研究可能有助于字符串匹配，这是一个经典的计算机科学问题。由于序列数据的大小，算法效率将是这个项目的核心。复杂基因组分析为各种组合算法问题提供了新的视角和公式。这样的公式可能会引起理论计算机科学界的兴趣。