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

点击翻译按钮获取中文摘要

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.