DNA字符串可以包含任意长度的5个字母(A、T、G、C、N)的任意组合。
有没有一种有效的方法来压缩由这5个字母组成的DNA字符串?除了考虑每个字母3个比特位外,我们能否使用更少的比特位进行高效的压缩和检索?有人能提供一个有效的压缩和检索的伪代码吗?
DNA字符串可以包含任意长度的5个字母(A、T、G、C、N)的任意组合。
有没有一种有效的方法来压缩由这5个字母组成的DNA字符串?除了考虑每个字母3个比特位外,我们能否使用更少的比特位进行高效的压缩和检索?有人能提供一个有效的压缩和检索的伪代码吗?
您有5个唯一的值,因此需要一个基于5的编码(例如:A=0,T=1,G=2,C=3,N=4)。
在32位中,您可以装下log5(232) = 13个基于5的值。
在64位中,您可以装下log5(264) = 27个基于5的值。
编码过程如下:
uint8_t *input = /* base-5 encoded DNA letters */;
uint64_t packed = 0;
for (int i = 0; i < 27; ++i) {
packed = packed * 5 + *input++;
}
解码:
uint8_t *output = /* allocate buffer */;
uint64_t packed = /* next encoded chunk */;
for (int i = 0; i < 27; ++i) {
*output++ = packed % 5;
packed /= 5;
}
3位:缺失的字符(如果没有,则使用Roee的编码进行该部分);
x位:前缀下一部分中的位数-取决于最长部分可能有多少个字符。 x = 6意味着最大部分长度可以是2^(2^6)! 不太可能。对于长度最大的部分为65000,我们可以分配x = 4;
前缀上一部分指示的位数,表示当前部分的长度。
gzip
压缩格式的压缩算法)。请注意,有些评论说通用压缩算法在原始基因数据上不起作用,但它们的有效性取决于数据如何呈现给它们。gzip
)以每字节为基础检查其输入。这意味着在3比特/碱基处“预压缩”基因组数据是适得其反的;相反,在通过通用压缩器之前,应将未压缩的基因组数据格式化为每个碱基一个字节。Ascii“AGTCN”编码应该很好,只要您不通过包括空格、换行或大小写变化来添加噪音。
log2( 5^n)
最接近下一个更大的整数,n=3
似乎是一个不错的选择。 - 463035818_is_not_a_number(b)
)?对于随机访问,5³略低于2⁷:使用7位编码每次三个碱基(N
代表什么?)(请参见user463035818的评论)。 - greybeard