Algoritmo per la ricerca di sequenze ripetute continue

Question

Sto cercando un algoritmo che trovi brevi ripetizioni in tandem in una sequenza del genoma.

Fondamentalmente, data una stringa molto lunga che può consistere solo dei 4 caratteri 'ATCG', ho bisogno di trovare brevi ripetizioni tra 2-5 caratteri che sono uno accanto all'altro.

es: TACATGAGATCATGATGATGATGATGGAGCTGTGAGATC darebbe ATGATGATG o ATG ripetuti 3 volte

L'algoritmo ha bisogno di scalare fino a una serie di 1 milione di personaggi così sto cercando di ottenere il più vicino al tempo di esecuzione lineare possibile .

Il mio attuale algoritmo: Dal momento che le ripetizioni possono essere lunghi 2-5 caratteri, io controllare il personaggio stringa personaggio e vedere se il carattere ennesimo è lo stesso che il carattere N + X, con X essendo da 2 a 5. Con un contatore per ogni X che conta corrispondenze sequenziali e ripristina in caso di mancata corrispondenza, sappiamo se c'è una ripetizione quando X = il contatore. Le ripetizioni successive possono quindi essere controllate manualmente.

Answer 1

State guardando ogni personaggio che vi dà O(n), dal momento che si confrontano su ogni personaggio successivi (massimo) cinque caratteri questo ti dà una costante c:

var data = get_input(); 
var compare = { `A`, `T`, `G`, `A`, `T` }   // or whatever 
var MAX_LOOKAHEAD = compare.length 
var n 
var c 

for(n = data_array.length; n < size; i++) {  // Has runtime O(n) 

    for(c = 0; c < MAX_LOOKAHEAD; c++) {   // Maximum O(c) 

    if(compare[c] != data[i+c]) { 
     break; 
    } else { 
     report("found match at position " + i) 
    } 

    } 
} 

E 'facile vedere che questo funziona O(n*c) volte. Dal momento che lo c è molto piccolo, può essere ignorato - e penso che non si possa sbarazzarsi di quella costante - il che si traduce in un runtime totale di O(n).

La buona notizia:

è possibile accelerare questo con parallelizzazione. Per esempio. potresti dividerlo in intervalli k e lasciare che più thread facciano il lavoro per te dando loro indici di inizio e fine appropriati. Questo potrebbe darti un incremento lineare .

Se lo fai assicurati di considerare le intersezioni come casi speciali in quanto potresti perdere una partita se i tuoi intervalli dividono una partita in due.

E.g. n = 50000:

Partizione per 4 thread: (n/10000) - 1 = 4. Il quinto thread non avrà molto da fare dato che gestisce solo le intersezioni ed è per questo che non abbiamo bisogno di considerare il suo overhead (nel nostro caso minuscolo).

1     10000    20000    40000    50000 
|-------------------|-------------------|-------------------|-------------------| 
| <- thread 1 -> | <- thread 2 -> | <- thread 3 -> | <- thread 4 -> | 
        |---|    |---|    |---|    
        |___________________|___________________| 
             | 
            thread 5 

e questo è come potrebbe sembrare:

var data; 
var compare = { `A`, `T`, `G`, `A`, `T` }; 
var MAX_LOOKAHEAD = compare.length; 

thread_function(args[]) { 

    var from = args[0]; 
    var to = args[1]; 

    for(n = from ; n < to ; i++) { 

     for(c = 0; c < MAX_LOOKAHEAD; c++) { 
     if(compare[c] != data[i+c]) { 
      break; 
     } else { 
      report("found match at position " + i) 
     } 
     } 
    } 
} 

main() { 
    var data_size  = 50000; 
    var thread_count = 4; 
    var interval_size = data_size/(thread_count + 1) ; 

    var tid[] 

    // This loop starts the threads for us: 

    for(var i = 0; i < thread_count; i++) { 
     var args = { interval_size * i, (interval_size * i) + interval_size }; 

     tid.add(create_thread(thread_function, args)); 
    } 

    // And this handles the intersections: 

    for(var i = 1; i < thread_count - 1; i++) { 
     var args = { interval_size * i, (interval_size * i) + interval_size }; 

     from = (interval_size * i) - compare.length + 1; 
     to = (interval_size * i) + compare.length - 1; 

     for(j = from; j < to ; j++) { 

      for(k = 0; k < MAX_LOOKAHEAD; k++) { 
       if(compare[k] != data[j+k]) { 
        break; 
       } else { 
        report("found match at position " + j) 
       } 
      } 
     } 
    } 

    wait_for_multiple_threads(tid); 
}