EAGER: High Performance Algorithms and Implementatations for Genome Alignment

生物序列分析是计算生物学中的一个基本问题，包括多序列比对、模体发现和基因组比对等，在单倍型重建、序列同源性分析、系统发育分析和进化起源预测等方面具有重要意义。大多数序列分析问题的公式（特别是那些与比对相关的）被认为是NP难的。序列比对问题的现有解决方案（顺序和并行）在其适用性方面非常有限，并且对于大数据集的性能很差。此外，这些解决方案中的大多数已经被设计用于比对短长度序列。基因组比对问题（非常长的序列）明显更难，并且存在能够从短读段构建基因组同时花费大量执行时间的非常少的解决方案。这个项目涉及高性能算法的设计和开发，以及使用创新的采样和区域分解策略来对齐基因组的实现。这种方法在过去从未被用于基因组比对。该项目将生物信息学、计算生物学、统计学和高性能计算等多个学科的工具和应用程序结合在一起，在多核集群和GPU单元组成的混合计算平台上实现算法。因此，这些发现将为生物学和生物医学应用引入新的工具。它将促进基因组的快速重建和将短读段映射到相应的单倍型。

Analysis of biological sequences, including multiple sequence alignment, motif finding, and genome alignment, is a fundamental problem in computational biology due to its critical significance in wide ranging applications including haplotype reconstruction, sequence homology, phylogenetic analysis, and prediction of evolutionary origins. Most of the sequence analysis problem formulations (particularly those related to alignment) are considered NP-hard. Existing solutions to the sequence alignment problem (both sequential as well as parallel) are extremely limited in their applicability and yield poor performance for large data sets. Moreover most of these solutions have been designed for aligning short length sequences. The genome alignment problem (very long sequences) is significantly harder and very few solutions exist that are capable to construct genomes from short reads while taking significant amount of execution time. This project deals with the design and development of high performance algorithms and implementations for aligning genomes using innovative sampling and domain decomposition strategies. This approach has never been pursued for genome alignment in the past. The proposed algorithms are implemented on hybrid computing platforms consisting of multicore clusters and GPU units.This project brings together tools and applications from multiple disciplines such as bioinformatics, computational biology, statistics, and high performance computing. Therefore the findings will introduce new tools for biology and biomedical applications. It will facilitate rapid reconstruction of genomes and mapping of short reads to the corresponding haplotypes.