An Efficient, Scalable, and Exact Representation of High-Dimensional Color Information Enabled Using de Bruijn Graph Search
An Efficient, Scalable, and Exact Representation of High-Dimensional Color Information Enabled Using de Bruijn Graph Search
复制标题
DOI：
10.1089/cmb.2019.0322
复制
发表时间：
2020-03-16
影响因子：
1.7
通讯作者：
Patro, Rob
中科院分区：
文献类型：
--
作者：
Almodaresi, Fatemeh;Pandey, Prashant;Patro, Rob
彩色 de Bruijn 图 (cdbg) 及其变体已成为基因组学众多领域中使用的重要组合结构，例如宏基因组样本中的群体水平变异检测、大规模序列搜索和基于 cdbg 的参考序列索引。当样本或基因组添加到 cdbg 中时，颜色信息开始主导表示该数据结构所需的空间。在本文中，我们展示了如何通过采用分层编码来有效地表示颜色信息，该分层编码利用 de Bruijn 图 (dbg) 中存在的颜色类（颜色出现模式）之间的相关性。利用这种相关性导出颜色信息的有效编码的一个主要挑战是确定哪些颜色类别在可能的颜色图案的高维空间中彼此接近。我们证明 dbg 本身可以用作一种有效的机制来搜索该空间中的近似最近邻居。虽然我们的方法即使对于相对较小的 cdbgs（数百个实验）也可以减少颜色信息的编码大小，但随着潜在颜色（即样本或参考）的数量增长到数千个，增益尤其重要。我们在两个不同应用程序的上下文中应用这种编码；用于大规模序列搜索索引 Mantis 的隐式 cdbg，以及 Vari 和 Rainbowfish 等工具用于群体水平变异检测的颜色信息编码。我们的结果表明颜色信息表示的整体大小和可扩展性有了显着改进。在我们对 10,000 个样本进行的实验中，与 Ramen、Ramen、Rao 相比，我们实现了 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 article, 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 into thousands. 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 >11 x better compression compared to Ramen, Ramen, Rao.