Более быстрая кластеризация подобия в python

У меня есть коллекция из нескольких тысяч строк (последовательностей ДНК). Я хочу сократить это число до пары сотен (точное число не критично), исключив очень похожие последовательности.

Я могу сделать это с помощью сопоставления с помощью модуля «Левенштейн». Это работает, но довольно медленно, и я почти уверен, что должен быть гораздо более быстрый способ. Код здесь — тот же подход, но примененный к словам, чтобы сделать его более проверяемым; у меня с такой отсечкой это занимает около 10 секунд и собирает ~1000 слов.

import Levenshtein as lev
import random
f = open("/usr/share/dict/words", 'r')
txt = f.read().splitlines()
f.close()
cutoff = .5
collected = []
while len(txt) > 0:
    a = random.choice(txt)
    collected.append(a)
    txt = filter( lambda b: lev.ratio(a,b) < cutoff, txt)

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


python cluster-analysis similarity
person iayork    schedule 27.02.2014    source источник

Ответы (2)


arrow_upward
3
arrow_downward

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

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

person Karamba    schedule 27.02.2014
comment
+1 Хэширование строк перед их сравнением - единственный способ быстро решить эту проблему. См. en.wikipedia.org/wiki/Soundex для примера того, как это работает. - person Aaron Digulla; 27.02.2014

arrow_upward
0
arrow_downward

Я не совсем уверен, на что нацелено ваше приложение, но при работе с последовательностями вы можете рассмотреть возможность использования Biopython. Альтернативным способом расчета расстояния между двумя фрагментами ДНК является использование оценки выравнивания (которая связана с Левенштейном непостоянными весами выравнивания). Используя biopython, вы можете выполнить множественное выравнивание последовательностей и создать филогенетическое дерево. Если вы хотите получить более быстрое решение, используйте BLAST, который представляет собой эвристический подход. Это будут последовательные решения, в то время как ваше зависит от случайного выбора входных последовательностей.

Что касается вашего первоначального вопроса, нет «простого» решения для ускорения вашего кода.

person Denis    schedule 27.02.2014