Algorithms for the Analysis of Data from Massively-parallel Genome Sequencing

新一代DNA测序技术正在给现代生物学研究带来革命性的变化。科学家们现在可以在短短几天内用一个测序仪器生成大致相当于整个人类基因组（约30亿个碱基对的DNA）。直到最近，如此大量的数据只能在大型基因组中心使用数百台测序仪产生。这些数据的分析因其规模而变得复杂——测序仪器的单次运行产生tb级的信息，通常需要对现有计算基础设施进行大规模扩展。该项目正在开发用于分析新一代测序数据的并行算法，特别关注在谷歌和IBM支持的高度分布式计算集群上实现的Map-Reduce范式。该项目主要集中于开发序列比对和序列组装的算法。基因组数据分析中的关键任务是什么？并且涉及到字符串匹配和图算法对Map-Reduce范式的适应。这项工作将有可能导致并行化的基因组分析软件，使研究人员能够通过网络规模的计算资源分析新一代测序数据，从而避免建立和维护本地高性能计算基础设施的需要。在此项目中开发的软件将在开源许可下提供，以鼓励广泛使用并使未来的研究成为可能。该研究与研究生和本科生的教学和指导相结合，工作结果将通过期刊出版物和会议报告传播。

New generation DNA sequencing technologies are revolutionizing modern biological research. Scientists can now generate the rough equivalent of an entire human genome (~3 billion base-pairs of DNA) in just a few days with one single sequencing instrument. Until recently, such amounts of data could only be generated at large genome centers using hundreds of sequencers. The analysis of these data is complicated by their size - a single run of a sequencing instrument yields terabytes of information, often requiring a significant scale-up of the existing computational infrastructure. This project is developing parallel algorithms for analyzing new generation sequencing data with a specific focus on the Map-Reduce paradigm implemented on a highly-distributed computing cluster supported by Google and IBM. The project is primarily focused on developing algorithms for sequence alignment and sequence assembly ? critical tasks in the analysis of genomic data ? and involves the adaptation of string matching and graph algorithms to the Map-Reduce paradigm. This work will potentially lead to parallelism-enabled genomic analysis software that will allow researchers to analyze new generation sequencing data through web-scale computational resources, thereby obviating the need for establishing and maintaining a local high-performance computing infrastructure. The software developed during this project is being made available under an open-source license in order to encourage broad use and to enable future research. The research is integrated with teaching and mentoring of graduate and undergraduate students and the results of the work will be disseminated through journal publications and conference presentations.