Algorithmic Foundation for Genome Assembly: Streaming and External Memory Techniques

基因组从头组装是生命科学的一项基础性工作。它需要在非常大的图形需要内存在TB范围内的组合优化问题的解决方案。 科学进步受到这样一个事实的阻碍，即针对这些问题的现有算法不是为了以内存和时间有效的方式科普大数据问题而设计的。在项目的头两年，我们与基尔的生命科学团体密切合作，为基因组组装的创新算法进行了基础工作。一个关键的结果是，在大型图的子结构，如长路径或欧拉图尔斯，新的算法可以计算在一个内存有效的方式与流技术。 此外，我们提出了一种算法，导致装配图的大幅减少，但它们仍然很大，我们永远受到大数据的挑战。在项目的第二阶段，我们将广泛研究与外部存储技术和更强大的流模型相关的基因组组装图问题。 这种算法研究特别是基于建立一个外部存储器库的汇编图，我们已经在编译合作与SPP集团在法兰克福。关于外部存储器和（汇编）图形绘制算法的设计，我们希望与SPP中的其他小组合作取得科学进步和协同作用，他们是这些领域的专家。 我们的内存高效算法将被实施和应用于基因组和转录组组装图所产生的鸟枪测序在生命科学组在基尔，例如，海洋生态学和临床分子生物学。

De novo genome assembly is a fundamental task in life science. It requires the solution of combinatorial optimization problems in very large graphs requiring memory in terabyte range. The scientific progress is hampered by the fact that existing algorithms for such problems are not designed to cope with the big data issue in a memory and time efficient way. In the first two years of the projectwe have carried out the ground work for an innovative algorithmics for genome assembly in close cooperation with life science groups in Kiel. A key result is that new algorithms for substructures in large graphs, like long paths or Eulerian tours, can be computed in a memory-efficient way with streaming techniques. Furthermore, we presented an algorithm leading to a drastic reduction of assembly graphs, but they are still large and we are perpetually challenged by big data. In the second phase of the project we will extensivelystudy graph problems related to genome assembly with external-memory techniques and more powerful streaming models. This algorithmic research is in particular based on the building of an external-memory library of assembly graphs, which we are already compiling in cooperation with the SPP group in Frankfurt. Concerning the design of external memory and (assembly-)graph drawing algorithms we expect scientific progress and synergies in cooperation with other groups in the SPP, who are expert in these areas. Our memory-efficient algorithms will be implemented and applied to genome and transcriptome assembly graphs arising fromshotgun sequencing in life science groups in Kiel, e.g., marine ecology and clinical molecular biology.