Algorithmic Foundation for Genome Assembly: Streaming and External Memory Techniques

基因组组装的算法基础：流式传输和外部存储技术

• 批准号: 255256381
• 负责人: Professor Dr. Thorsten Reusch, Ph.D.
• 金额: --
• 依托单位: Institut für Klinische Molekularbiologie
• 依托单位国家: 德国
• 项目类别: Priority Programmes
• 财政年份: 2014
• 资助国家: 德国
• 起止时间: 2013-12-31 至 2023-12-31
• 项目状态: 已结题
• 来源: https://gepris.dfg.de/gepris/projekt/255256381?language=en
• 关键词: Algorithmic; Foundation; Genome; Assembly; Streaming

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.

重新组装基因组是生命科学中的一项基本任务。它需要解决非常大的图中的组合优化问题，这些图需要太字节范围的内存。科学进步受到这样一个事实的阻碍，即针对这类问题的现有算法没有设计成以内存和时间高效的方式处理大数据问题。在该项目的头两年，我们与基尔的生命科学小组密切合作，为基因组组装的创新算法开展了基础工作。一个关键的结果是，大型图中的子结构的新算法，如长路径或欧拉巡回，可以通过流技术以节省内存的方式进行计算。此外，我们提出了一个算法，导致了装配图的急剧减少，但它们仍然很大，我们永远受到大数据的挑战。在项目的第二阶段，我们将使用外部记忆技术和更强大的流模型来广泛地研究与基因组组装相关的图问题。这项算法研究特别是基于建立装配图的外部存储库，我们已经与法兰克福的SPP小组合作编制了该库。关于外部存储器和(装配)图形绘制算法的设计，我们期待与SPP中的其他小组合作取得科学进展和协同作用，这些小组是这些领域的专家。我们的内存高效算法将被实施并应用于基尔生命科学小组(例如海洋生态学和临床分子生物学)中由鸟枪测序产生的基因组和转录组组装图。