Быстрый способ найти строки на расстоянии Хэмминга x друг от друга в большом массиве случайных строк фиксированной длины

Question

У меня есть большой массив с миллионами последовательностей ДНК длиной всего 24 символа. Последовательности ДНК должны быть случайными и могут содержать только A, T, G, C, N. Я пытаюсь найти строки, которые находятся на определенном расстоянии друг от друга.

Моим первым подходом было вычисление расстояния Хемминга между каждой струной, но это заняло бы много времени.

Мой второй подход использовал метод маскирования, чтобы создать все возможные варианты строк и сохранить их в словаре, а затем проверить, был ли этот вариант найден более 1 раза. Это работало довольно быстро (20 минут) для расстояния Хэмминга 1, но очень требовательно к памяти и было бы непригодным для использования на расстоянии Хэмминга 2 или 3.

Python 2.7 реализация моего второго подхода.

sequences = []
masks = {}
for sequence in sequences:
    for i in range(len(sequence)):
        try:
            masks[sequence[:i] + '?' + sequence[i + 1:]].append(sequence[i])
        except KeyError:
            masks[sequence[:i] + '?' + sequence[i + 1:]] = [sequence[i], ]

matches = {}
for mask in masks:
    if len(masks[mask]) > 1:
        matches[mask] = masks[mask]

Я ищу более эффективный метод. Я натолкнулся на три-деревья, KD-деревья, n-граммы и индексирование, но я заблудился относительно того, что будет лучшим подходом к этой проблеме.

Answer 1

Нашел мое решение здесь: http://www.cs.princeton.edu/~rs/strings/

Это использует троичные деревья поиска и заняло всего пару минут и ~ 1 ГБ оперативной памяти.Я изменил файл demo.c, чтобы он работал для моего варианта использования.

Answer 2

Один из подходов - Хеширование с учетом локальных особенностей

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

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

Ваша проблема может быть математически преобразована как:

С учетом N векторов v ∈ R^{24}, N<<5^24 и максимального расстояния Хэмминга d, возвратите пары, у которых расстояние Хемминга не более d.

Способ решения этой проблемы заключается в случайном генерировании K самолетов {P_1,P_2,...,P_K} в R^{24}; Где K - параметр, с которым вам придется поэкспериментировать. Для каждой точки данных v вы определите хеш v как кортеж Hash(v)=(a_1,a_2,...,a_K), где a_i∈{0,1} обозначает, находится ли v над этой плоскостью или под ней. Вы можете доказать (я опущу доказательство), что если расстояние Хемминга между двумя векторами мало, то вероятность того, что их хэш близок, высока.

Таким образом, для любой заданной точки данных вместо проверки всех точек данных в последовательностях вы проверяете только точки данных в ячейке «закрытых» хэшей.

Обратите внимание, что они основаны на эвристике, и вам нужно будет поэкспериментировать с K и тем, насколько «близко» вы хотите искать по каждому хешу. При увеличении K количество ваших бинов увеличивается экспоненциально, но вероятность подобия увеличивается.

Судя по тому, что вы сказали, похоже, у вас есть гигантский набор данных, поэтому я подумал, что выкину это, чтобы вы подумали.