An Efficient, Scalable and Exact Representation of High-Dimensional Color Information Enabled via de Bruijn Graph Search
An Efficient, Scalable and Exact Representation of High-Dimensional Color Information Enabled via de Bruijn Graph Search
复制标题
DOI：
10.1101/464222
复制
发表时间：
2018-11
期刊：
影响因子：
--
通讯作者：
Fatemeh Almodaresi;Prashant Pandey;Michael Ferdman;Robert C. Johnson;Robert Patro
中科院分区：
文献类型：
--
作者：
Fatemeh Almodaresi;Prashant Pandey;Michael Ferdman;Robert C. Johnson;Robert Patro
彩色de Bruijn图（cdbg）及其变体已成为基因组学中许多领域中使用的重要组合结构，例如宏基因组样本中的群体水平变异检测，大规模序列搜索和基于cdbg的参考序列索引。随着样本或基因组被添加到cdbg中，颜色信息开始支配表示该数据结构所需的空间。在本文中，我们将展示如何有效地表示颜色信息，采用分层编码，利用颜色类之间的相关性-颜色发生模式-存在于德布鲁因图（dbg）。在推导利用这种相关性的颜色信息的有效编码中的主要挑战是确定哪些颜色类在可能的颜色模式的高维空间中彼此接近。我们证明，DBG本身可以作为一个有效的机制，在这个空间中搜索近似最近的邻居。虽然我们的方法即使对于相对较小的cdbg（数百次实验）也可以减少颜色信息的编码大小，但随着潜在颜色（即样本或参考）的数量增加到数千次实验，收益尤其重要。我们在两个不同的应用程序的上下文中应用这种编码;用于大规模序列搜索索引Mantis的隐式cdbg，以及通过瓦里和Rainbowfish等工具在群体水平变异检测中使用的颜色信息编码。我们的研究结果表明显着改善的整体规模和可扩展性的颜色信息的表示。在我们对10，000个样本的实验中，我们实现了比RRR高11倍的压缩。
The colored de Bruijn graph (cdbg) and its variants have become an important combinatorial structure used in numerous areas in genomics, such as population-level variation detection in metagenomic samples, large scale sequence search, and cdbg-based reference sequence indices. As samples or genomes are added to the cdbg, the color information comes to dominate the space required to represent this data structure. In this paper, we show how to represent the color information efficiently by adopting a hierarchical encoding that exploits correlations among color classes — patterns of color occurrence — present in the de Bruijn graph (dbg). A major challenge in deriving an efficient encoding of the color information that takes advantage of such correlations is determining which color classes are close to each other in the high-dimensional space of possible color patterns. We demonstrate that the dbg itself can be used as an efficient mechanism to search for approximate nearest neighbors in this space. While our approach reduces the encoding size of the color information even for relatively small cdbgs (hundreds of experiments), the gains are particularly consequential as the number of potential colors (i.e. samples or references) grows to thousands of experiments. We apply this encoding in the context of two different applications; the implicit cdbg used for a large-scale sequence search index, Mantis, as well as the encoding of color information used in population-level variation detection by tools such as Vari and Rainbowfish. Our results show significant improvements in the overall size and scalability of representation of the color information. In our experiment on 10,000 samples, we achieved more than 11× better compression compared to RRR.