Algoritmi veloci per la ricerca di set unici in due molto lunghe sequenze di testo

Question

ho bisogno di confrontare le sequenze di DNA di cromosomi X e Y, e trovare modelli (composto di circa 50-75 paia di basi) che sono unici per il cromosoma Y. Si noti che queste parti della sequenza possono ripetersi nel cromosoma. Questo deve essere fatto rapidamente (BLAST impiega 47 giorni, necessita di poche ore o meno). Esistono algoritmi o programmi particolarmente adatti a questo tipo di confronto? Ancora una volta, la velocità è la chiave qui.

Uno dei motivi per cui l'ho inserito in SO è stato ottenere la prospettiva da persone esterne al dominio dell'applicazione specifico, che possono elaborare gli algoritmi utilizzati nella comparazione delle stringhe nel loro uso quotidiano, che potrebbero applicarsi al nostro utilizzo. Quindi non essere timido!

Answer 1

1. costruire un suffix tree S in sequenza X.
2. Per ogni posizione di partenza i in sequenza Y, cercare la stringa Y [i..i + 75] a S. Se nessuna corrispondenza può essere trovato a partire da posizione i (vale a dire se la ricerca fallisce dopo j < 75 nucleotidi corrispondenti) allora hai trovato una lunghezza j stringa univoca per Y.
3. La più piccola stringa di questo tipo su tutte le posizioni iniziali i è la stringa univoca più breve (o si ferma semplicemente dopo trova una stringa di questo tipo se non sei interessato a minimizzare la lunghezza).

Tempo totale: O (| X | + m | Y |) dove m è la lunghezza massima della stringa (ad esempio m = 75).

Ci sono probabilmente ancora più efficiente algoritmi basati su alberi di suffisso generalizzate.

Answer 2

Questo paper potrebbe avere alcune alternative per l'adattamento di BLAST per migliorare le sue prestazioni (suddividendo lo spazio dei problemi AFAIKS).

Answer 3

Io parto dal presupposto che si dispone di un singolo X e un singolo Y per confrontare. Concatenarli, separati da un carattere di indicatore che non appare in nessuno dei due, per formare ad es. Xoy. Ora forma lo http://en.wikipedia.org/wiki/Suffix_array in tempo lineare.

Quello che ottieni è un array di puntatori alle posizioni nella stringa concatenata, in cui i puntatori sono disposti in modo che le sottostringhe che indicano siano visualizzate in ordine alfabetico nell'array. Vedrete anche una serie LCP, dando la lunghezza del più lungo prefisso comune condivisa tra un suffisso e il suffisso direttamente prima che nella matrice, che è il suffisso che ordina poco meno di esso. Questo è infatti il ​​più lungo prefisso comune condivisa tra questa posizione e qualsiasi sottostringa meno, perché qualsiasi cosa con un prefisso più comune e meno di string [i] sarebbe sorta tra esso e la stringa corrente [i - 1].

È possibile indicare quale stringa originale punta un puntatore dalla sua posizione, perché X viene prima di Y. È possibile tagliare l'array in sottosezioni alternate di puntatori X e Y. La lunghezza del prefisso comune condiviso tra pos [i] e pos [i - 1] è lcp [i]. La lunghezza del prefisso condiviso tra pos [i] e pos [i-2] è min (lcp [i], lcp [i-1]). Quindi, se inizi dal valore Y poco prima di un intervallo di X, puoi calcolare il numero di caratteri di prefisso tra quella Y e tutte le X, a turno abbassando la sezione, eseguendo un'operazione minima ad ogni passaggio. Allo stesso modo è possibile calcolare il numero di caratteri di prefisso condivisi tra tutte quelle X e Y visualizzata accanto nella matrice suffisso al costo di un min per X. Idem, naturalmente per Y gamme. Ora fai un massimo per ogni voce per calcolare il prefisso più lungo condiviso tra ogni posizione in X (o Y) e qualsiasi posizione in Y (o X).

Penso che vuoi le sottostringhe all'interno di X o Y che hanno piccoli prefissi condivisi tra esso e qualsiasi altra sottostringa dell'altro sesso, perché le stringhe un carattere più lungo di questo a partire dalla stessa posizione non compaiono nell'altro sesso a tuttiPenso che dopo aver eseguito i calcoli min() sopra puoi estrarre le sottostrutture con il prefisso N più piccolo usando un heap per tenere traccia delle N voci più piccole. Penso che tutto qui richieda tempo lineare in | X | + | Y | (a meno che N sia paragonabile a | X | or | Y |).

Answer 4

Ho una risposta interessante, sarà tecnologica. L'idea principale è che i confronti delle sequenze secondarie dovrebbero essere fatti su GPU, perché la GPU delle moderne schede video è un ambiente di elaborazione altamente parallelo (come un piccolo supercomputer). Quindi possiamo codificare la coppia di basi come un pixel, dato che il cromosoma X è di 154 milioni di paia- otteniamo un'immagine per il cromosoma X che consiste di 154 milioni di pixel - questa dimensione dell'immagine sarà di circa 500 MB. Per il cromosoma Y otteniamo un'immagine di 160 MB. Quindi queste due immagini (500 + 160) MB potrebbero essere gestite in modo molto efficace dalla scheda video di discesa. (Basta ottenere una scheda video con> = 1 GB di ram video).

passo successivo è quello di scrivere il programma GPU, forse con l'aiuto di Pixel Shader o Cuda o OpenCL

programma GPU sarebbe semplice - in fondo si confronterà 50-75 pixel vicini immagine cromosoma Y in a tutti i pixel di X immagine cromosomica. Quindi questo programma GPU dovrebbe avere un massimo di 75 * 154 milioni di operazioni, che saranno calcolate sulla GPU moderna in un'ora circa. Poiché tutte le sottosequenze di Y saranno testate in parallelo.

speranza che aiuti