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.