Re2Pair:通过降低内存使用量来增加RePair的可扩展性
Justin Kim1, Rahul Varki2, Marco Oliva2
1Department of Computer and Information Science and Engineering, University of Florida, Gainesville, Florida, 32607.
bioRxiv : the preprint server for biology
|July 29, 2024
概括
与BigRePair相比,递归RePair (rRePair) 增强了生物信息学的文本压缩,减少了40%以上的内存使用量,并增加了高达79%的速度,提高了大型数据集的可扩展性.
科学领域:
- 生物信息学是一种生物信息学.
- 计算机科学 计算机科学
- 数据压缩数据压缩
背景情况:
- RePair压缩算法创建无上下文语法,以提供高效的文本访问.
- BigRePair使用无前解析 (PFP) 进行 RePair 的缩放,但在进行大型解析时面临内存瓶.
研究的目的:
- 开发一个更可扩展的 RePair 压缩算法,解决 BigRePair 的内存限制.
- 引入递归RePair (rRePair),可以在没有直接解析访问的情况下构建语法.
主要方法:
- 实现了使用递归前免费解析的递归RePair (rRePair).
- 仅使用文本字典和解析字典信息构建RePair语法.
- 将rRePair与BigRePair进行比较,使用SARS-CoV-2和1000个基因组项目的单元型数据.
主要成果:
- 与BigRePair相比,rRePair实现了超过40%的峰值记忆减少.
- 对于大型输入文本,rRePair显示了12%至79%的加快速度.
- 这种新的算法成功地构建了RePair语法,而没有直接的解析访问.
结论:
- 与BigRePair相比,递归RePair (rRePair) 在内存效率和压缩速度方面提供了显著的改进.
- rRePair提供了一个可扩展的解决方案,用于生物信息学和相关领域的文本压缩.
- 该rRePair算法是公开可用的研究和应用.
相关概念视频
Long-patch Base Excision Repair
7.0K
Since the discovery of the two BER pathways, there has been a debate about how a cell chooses one pathway over the other and the factors determining this selection. Numerous in vitro experiments have pointed out multiple determinants for the sub-pathway selection. These are:
7.0K
Fixing Double-strand Breaks
12.5K
The double-stranded structure of DNA has two major advantages. First, it serves as a safe repository of genetic information where one strand serves as the back-up in case the other strand is damaged. Second, the double-helical structure can be wrapped around proteins called histones to form nucleosomes, which can then be tightly wound to form chromosomes. This way, DNA chains up to 2 inches long can be contained within microscopic structures in a cell. A double-stranded break not only damages...
12.5K
Base Excision Repair
22.2K
One of the common DNA damages is the chemical alteration of single bases by alkylation, oxidation, or deamination. The altered bases cause mispairing and strand breakage during replication. This type of damage causes minimal change to the DNA double helix structure and can be repaired by the base excision repair (BER) pathways. BER corrects damaged DNA sequences by removing the damaged base and restoring the original base sequence using the complementary strand as a template.
The first step of...
The first step of...
22.2K
Nucleotide Excision Repair
3.5K
DNA Distortion and Damage
Cells are regularly exposed to mutagens—factors in the environment that can damage DNA and generate mutations. UV radiation is one of the most common mutagens and is estimated to introduce a significant number of changes in DNA. These include bends or kinks in the structure, which can block DNA replication or transcription. If these errors are not fixed, the damage can cause mutations, which in turn can result in cancer or disease depending on which sequences are...
Cells are regularly exposed to mutagens—factors in the environment that can damage DNA and generate mutations. UV radiation is one of the most common mutagens and is estimated to introduce a significant number of changes in DNA. These include bends or kinks in the structure, which can block DNA replication or transcription. If these errors are not fixed, the damage can cause mutations, which in turn can result in cancer or disease depending on which sequences are...
3.5K
Homologous Recombination
50.4K
The basic reaction of homologous recombination (HR) involves two chromatids that contain DNA sequences sharing a significant stretch of identity. One of these sequences uses a strand from another as a template to synthesize DNA in an enzyme-catalyzed reaction. The final product is a novel amalgamation of the two substrates. To ensure an accurate recombination of sequences, HR is restricted to the S and G2 phases of the cell cycle. At these stages, the DNA has been replicated already and the...
50.4K
Mismatch Repair
40.0K
Overview
40.0K


