Два дополнения в Python (сдвиг влево на много бит с округлением)

Question

Как мы могли бы закодировать обратную последовательность последовательности ДНК из ее кода?

Последовательность ДНК может содержать 4 разных символа A, C, G, T; где A - дополнение к T, а C - дополнение к G.

Обратный комплемент последовательности ДНК - это комплемент последовательности, но обратным образом (мы вычисляем комплемент каждого символа справа налево).

Пример: дополнение (AA): TT, дополнение (AC) - GT и так далее...

В общем, используя python, мы кодируем последовательность, отображая каждый символ в число от 0 до 3,

    {A:0, C:1, G:2, T:3}

тогда кодировка АА равна: 0, кодировка АС:

    AC = 0*4^0+1*4^1 = 4

кодировка GT:

    GT = 2*4^0+3*4^1 = 14 

Как я мог преобразовать код каждой последовательности в ее обратное дополнение в python, не создавая словарь? Для приведенного выше примера: преобразовать 4 в 14? и от 0 до 15 ...

Answer 1

Ваш набор символов слишком мал, чтобы хеш-карта была действительно эффективной. И смешивание двух дополнений в вашу проблему только что вызвало путаницу.

symbols = 'ACGT'
complements = symbols[::-1]   # reverse order
import string
table = string.maketrans(symbols, complements)
sample = 'ACCGTT'
print(sample[::-1].translate(table))
# output: AACGGT

Преобразование в какой-нибудь битовый формат заняло бы меньше места, но потребовало бы гораздо большей специальной обработки, так как вам нужно было бы отслеживать размеры по отдельности, выполнять произвольно широкие сдвиги и так далее. Python, безусловно, может сделать это, в частности, с помощью int(), принимающего множество баз и создающего результаты произвольной ширины, но это, вероятно, контрпродуктивный обходной путь.

digits = string.digits[:len(symbols)]
length = len(sample)
digitmap = string.maketrans(symbols, digits)
number = int(sample.translate(digitmap), len(digits))

def reversemapnumber(function=id, number=0, radix=0b100, length=0):
    result = 0
    for i in range(length):
        number,digit = divmod(number, radix)
        result = result*radix + function(digit)
    return result
revcomplemented = reversemapnumber(function=lambda x: 3-x,
        number=number, length=length)
# binary form
print('{:0{}b}'.format(revcomplemented, length*2))
# back to text form
print(''.join(symbols[(revcomplemented>>i)&0b11]
    for i in range(2*length-2, -2, -2)))

В этом беспорядке кода я использовал деление, а не сдвиги, чтобы быть несколько более общим (поддерживая основание, а не степень двух), но примеры печати полагаются именно на ширину. В конце концов, это просто сложно и непонятно.

Answer 2

Обратная сторона списка в python

>>> xs = [1,2,3]
>>> reversed(xs)
<listreverseiterator object at 0x10089c9d0>
>>> list(reversed(xs))
[3, 2, 1]
>>>

def complement(x):
   return ~x & 15 # as 15 == int('1111', 2) 

15 это битовая маска Представляет двоичный файл 1111, Затем мы используем двоичный and оператор.

>>> "{0:b}".format(complement(int('1111',2)))
'0'
>>> "{0:b}".format(complement(int('0001',2)))
'1110'
>>> "{0:b}".format(complement(int('1001',2)))
'110'

>>> xs = [int('1111',2), int('1001',2), int('0110',2), int('1011',2)]
>>> map(complement, xs)
[0, 6, 9, 4]
>>> list(reversed(map(complement, xs)))
[4, 9, 6, 0]

Основываясь на вашем примере, где

задана последовательность из 6 символов: ACCGTT, дополнением A является: T, а дополнением C является G; поэтому обратное дополнение ACCGTT: AACGGT.

Предположим, что у вас есть полная функция complement и обратная функция reverse,

у нас есть reverse(ACCGTT) = TTGCCA а также complement(ACCGTT) = TGGCAA, Обращение списка после вызова функции для каждого элемента аналогично вызову функции для каждого элемента в списке.

complement(reverse(ACCGTT)) = reverse(complement(ACCGTT))

Так что другая часть вопроса заключается в том, что вы хотите отобразить

{A:0, C:1, G:2, T:3}
A -> T | 0 -> 3
T -> A | 3 -> 0
C -> G | 1 -> 2
G -> C | 2 -> 1

который в двоичном будет

a = int('00', 2) # 0
c = int('01', 2) # 1
g = int('10', 2) # 2
t = int('11', 2) # 3

def complement(x):
    return ~x & 3 # this 3 is the same as int('11', 2)

def reverse_complement(list_of_ints):
    return list(reversed(map(complement, list_of_ints)))