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.