Рассчитать матрицу попарных различий для большого количества последовательностей?

Я хотел бы рассчитать количество попарных различий между длинным списком последовательностей и вернуть его в матричную форму.

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

Например,

Sequence 1: "GAT-ACA"
Sequence 2: "AT-GCGA"
Number of differences: 6

(Дефис здесь позволяет выравнивать последовательности, и мои последовательности также могут включать тире).

Есть ли какой-нибудь эффективный способ сделать это с помощью python (или другого языка) с коротким временем вычислений? Я также задал этот вопрос в R, изначально намереваясь сделать это таким образом, но он оказался слишком медленным, чтобы его можно было применить к нескольким сотням последовательностей.

Благодарю вас!


python sequence matrix dna-sequence
person Jennifer Collins    schedule 08.07.2012    source источник
comment
Существуют пределы того, насколько быстро это можно сделать - для сравнения потребуется ~ O((L)(n^2)) где L - длина последовательности, хотя есть несколько более быстрых подходов; см. эту статью в открытом доступе   -  person Argalatyr    schedule 09.07.2012

Ответы (3)


arrow_upward
4
arrow_downward

Если вы хотите рассчитать матрицу, которая отображает различия между парами, вы можете сделать это следующим образом:

import numpy as np

def get_difference(x,y):
    return sum(ele_x != ele_y for ele_x, ele_y in zip(x,y))

my_list = ['abcde','abcwe','zbfwe']
n = len(my_list)

my_array = np.zeros((n,n))
#
for i, ele_1 in enumerate(my_list):
    for j, ele_2 in enumerate(my_list):
        if j >= i:
            break # Since the matrix is symmetrical we don't need to
                  # calculate everything
        difference = get_difference(ele_1, ele_2)  
        my_array[i, j] = difference
        my_array[j, i] = difference

Результат:

>>> my_array
array([[ 0.,  1.,  3.],
       [ 1.,  0.,  2.],
       [ 3.,  2.,  0.]])

Полученная матрица (массив OK) показывает различия между парами.

person Akavall    schedule 08.07.2012
comment
Сравнение, когда i == j, является пустой тратой (всегда 0) и может назначать симметричные ячейки (в том же операторе) для заполнения верхнего треугольника матрицы. - person Argalatyr; 08.07.2012
comment
@Argalatyr, оба хороши. Благодарю вас. Я отредактировал свой пост, чтобы отразить их. - person Akavall; 08.07.2012
comment
Спасибо!! Это именно то, что я искал, и запуск даже на большом количестве последовательностей не занимает много времени. Это определенно намного лучше, чем то, что я закодировал в R. - person Jennifer Collins; 11.07.2012

arrow_upward
2
arrow_downward

Заархивируйте строки в кортежи, а затем используйте сумму для подсчета логических значений True (т.е. несовпадающих точек).

s1 = "GAT-ACA"
s2 = "AT-GCGA"

print sum(a != b for (a,b) in zip(s1, s2))
person Maria Zverina    schedule 08.07.2012
comment
Если это не тот ответ, который вы ищете, опубликуйте еще несколько примеров входных и выходных данных. - person Maria Zverina; 08.07.2012
comment
+1. Хотя я бы использовал itertools.izip. (если это не Python 3) - person Joel Cornett; 08.07.2012

arrow_upward
0
arrow_downward

Если я правильно понимаю, то просто:

diff = lambda seq1, seq2: sum(seq1[i]!=seq2[i] for i in range(len(seq1)))
person acondolu    schedule 08.07.2012