complessità in spazio ed in tempo

Come convenzioni, S (source) è la sequenza dalla quale vengono calcolati i grafi ed è lunga n, T (target) è la sequenza che si cerca di coprire con le sottostringhe di S ed è lunga m, k è la dimensione dell'alfabeto, u è la dimensione di una stringa della quale si vuole verificare il riconosicmento da parte di G (grafo di S), l è la lunghezza minima delle sottostringhe ritenute valide per essere usate nella copertura di T.
[costruzione del grafo]
[grafo]
[calcolo della copertura]

costruzione del grafo

top

Esaminando il [procedimento schematizzato in precedenza] si nota che avvengono n iterazioni del ciclo principale ([READ][ADD][WALK][CURSOR]) ed in ognuna di queste si ha un ciclo [WALK], lungo tanto quanti sono i cursori attivi in quel passo d'iterazione.
Nel caso pessimo, al passo i-esimo si hanno al massimo i-1 cursori attivi, dato che il loro numero parte da 0 e se ne aggiunge al massimo uno ad ogni passo.
Nel caso medio di una sequenza casuale di caratteri la quantità di cursori attivi al passo i-esimo è invece solo logk(i), questo in quanto tale numero rappresenta la stima della massima lunghezza di una sottostringa diretta terminante nel carattere i-esimo di S, la quale risulta essere già stata vista all'interno della sezione di S immediatamente precedente al carattere i-esimo.
Statistiche : [cursori attivi] durante la creazione dei grafi da sequenza casuali.
Nel caso medio di una sequenza genetica umana la quantità di cursori attivi ad ogni passo risulta avere un andamento sostanzialmente simile a quello osservato per le sequenze casuali, modulo alcune occasionali e brevi fluttuazioni quando nell'analisi si arriva a zone in cui vi sono geni in tandem, LINEs, le zone dei telomeri ed altri punti in cui vi sono tratti di genoma con un'alta ripetitività di un certo pattern di basi.
Statistiche : [cursori attivi] durante la creazione dei grafi da sequenze genetiche umane.
In ognuna delle n iterazioni principali, per ognuno dei cursori attivi, è necessario individuare, se esiste, un arco diretto o laterale che permette di continuare il percorso; il tempo richiesto per quest'operazione è logaritmico con la quantità di archi uscenti dal nodo su cui è posto il cursore (essendo gli archi ordinabili secondo il valore del loro campo from).
Vi è sempre uno ed un solo arco diretto uscente.
La quantità di archi laterali uscenti da un nodo al passo i-esimo è nel caso pessimo i-1.
La quantità di archi laterali uscenti da un nodo al passo i-esimo nel caso medio di una sequenza casuale si è osservato essere prossimo ad un logk(n/i).
Statistiche : [archi laterali uscenti] nei grafi creati a partire da sequenza casuali.
La quantità di archi uscenti da un nodo al passo i-esimo nel caso medio di una sequenza genetica umana si è verificata essere sostanzialmente simile a quella osservata per le sequenze causuali, valgono le stesse osservazioni fatte in precedenza per la quantità di cursori attivi.
Statistiche : [archi laterali uscenti] nei grafi creati a partire da sequenze genetiche umane.
In pratica, la costruzione del grafo per una sequenza genetica reale non risulta, almeno così pare a seguito delle varie prove eseguite, richiedere una quantità di risorse di tempo diversa da quella richiesta per le sequenze casuali.
La richiesta di spazio invece è costante per tutte e tre le casistiche, infatti per generare il grafo vi è bisogno anche di poterlo percorrere e la sua dimensione è data dalla quantità di nodi più la quantità di archi più la dimensione dell'array STARTS: la quantità di nodi è pari a n, la quantità di archi diretti pari a n-1 la quantità di archi laterali non è superiore a n e la dimensione di STARTS è pari a k.
Lo spazio necessario per memorizzare anche i cursori è sempre limitato a n.
In conclusione, ricapitolando, le risorse di tempo sono:
- caso pessimo : O(n² log(n))
- caso medio (sequenze casuali) : O(n logk(n) log(logk(n)))
- caso medio (sequenze genetiche umane, k=4) : O(n log(n) log(log(n)))
Mentre le risorse di spazio sono:
- caso generico : O(n+k)
- caso biologico (k=4) : O(n)

grafo

top

La dimensione del grafo è data dalla quantità di nodi più la quantità di archi più la dimensione dell'array STARTS: la quantità di nodi è pari a n, la quantità di archi diretti pari a n-1, la quantità di archi laterali non è superiore a n e la dimensione di STARTS è pari a k.
Il tempo necessario ad un cursore per riconoscere il match o il mismatch di una sequenza lunga u è determinato dal fatto che sono necessari fino ad u passi in cui il cursore cerca un percorso sul grafo.
Il primo passo richiede un tempo logaritmico con la dimensione dell'alfabeto in uso per trovare il giusto campo dell'array STARTS.
Ogni passo successivo richiede un tempo logaritmico con la quantità di archi uscenti dal nodo su cui si trova il cursore, tale quantità è già stata studiata durante l'analisi della generazione del grafo, si veda dunque il precedente paragrafo per la sua valutazione.
Le risorse di tempo sono:
- caso pessimo : O(u log(n)+log(k))
- caso medio (sequenze casuali) : O(u log(logk(n))+log(k))
- caso medio (sequenze genetiche umane, k=4) : O(u log(log(n)))
Mentre le risorse di spazio sono:
- caso generico : O(n+k)
- caso biologico (k=4) : O(n)

Nei test eseguiti la crescita del fattore log(logk(n)) si è dimostrato essere insignificante anche per valori di n dell'ordine di 10^7. In pratica, il tempo richiesto nei casi reali su sequenze genomiche si può considerare O(u).

calcolo della copertura

top

Esaminando l'[algoritmo di copertura] si osserva che l'idea dell'algoritmo è di scorrere tutto T, analizzando le basi una per una o eventualmente, se si cade nel caso 1, anche saltando alcune brevi sequenze.
Diventa importante il parametro l: affinchè il confronto delle sequenze S e T sia significativo in termini statistici, cioè, affinchè le sequenze selezionate per la copertura abbiano una buona probabilità di essere significative e non siano semplicemente state prese per caso, occorre utilizzare un l superiore a logk(n).
Più è grande l, più il risultato della copertura è attendibile.
Di contro però, con l'aumentare dell'attendibilità, diminuisce la sensibilità. Questo perchè si ignorano tutte le sequenze più piccole di l che possono aver avuto il ruolo evolutivo che si va cercando.
Occorre quindi selezionare accuratamente un valore di l a seconda del rapporto sensibilità/attendibilità che si desidera ottenere.
Nella maggior parte dei test eseguiti è stato scelto di utilizzare l=2 logk(n).
Se nell'applicazione dell'algoritmo cado nel caso 1 il tempo necessario per concludere l'iterazione è:
- nel caso di fallimento, e quindi avanzando poi da 1 fino a l posizioni, il tempo di eseguire il match di una sequenza lunga fino a l.
- nel caso di successo trovando una sequenza lunga z, e quindi avanzando poi di z caratteri, il tempo di eseguire il match di una sequenza lunga l e poi di un'altra lunga z.
Se nell'applicazione dell'algoritmo cado invece nel caso 2 il tempo necessario per concludere l'iterazione è:
- nel caso di fallimento, e quindi avanzando poi di 1 sola posizione, il tempo di eseguire due match di una sequenza lunga fino a l per determinare massimo suffisso e massimo prefisso, nel caso pessimo si dovranno poi eseguire fino ad altri l-1 match lunghi fino a l.
- nel caso di successo trovando una sequenza non sovrapposta lunga z, e quindi avanzando poi di z caratteri, il tempo di eseguire il match di una sequenza lunga z.
- nel caso di successo trovando una sequenza sovrapposta lunga z, e quindi avanzando poi da 1 fino a z-1 caratteri, il tempo può arrivare ad essere lo stesso richiesto da un fallimento.
Il tempo richiesto nel caso medio per terminare la computazione dipende dalla probabilità di verificarsi dei casi e dei sottocasi: per l elevati, ottenendo dati attendibili ma poco sensibili, ci si imbatte principalmente nel caso 1 dell'algoritmo, per l inferiori ci si imbatte invece più di frequente nel caso 2, questo porta a stime medie di tempo diverse tra di loro.
Statistiche : [influenza della lunghezza minima l] nel calcolo della copertura.
Le stime sui casi medi sono state fatte utilizzando l>2 logk(n).
Le risorse di tempo sono:
- caso pessimo : O(m l²)
- caso medio (sequenze casuali) : O(m)
- caso medio (sequenze genetiche umane, k=4) : O(m)
Mentre le risorse di spazio sono:
- caso generico : O(n+k)
- caso biologico (k=4) : O(n)