Approssimativi algoritmi di corrispondenza delle stringhe

Qui al lavoro, spesso abbiamo bisogno di trovare una stringa dall’elenco di stringhe che è la corrispondenza più vicina con un’altra stringa di input. Attualmente, stiamo usando l’algoritmo di Needleman-Wunsch. L’algoritmo restituisce spesso molti falsi positivi (se impostiamo il punteggio minimo troppo basso), a volte non trova una corrispondenza quando dovrebbe (quando il punteggio minimo è troppo alto) e, il più delle volte, dobbiamo controllare i risultati a mano. Abbiamo pensato di provare altre alternative.

Hai qualche esperienza con gli algoritmi? Sai come si confrontano gli algoritmi l’uno con l’altro?

Gradirei davvero qualche consiglio.

PS: Stiamo codificando in C #, ma non dovresti preoccupartene – sto chiedendo gli algoritmi in generale.


Oh, mi dispiace di aver dimenticato di dirlo.

No, non lo stiamo usando per abbinare i dati duplicati. Abbiamo una lista di stringhe che stiamo cercando – la chiamiamo lista di ricerca. E poi dobbiamo elaborare i testi da varie fonti (come feed RSS, siti web, forum, ecc.) – estraiamo parti di quei testi (ci sono interi set di regole per questo, ma questo è irrilevante) e dobbiamo abbinare quelli contro la lista di ricerca. Se la stringa corrisponde a una delle stringhe nella lista di ricerca, dobbiamo eseguire un’ulteriore elaborazione della cosa (che è anche irrilevante).

Non possiamo eseguire il confronto normale, perché le stringhe estratte dalle fonti esterne, il più delle volte, includono alcune parole extra ecc.

Ad ogni modo, non è per il rilevamento di duplicati.

OK, Needleman-Wunsch (NW) è un classico allineatore end-to-end (“globale”) della letteratura bioinformatica. Era molto tempo fa disponibile come “align” e “align0” nel pacchetto FASTA. La differenza era che la versione “0” non era così prevenuta sull’evitare il gapping finale, che spesso permetteva di facilitare le corrispondenze interne di alta qualità. Smith-Waterman, sospetto che tu sappia, è un allineatore locale ed è la base originale di BLAST. FASTA aveva anche il proprio allineatore locale che era leggermente diverso. Tutti questi sono essenzialmente metodi euristici per stimare la distanza di Levenshtein relativa a una metrica di punteggio per coppie di caratteri individuali (in bioinformatica, spesso data da Dayhoff / “PAM”, Henikoff & Henikoff, o altre matrici e solitamente sostituita con qualcosa di più semplice e più ragionevolmente riflettente di sostituzioni nella morfologia del termine linguistico quando applicata al linguaggio naturale).

Non vogliamo essere preziosi sulle etichette: la distanza di Levenshtein, come minimo nella pratica, è fondamentalmente la distanza di modifica e devi stimarla perché non è fattibile calcolarla in generale, ed è costoso calcolare esattamente anche in casi speciali interessanti: l’acqua ci si immerge rapidamente, e quindi abbiamo metodi euristici di lunga e buona reputazione.

Ora per quanto riguarda il tuo problema: diversi anni fa, ho dovuto verificare l’accuratezza delle letture brevi del DNA rispetto alla sequenza di riferimento che si sa essere corretta e ho trovato qualcosa che ho chiamato “allineamenti ancorati”.

L’idea è di prendere il set di stringhe di riferimento e “digerirlo” trovando tutte le posizioni in cui si verifica una sottostringa data da un N carattere. Scegli N in modo che la tabella che costruisci non sia troppo grande ma anche che le sottostringhe di lunghezza N non siano troppo comuni. Per piccoli alfabeti come le basi del DNA, è ansible trovare un hash perfetto su stringhe di caratteri N e creare una tabella e concatenare le corrispondenze in un elenco collegato da ciascun contenitore. Le voci dell’elenco devono identificare la sequenza e iniziare la posizione della sottostringa che esegue il mapping al raccoglitore nel cui elenco si verificano. Si tratta di “ancore” nell’elenco delle stringhe da cercare in cui è probabile che un allineamento NW sia utile.

Quando si elabora una stringa di query, si prendono i caratteri N a partire da un offset K nella stringa di query, li si hash, si cerca il loro bin e se l’elenco per quel bin è non vuoto si passa a tutti i record di elenco e si eseguono gli allineamenti tra la stringa di query e la stringa di ricerca a cui si fa riferimento nel record. Quando esegui questi allineamenti, allinea la stringa di query e la stringa di ricerca all’ancora ed estrai una sottostringa della stringa di ricerca che ha la stessa lunghezza della stringa di query e che contiene quell’ancora con lo stesso offset, K.

Se scegli una lunghezza di ancoraggio N abbastanza lunga e un ragionevole insieme di valori dell’offset K (possono essere distribuiti su tutta la stringa della query o essere limitati a offset bassi) dovresti ottenere un sottoinsieme di possibili allineamenti e spesso otterranno vincitori più chiari. Normalmente si vorrà usare l’allineatore NW meno allineato alla fine di tipo align0.

Questo metodo cerca di incrementare un po ‘NW limitando il suo input e questo ha un guadagno in termini di prestazioni perché fai meno allineamenti e sono più spesso tra sequenze simili. Un’altra buona cosa da fare con il tuo allineatore NW è di permettere che si arrenda dopo un certo ammontare o la lunghezza del gapping per ridurre i costi, specialmente se sai che non vedrai o non sarai interessato a partite di qualità media.

Infine, questo metodo è stato utilizzato su un sistema con piccoli alfabeti, con K limitato alle prime 100 posizioni nella stringa di query e con stringhe di ricerca molto più grandi delle query (le letture del DNA erano circa 1000 basi e le stringhe di ricerca erano attive dell’ordine di 10000, quindi cercavo corrispondenze di sottostringhe approssimative giustificate da una stima della distanza di modifica specifica). Adattare questa metodologia al linguaggio naturale richiederà un attento esame: si perde sulla dimensione dell’alfabeto, ma si guadagna se le stringhe di query e le stringhe di ricerca sono di lunghezza simile.

In entrambi i casi, consentire l’utilizzo simultaneo di più di un’ancora da estremità diverse della stringa di query potrebbe essere utile per filtrare ulteriormente i dati inviati a NW. Se si esegue questa operazione, prepararsi a inviare eventualmente stringhe sovrapposte contenenti ciascuna delle due ancore dell’allineatore e quindi riconciliare gli allineamenti … o eventualmente modificare ulteriormente NW per enfatizzare mantenendo le ancore per lo più intatte durante un allineamento utilizzando la modifica della penalità durante l’esecuzione dell’algoritmo.

Spero che questo sia utile o almeno interessante.

Relativo alla distanza di Levenstein: potresti voler normalizzarlo dividendo il risultato con la lunghezza della stringa più lunga, in modo da ottenere sempre un numero compreso tra 0 e 1 e in modo da poter confrontare la distanza della coppia di stringhe in modo significativo modo (l’espressione L (A, B)> L (A, C) – per esempio – non ha significato se non si normalizza la distanza).

Algoritmi alternativi da considerare sono gli algoritmi agrep ( Wikipedia entry su agrep ), FASTA e BLAST . Questi sono casi speciali di corrispondenza approssimativa delle stringhe , anche nella repositry dell’algoritmo Stony Brook . Se riesci a specificare i modi in cui le stringhe differiscono l’una dall’altra, potresti probabilmente concentrarti su un algoritmo su misura. Ad esempio, aspell utilizza una variante della distanza “soundlike” (soundex-metaphone) in combinazione con una distanza “da tastiera” per accogliere allo stesso modo sia i malintenzionati che i cattivi.

Stiamo utilizzando il metodo di distanza Levenshtein per verificare la presenza di clienti duplicati nel nostro database. Funziona abbastanza bene.

Usa l’ indice FM con Backtracking, simile a quello dell’allineamento fuzzy di Bowtie

Per minimizzare i disallineamenti dovuti a leggere variazioni o errori di ortografia, ho usato l’algoritmo del Metaphone, quindi la distanza di Levenshtein (adattata a 0-100 come percentuale di corrispondenza) sulle codifiche di Metaphone per una misura di vicinanza. Sembra che abbia funzionato abbastanza bene.

Per espandere la risposta di Cd-MaN, sembra che tu stia affrontando un problema di normalizzazione. Non è ovvio come gestire i punteggi tra gli allineamenti con lunghezze diverse.

Dato ciò che ti interessa, potresti voler ottenere valori p per il tuo allineamento. Se stai usando Needleman-Wunsch, puoi ottenere questi valori di p usando la statistica di Karlin-Altschul http://www.ncbi.nlm.nih.gov/BLAST/tutorial/Altschul-1.html

BLAST potrà allineamento locale e valutarli usando queste statistiche. Se sei preoccupato per la velocità, questo sarebbe un buon strumento da usare.

Un’altra opzione è usare HMMER. HMMER utilizza Profile Hidden Markov Models per allineare le sequenze. Personalmente, penso che questo sia un approccio più potente poiché fornisce anche informazioni sulla posizione. http://hmmer.janelia.org/