По-бързо групиране по сходство в python

Имам колекция от няколко хиляди низа (ДНК последователности). Искам да намаля това до няколко стотин (точният брой не е критичен), като изключа последователности, които са много сходни.

Мога да направя това чрез съпоставяне с помощта на модула "Levenshtein". Работи, но е доста бавно и съм почти сигурен, че трябва да има много по-бърз начин. Кодът тук е същият подход, но приложен към думи, за да бъде по-тестваем; за мен с това прекъсване отнема около 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)

Опитах няколко различни варианта и някои други съвпадащи модули (Mellyfish), без да стана значително по-бърз.


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

Отговори (2)


arrow_upward
3
arrow_downward

Може би бихте могли да използвате чувствително към местоположението хеширане. Можете да хеширате всички низове в кофи, така че всички низове в една кофа да са много подобни една на друга. След това можете да изберете само една от всяка кофа.

Никога не съм го използвал лично (не знам колко добре работи във вашия случай), това е просто идея. свързани: Python digest/hash за сходство на низ

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. Алтернативен начин за изчисляване на разстоянието между два ДНК фрагмента е използването на оценка за подравняване (която е свързана с Levenshtein чрез непостоянни тегла на подравняване). С помощта на biopython можете да извършите подравняване на множество последователности и да създадете филогенетично дърво. Ако искате да имате по-бързо решение, използвайте BLAST, което е евристичен подход. Това биха били последователни решения, докато вашето зависи от произволния избор на входните последователности.

Относно първоначалния ви въпрос, няма "просто" решение за ускоряване на вашия код.

person Denis    schedule 27.02.2014