Sketching Methods with Small Window Guarantee Using Minimum Decycling Sets
Sketching Methods with Small Window Guarantee Using Minimum Decycling Sets
复制标题
DOI：
10.1089/cmb.2024.0544
复制
发表时间：
2024-07-09
影响因子：
1.7
通讯作者：
Kingsford，Carl
中科院分区：
文献类型：
--
作者：
Marcais，Guillaume;Deblasio，Dan;Kingsford，Carl
大多数序列草图方法的工作原理是从序列中选择特定的序列，以便仅使用草图就可以估计两个序列之间的相似性。由于使用草图估计序列相似性比使用序列比对快得多，因此使用草图方法来减少计算生物学软件的计算需求。使用草图的应用程序通常依赖于k-mer选择过程的性质，以确保与使用序列比对相比，使用草图不会降低结果的质量。这类属性的两个重要示例是局部性和窗口保证，后者确保序列的任何较长区域都不会在草图中不出现。具有窗口保证的草图绘制方法隐式或显式地对应于de Bruijn图的循环集，这是一组不可避免的ek-mers。根据定义，任何足够长的序列都必须包含来自任何去环集的AK-mer(因此，不可避免的性质)。相反，取消循环集还通过从集合中选择k-MERS作为代表来定义草图绘制方法。尽管目前的方法使用少数草图方法族中的一种，但取消循环集的空间要大得多，而且在很大程度上尚未开发。寻找具有期望的特征(例如，较小的剩余路径长度)的解循环集是发现具有改进的性能(例如，具有较小窗口保证)的新草图方法的一种很有前途的方法。最小循环集(MDS)因其最小尺寸而特别受关注。之前已知只有Mykkeltveit和Champarnaud的两种算法可以生成两个特定的MDS，尽管通常存在大量的替代MDS。我们提供了一种简单的方法来枚举MDS。这种方法允许人们探索MDS的空间，并找到针对所需特性进行优化的MDS。我们证明了Mykeltveit集对于剩余路径长度这一特殊性质是接近最优的。文中提出了许多猜想，并提供了支持它们的计算和理论证据。代码可在https://github.com/Kingsford-Group/mdsscope上找到
Most sequence sketching methods work by selecting specifick-mers from sequences so that the similarity between two sequences can be estimated using only the sketches. Because estimating sequence similarity is much faster using sketches than using sequence alignment, sketching methods are used to reduce the computational requirements of computational biology software. Applications using sketches often rely on properties of thek-mer selection procedure to ensure that using a sketch does not degrade the quality of the results compared with using sequence alignment. Two important examples of such properties are locality and window guarantees, the latter of which ensures that no long region of the sequence goes unrepresented in the sketch. A sketching method with a window guarantee, implicitly or explicitly, corresponds to adecycling setof the de Bruijn graph, which is a set of unavoidablek-mers. Any long enough sequence, by definition, must contain ak-mer from any decycling set (hence, the unavoidable property). Conversely, a decycling set also defines a sketching method by choosing thek-mers from the set as representatives. Although current methods use one of a small number of sketching method families, the space of decycling sets is much larger and largely unexplored. Finding decycling sets with desirable characteristics (e.g., small remaining path length) is a promising approach to discovering new sketching methods with improved performance (e.g., with small window guarantee). TheMinimum Decycling Sets(MDSs) are of particular interest because of their minimum size. Only two algorithms, by Mykkeltveit and Champarnaud, are previously known to generate two particular MDSs, although there are typically a vast number of alternative MDSs. We provide a simple method to enumerate MDSs. This method allows one to explore the space of MDSs and to find MDSs optimized for desirable properties. We give evidence that the Mykkeltveit sets are close to optimal regarding one particular property, the remaining path length. A number of conjectures and computational and theoretical evidence to support them are presented. Code available at https://github.com/Kingsford-Group/mdsscope