HySim: Hybrid-parallel similarity search for the analysis of big genomic and proteomic data

近年来，生命科学产生的数据量急剧增加。对这些数据集的分析提出了困难的计算挑战，是一个活跃的研究领域。目前，在科学和工业的许多领域的数据丰富场景中，一种流行的策略是采用大数据技术。然而，典型生物数据集的特征及其预期用途与大多数其他大数据应用领域有很大不同。生物数据处理通常需要比大数据技术所能提供的更复杂的分析技术，而大数据技术往往限于具有线性或次线性复杂性的算法或启发式算法。在许多应用场景中，对真实结果的粗略近似是完全可以接受的，但在生命科学中，这种情况很少发生。生物医学应用程序通常甚至不能容忍中等数量的分类错误。因此，今天的计算生命科学倾向于依赖于一种不同的计算模型来处理大规模应用，即高性能计算(HPC)。然而，HPC更多地是针对具有大量计算工作(大计算)问题而不是针对具有巨大存储需求(大数据)的问题而定制的。生物数据集的特殊性和所需数据分析的复杂性构成了这两种方法都不能完全克服的挑战。相反，将大数据的想法与HPC方法相结合的混合方法可能是更可取的，因为来自大数据算法的想法可以帮助灵活且高性能的HPC方法扩展到原本对它们来说太大的数据集。在本项目中，我们建议研究这种混合方法，以应对高效而准确地处理大规模基因组和蛋白质组数据集的挑战。我们特别关注的是相似性搜索；这是一种重要的算法技术，在基因组学和蛋白质组学中都有许多应用。相应的数据集由两种类型的高通量技术产生：下一代测序仪(NGS)和质谱仪(MS)。我们的具体项目目标有三个：(I)设计高效和准确的大数据算法，用于在NGS数据中进行相似性搜索，并将其应用于元基因组学和基于位置敏感散列(LSH)技术的读取纠错。(Ii)设计高效、准确的大数据相似度搜索算法及其在蛋白质组学中的应用。(3)在大数据/高性能计算混合平台上开发这些新算法的高效实施，为大规模NGS和MS数据集提供强大的可扩展性。

Recent years have seen a tremendous increase in the volume of data generated in the life sciences. The analysis of these data sets poses difficult computational challenges and is an active field of research. Currently, a popular strategy in data rich scenarios across many areas of science and industry is to adopt big data technologies. However, characteristics of typical biological data sets and their intended uses differ significantly from most other big data application areas. Biological data processing often requires more complex analysis techniques than can be afforded by big data technology, which is often constrained to algorithms or heuristics with linear or sublinear complexity. In many application scenarios, rough approximations of true outcomes are perfectly acceptable, but in the life sciences, this is rarely the case. A biomedical application will typically be unable to tolerate even moderate numbers of classification mistakes. Consequently, computational life sciences today tend to rely on a different computational model for large scale applications, namely high performance computing (HPC). However, HPC is tailored more towards problems with a significant amount of computational work (big compute) than at those with enormous storage requirements (big data). The peculiarities of biological data sets and the complexity of the required data analysis pose challenges that neither of the two approaches is perfectly suited to overcome. Instead, a hybrid approach, combining ideas from big data with HPC methodologies, might be preferable, as ideas from big data algorithms can help flexible and highly performant HPC methods to scale towards data sets that would otherwise be too large for them.In this project, we propose to study such hybrid methods in order to meet the challenge of processing large scale genomic and proteomic data sets efficiently yet accurately. Our particular focus is similarity search; an important algorithmic technique for a number of applications in both genomics and proteomics. Corresponding data sets are produced by two types of high throughput technologies: Next Generation Sequencers (NGS) and Mass Spectrometers (MS).Our specific project goals are threefold: (i) Design of efficient and accurate big data algorithms for similarity search in NGS data with applications to metagenomics and read error correction based on locality sensitive hashing (LSH) techniques. (ii) Design of efficient and accurate big data algorithms for similarity search in MS raw data with applications to proteomics based on LSH techniques. (iii) Development of efficient implementations of these new algorithms on a hybrid big data/HPC platform that provide strong scalability for large scale NGS and MS data sets.