python - 将字符串转换为 64 位整数映射字符到自定义两位值映射

Question

我正在尝试将一串字符(A、T、C、G)映射到一个 64 位整数，其中每个字母使用此映射表示为两位:

mapping = {'A': 0b00, 'C': 0b01, 'G': 0b10, 'T': 0b11} 

“sequence”字符串不会超过 28 个字符，我打算在整数开始时用零填充使其成为 64 位。目前，我使用以下功能，但速度非常慢。然后我通过调用转换输出:

int(result, 2)

这目前有效，但我想让这个功能非常快。我不太了解 C++，所以我很难移植到它。我现在正在尝试 Cython，但我也不熟悉它。任何有助于在 Python(或什至 C++ 或 Cython 等价物)中提高效率的帮助将不胜感激。

下面是我的代码，之后我又调用了 int()。

def seq_to_binary(seq):
    values = [mapping[c] for c in seq]
    BITWIDTH = 2
    return "".join(map(lambda x: bin(x)[2:].zfill(BITWIDTH), values)).encode();

典型的序列输入类似于:'TGTGAGAAGCACCATAAAAGGCGTTGTG'

Answer 1

您将一个由 4 个不同“数字”组成的字符串解释为一个数字，因此是 base 4 notation。如果您有一串 0-3 范围内的实际数字，您可以让 int() 非常快速地生成一个整数。

def seq_to_int(seq, _m=str.maketrans('ACGT', '0123')):
    return int(seq.translate(_m), 4)

以上函数使用str.translate()用匹配的数字替换 4 个字符中的每一个(我使用静态 str.maketrans() function 创建转换表)。然后将生成的数字串解释为以 4 为基数的整数。

请注意，这会产生一个整数对象，而不是零和一个字符的二进制字符串:

>>> seq_to_int('TGTGAGAAGCACCATAAAAGGCGTTGTG')
67026852874722286
>>> format(seq_to_int('TGTGAGAAGCACCATAAAAGGCGTTGTG'), '016x')
'00ee20914c029bee'
>>> format(seq_to_int('TGTGAGAAGCACCATAAAAGGCGTTGTG'), '064b')
'0000000011101110001000001001000101001100000000101001101111101110'

这里不需要填充；只要您的输入序列不超过 32 个字母，生成的整数将适合无符号 8 字节整数表示。在上面的输出示例中，我使用 format() 字符串将该整数值分别格式化为十六进制和二进制字符串，并将这些表示形式用零填充为 64- 的正确位数位数。

为了衡量这是否更快，让我们随机生成 100 万个测试字符串(每个字符串长 28 个字符):

>>> from random import choice
>>> testvalues = [''.join([choice('ATCG') for _ in range(28)]) for _ in range(10 ** 6)]

上述函数可以在我的配备 2.9 GHz Intel Core i7 和 Python 3.6.5 的 Macbook Pro 上在不到 3/4 秒内产生 100 万次转换:

>>> from timeit import timeit
>>> timeit('seq_to_int(next(tviter))', 'from __main__ import testvalues, seq_to_int; tviter=iter(testvalues)')
0.7316284350017668

所以每次调用需要 0.73 微秒。

(之前，我提倡预计算版本，但在实验之后我想到了 base-4 的想法)。

为了将此方法与目前发布在此处的其他方法进行比较，一些方法也需要进行调整以生成整数，并包装到函数中:

def seq_to_int_alexhall_a(seq, mapping={'A': b'00', 'C': b'01', 'G': b'10', 'T': b'11'}):
    return int(b''.join(map(mapping.__getitem__, seq)), 2)

def seq_to_int_alexhall_b(seq, mapping={'A': b'00', 'C': b'01', 'G': b'10', 'T': b'11'}):
    return int(b''.join([mapping[c] for c in seq]), 2)

def seq_to_int_jonathan_may(seq, mapping={'A': 0b00, 'C': 0b01, 'G': 0b10, 'T': 0b11}):
    result = 0
    for char in seq:
        result = result << 2
        result = result | mapping[char]
    return result

然后我们可以比较这些:

>>> testfunctions = {
...     'Alex Hall (A)': seq_to_int_alexhall_a,
...     'Alex Hall (B)': seq_to_int_alexhall_b,
...     'Jonathan May': seq_to_int_jonathan_may,
...     # base_decode as defined in https://stackoverflow.com/a/50239330
...     'martineau': base_decode,
...     'Martijn Pieters': seq_to_int,
... }
>>> setup = """\
... from __main__ import testvalues, {} as testfunction
... tviter = iter(testvalues)
... """
>>> for name, f in testfunctions.items():
...     res = timeit('testfunction(next(tviter))', setup.format(f.__name__))
...     print(f'{name:>15}: {res:8.5f}')
...
  Alex Hall (A):  2.17879
  Alex Hall (B):  2.40771
   Jonathan May:  3.30303
      martineau: 16.60615
Martijn Pieters:  0.73452

我提出的 base-4 方法很容易赢得这场比较。