保持局部性的k-mers的最小完美散列
Giulio Ermanno Pibiri1,2, Yoshihiro Shibuya3, Antoine Limasset4
1Ca' Foscari University of Venice, Venice 30172, Italy.
这项研究为k-mers.引入了一种新的局部维护最小完美的哈希函数 (MPHF). 新的MPHF结构减少了空间使用,增加了k,提供了实际的好处.
科学领域:
- 计算机科学 计算机科学
- 数据结构 数据结构
- 算法算法是一种算法.
背景情况:
- 最小完美的哈希 (MPHF) 将n个不同的密钥映射到 {1,...,n} 中.
- 标准的MPHF需要每键n log2{\displaystyle n_{log2}{e}}比特,而无需利用密钥关系.
- 利用密钥中的内在关系,比如字符串中的k-mers,可以减少空间复杂性.
研究的目的:
- 开发一种针对连续提取的k-mers.而定制的新型本地保护MPHF.
- 设计一个空间使用量随k增加而减少的建筑.
- 为了保持哈希函数输出空间中的k-mers的顺序关系.
主要方法:
- 引入了一个新的MPHF结构,专门用于从字符串中衍生的k-mers.
- 开发了一种方法,其中哈希函数的大小与k相反相关.
- 实施并评估拟议的MPHF的实际表现.
主要成果:
- 拟议的MPHF建设表明,对于较大的k.的空间需求减少.
- 与现有的MPHF相比,实际实施显示了空间利用的显著改善.
- 该方法还为连续k-mers提供更快的查询时间,增强参考的局部性.
结论:
- 新的局部保护MPHF对k-mer数据集有效.
- 这种方法在空间和查询时间方面为生物信息学和字符串处理应用提供了实际优势.
- 利用k-mers的固有结构可以实现更高效的散列解决方案.
更多相关视频
12:27Large-scale Reconstructions and Independent, Unbiased Clustering Based on Morphological Metrics to Classify Neurons in Selective Populations
Published on: February 15, 2017
12:11Simultaneous Affinity Enrichment of Two Post-Translational Modifications for Quantification and Site Localization
Published on: February 27, 2020
相关概念视频
¹H NMR Chemical Shift Equivalence: Homotopic and Heterotopic Protons
Modern Molecular Taxonomy
Routh-Hurwitz Criterion I
To apply the Routh-Hurwitz criterion, a Routh table is constructed. The table's rows are labeled with powers of the complex frequency variable s, starting from the...
Routh-Hurwitz Criterion II
The first scenario occurs when a singular zero appears in the first column of the Routh table. This situation creates a division by zero issues. To resolve this, a small positive or negative number, denoted as epsilon (∈), is substituted for the zero. The stability analysis proceeds by assuming a sign for ∈. If ∈ is positive, any sign change in the first...
Multi-species Conserved Sequences
Although the genome of each species varies greatly from each other, a few sequences are highly conserved. Such conserved...
Conservation of Protein Domains Over Different Proteins
A limited set of protein domains often duplicate and recombine during evolution. These domains can be organized in different combinations to...
