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.