将字符串存储为整数的函数

Question

我有一个固定的 32 位来存储尽可能多的 DNA。存储 1 个 DNA 字符（'A'、'C'、'G' 或 'T'）所需的 space 量为 2 位（00、 01、10、11，因为只有 4 个组合）。

要存储 最多 2 个字符，（因此，A、C、G、T、AA, AC, ..., GG) 有 20 种可能的组合，我们可以用函数 ((4**(x+1))-2)/(4-1) 计算出来，其中 x 是最大值我们要存储的 DNA 长度。因此，DNA 的 16 个字符将有 5,726,623,060 种组合，但是在 32 位中我最多只能存储 4,294,967,296 个数字 (2**32)。

长话短说，在 32 位中，一个人可以存储的可变长度 DNA 的最大数量是 15 个字母（1,431,655,764 种组合）。

所以，下一步是制作一个函数，将最多 15 个 DNA 字母作为一个字符串，并将其转换为一个数字。哪个数字并不重要（'A'可以是0，可以是1，也可以是1332904，真的没关系）只要我们可以反转函数，稍后将数字返回'A'。

我开始通过制作包含 1,431,655,764 个元素的 key, value 对的字典来解决这个问题，但很快运行就用完了 RAM。这就是为什么我需要一个从字符串到整数的 t运行slation 函数。

Answer 1

这是我的建议。

如果存储字母需要 2 到 30 位，那么您至少还有 2 位可以帮助您推断长度。始终在代表您的字符的位之后添加 1，并用零填充其余部分。这样，如果您在您的位模式中查找 last 1，它总是在您的字符串结尾之后。

例如

A  -> 00 (meaning 'A') followed by 1 (meaning 'end') followed by 29 zeroes
   -> 00100000000000000000000000000000
C  -> 01 (meaning 'C') followed by 1 (meaning 'end') followed by 29 zeroes
   -> 01100000000000000000000000000000
G  -> 10 (meaning 'G') followed by 1 (meaning 'end') followed by 29 zeroes
   -> 10100000000000000000000000000000
T  -> 11 (meaning 'T') followed by 1 (meaning 'end') followed by 29 zeroes
   -> 11100000000000000000000000000000
AA -> 0000 (meaning 'AA') followed by 1, followed by 27 zeroes
   -> 00001000000000000000000000000000
...
AAAAAAAAAAAAAAA
   -> 000000000000000000000000000000 (meaning the 'A's) followed by 1, followed by 1 zero
   -> 00000000000000000000000000000010

这应该明确表示您的字符串并允许您在 32 位中最多包含 15 个字符。

Answer 2

给定静态排序，您可以将每个单独的排列称为表示其在序列中的顺序的单个数字。然后你可以在另一边转换它而不是构建字典。

import itertools

def build_sequence(length):
    return itertools.product("ACTG", repeat=length)

def encode(sequence: str):
    seq = build_sequence(len(str))
    t_seq = list(sequence)  # to compare to seq
    for idx, s in enumerate(seq):
        if s == t_seq:
            return idx

def decode(e_sequence):
    max_length = math.ceil(math.log(e_sequence, 4))
    # max_length is the character count of ATCGs that e_sequence contains,
    #   since each sequence has 4**length elements
    seq = build_sequence(max_length)
    for _ in range(e_sequence):
        # skipping these is like indexing a list
        next(seq)
    return next(seq)

然后您可以将该数字打包成更小的类型并通过网络发送，再次解包并解码。

import struct

packed = struct.pack("I", encode(some_sequence))
#  send it? I'm not sure what you're doing with it

rcvd_pack = b'SUUU'
unpacked = struct.unpack("I", rcvd_pack)
# becomes a tuple of the value
enc_seq = unpacked[0]

result = decode(enc_seq)

这应该可以让您构建 16 个字符序列并将它们打包成 32 位数据。

Answer 3

根据 Khelwood 的信息，我用以下代码解决了这个问题：

b = {'A':0b00,'C':0b01,'G':0b10,'T':0b11}
t = {'00':'A','01':'C','10':'G','11':'T'}

def binarize(string):
    result = 0
    for char in (string + 'G').ljust(16,'A'): result = (result << 2) + d[char]
    return result

def textualize(value):
    result = ''
    for twobits in [ format(value, '032b')[i:i+2] for i in range(0,32,2) ]:
        result += t[twobits]
    return result.rstrip('A')[:-1]

>>> binarize('TTTTTTTTTTTTTTT')
    4294967294

>>> textualize(4294967294)
    u'TTTTTTTTTTTTTTT'

我确信有一种更有效的方法来完成这一切，我认为我需要这样做，因为我将编码和解码数十亿次，但现在它至少有效:)

将字符串存储为整数的函数

Function to store strings as ints

python

bioinformatics

dna-sequence