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

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

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.