3.4 Identificare bubbles in un grafo orientato: MouthCycle
3.4.1 Descrizione metodologia
Sia G = (V, E) un grafo orientato e siano s, t ∈ V , richiamiamo due definizioni già date nel (cap.3.2.1):
Definizione 11 ((s,t)-bubble) Con (s,t)-bubble intendiamo due vertex di-
sjoint (s,t)-path ovvero due (s,t)-path che non hanno alcun nodo in comune.
Definizione 12 ((s,t)-path) Un (s,t)-path è un cammino da un source-node
s ad un target-node t.
MouthCycle fondamentalmente si divide in due fasi distinte: 1. trasformazione di G in un grafo G0
s = (Vs0, Es0).
2. ricerca in G0
s di particolari cicli elementari.
Di seguito approfondiamo queste due distinte fasi dell’algoritmo ad iniziare dalla fase di trasformazione.
(FASE 1): Trasformazione G in G0s
Il grafo direzionato G = (V, E) viene trasformato in un grafo G0
s = (V
0
s, E
0
s),
dove s è un parametro fondamentale nella costruzione e corrisponde ad un qualunque source-node s ∈ V :
Vs0 = {v, ¯v|v ∈ V }
3.4 Identificare bubbles in un grafo orientato: MouthCycle 41
Vediamo di descrivere a parole il formalismo: l’insieme dei nodi V0
s sarà
costituito da tutti i nodi v ∈ V e per ognuno di essi verrà aggiunto un nuovo nodo che denoteremo ¯v. In seguito con la notazione ¯V = V0
s/V ci riferiremo ai
soli nodi del tipo ¯x.
Definizione 13 (twin vertices) Due vertici x,¯x ∈ Vs0 sono detti twin verti- ces, nodi gemelli.
L’insieme degli edge E0
s sarà invece costituito da l’unione di questo elenco:
1. gli stessi archi di G meno tutti gli archi entranti in s.
2. per ogni arco (u, v) ∈ E aggiungeremo un arco nel senso opposto fra i rispettivi twin vertices (¯v, ¯u).
3. un arco (v, ¯v) che congiungerà ogni nodo v ∈ V al suo nodo twin corri- spondente fatta eccezione del source-node s.
4. un arco (¯s, s) che congiungerà ¯s ad s stesso.
Definizione 14 (twin arc) Definiamo twin arc ogni arco(¯v, ¯u) ∈ Es0 fra twin nodes.
Figura 3.10: A sinistra un grafo G, a destra il rispettivo grafo G0
s ottenuto
applicandogli la procedura di trasformazione descritta. [33]
(FASE 2): Ricerca cicli elementari in G0s
Definizione 15 (bipolar cycle) Un ciclo in G0s è detto bipolare se contiene vertici sia in V che in ¯V
Definizione 16 (swap arc) Definiamo swap arc l’arco (t, ¯t) ∈ Es0 che con- giunge il target-node t al suo nodo gemello ¯t per un qualche t ∈ V .
Siccome per costruzione esiste un solo arco che congiunge un nodo ¯v ad un nodo v, l’arco (¯s, s), in un ciclo bipolare può esistere un solo swap arc.
Definizione 17 (twin free cycle) Un ciclo C è detto twin free, se non con-
tiene nessuna coppia di twin vertices fatta eccezione per (s, ¯s) e (t, ¯t)
Definizione 18 (bubble-cycle) Definiamo bubble-cycle un twin free cycle C
in G0s con dimensione maggiore di 4.
I bubble-cycle non sono quindi altro che dei cicli elementari che hanno come caratteristica particolare la bipolarità. Questa è la differenza di fondo che c’è tra il metodo Johnson originale [36] ed il suo adattamento proposto in MouthCycle [33]. Il motivo del lower bound 5 per i bubble-cycle è puramente strutturale, infatti per costruzione esiste un ciclo s, v, ¯v, ¯s per ogni nodo v adiacente ad s. A questi cicli non corrisponde perciò alcuna bubble in G, e la condizione permette di non rilevare tali strutture.
Relazione bubble-cycle/(s,t)-bubble
Ricapitolando, fin qui abbiamo detto che trasformeremo il grafo G nel grafo
G0s ed in questo nuovo grafo andremo a scovare i cicli elementari bipolari che
abbiamo definito bubble-cycle. Ma dato che il nostro problema originale è quello di individuare le (s, t) − bubble, ancora sfugge il motivo per cui applichiamo questo metodo. Il tutto però viene chiarito dalla seguente proposizione:
Proposizione 3 Dato un vertice s in G, esiste una corrispondenza 1:2 tra
l’insieme delle (s,t)-bubbles in G per ogni t ∈ V , e l’insieme delle bubble-cycle in G0s.
La proposizione, dimostrata valida nell’articolo originale, ci garantisce che ad ogni (s,t)-bubble corrispondano 2 distinti bubble-cycle e ad avvalorare questo fatto mostro un esempio che aiuta a vedere meglio questa corrispondenza:
3.4.2
Dettagli algoritmo
MC adatta al problema della ricerca di bubble-cycle il principio dell’algoritmo proposto da Johnson, studiato per enumerare tutti i cicli elementari in un grafo. I due problemi sono piuttosto simili, abbiamo visto infatti che i bubble-
cycle sono cicli elementari in G0s, con la particolarità che sono anche bipolari.
3.4 Identificare bubbles in un grafo orientato: MouthCycle 43
Figura 3.11: A sinistra un grafo G, in cui viene evidenziata una (s,t)-bubble (con s = U0, t = U3). Questa corrisponde a 2 bubble-cycle in G0
s evidenziati
in nero e grigio in G0
s.
bubble detection in polynomial delay: il numero di attraversamenti massimo
che intercorre tra l’output di due bubble-cycle consecutivi è O(|V | + |E|). Se si esegue l’algoritmo su G0
s per ogni s ∈ V , nell’articolo originale si dimostra
che verranno identificate tutte le (s,t)-bubble di G. Per una complessità totale dell’algoritmo nel caso peggiore pari a O((|V | + |E|)C) dove C è il numero di cicli rilevati, per far ciò verrà attraversato ricorsivamente il grafo G0
s, seguendo
una strategia depth first e tenendo traccia delle seguenti informazioni:
• Uno stack: che contiene i nodi del path da s al nodo corrente. Ogni volta che è possibile raggiungere ¯s dal nodo corrente con la condizione che il ciclo sia di dimensione superiore a 4, lo stack viene mandato in output perchè il contenuto corrisponde ad un bubble-cycle
• Una variabile status(v): per ogni nodo v ∈ V0
s che può avere tre possibili
valori:
– free: v è visitabile nell’attraversamento di G0s ossia non è presente
nello stack;
– blocked: v non può essere visitato in quanto è già presente nello
stack (cioè è già stato visitato) o perchè, durante l’esecuzione, pas- sando attraverso v non si è riusciti a chiudere nessun bubble-cycle. In tal caso infatti, per evitare di riattraversare un nodo dal quale già sappiamo non si arriverà in ¯s, v resta blocked. Sarà nuovamente sbloccato (status(v)=free) nel momento in cui, passando per un no- do adiacente a v si riesce a chiudere un bubble-cycle, infatti solo in
quel momento saremo certi che, nel proseguo dell’esecuzione, anche passando per v potremo chiudere un ciclo.
– twined: v ∈ ¯V e il rispettivo nodo twin è nello stack. In questo caso
v non può essere visitato.
• Un insieme Bset(v) per ogni nodo v che contiene tutti gli in-nodes w
(nodi che hanno v come nodo adiacente (w, v) ∈ E0
s) dai quali non è
stato possibile chiudere nessun ciclo. Da quanto detto si può dedurre che neanche passando attraverso v si riesce a chiudere un ciclo, ma se una modifica nello stack fa in modo che v venga sbloccato, allora viene sbloccato anche qualsiasi w ∈ Bset(v).
Intuitivamente l’idea che sta dietro Bset e status blocked (nel caso parti-
colare in cui un nodo v non sia nello stack) è quella di evitare inutili visite passando per un path che già in precedenza avevamo attraversato senza che ciò ci avesse portato alla chiusura di un bubble-cycle. Questa intuizione viene maggiormente chiarita con una attenta lettura del pseudocodice riportato di seguito con un breve commento. L’algoritmo si suddivide in tre funzioni:
• La funzione Main (3.12), in cui vengono inizializzate le variabili e viene chiamata la funzione ricorsiva CYCLE (3.13) per ogni s ∈ V .
• La funzione ricorsiva CY CLE :: Node −→ Bool (3.13) che riceve in input il nodo da attraversare e restituisce:
– true: se attraverso il nodo corrente si è chiuso almeno un bubble-
cycle
– false: se attraverso il nodo corrente non si è chiuso neanche un
bubble-cycle
Con N+(v) denotiamo l’insieme dei nodi w adiacenti a v. La variabile f
ha il compito di memorizzare il valore che verrà restituito dalla funzione (come detto sopra). Lo pseudocodice di CYCLE è suddiviso in 3 blocchi principali: le istruzioni nelle linee [5-22] vengono eseguite solo nel caso in cui il nodo che si sta attraversando è v ∈ V0
s/ ¯V, nelle linee [24-36] viene
trattato un qualunque nodo ¯v ∈ ¯V , mentre nelle linee [37-46] se f = true viene sbloccato v richiamando la procedura UNBLOCK(3.14) altrimenti
v viene inserito nella Bset di ogni suo nodo adiacente w ma non viene
3.4 Identificare bubbles in un grafo orientato: MouthCycle 45
descritta precedentemente: nel momento in cui passando per un qualun- que v non si è riusciti a chiudere nessun bubble-cycle, immagazziniamo questa importante informazione con l’azione di non sbloccare v ma anzi inserendolo nella Bset di ogni suo nodo adiacente w (linee [42-44]). Non
appena uno di questi nodi adiacenti w verrà sbloccato (quindi tramite w si è chiuso un bubble-cycle) dovranno essere sbloccati anche tutti i nodi presenti nella sua Bset (essendo (v, w) ∈ Vs0 anche da v siamo di nuovo
in grado di chiudere un bubble-cycle).
• La procedura UNBLOCK (3.14) riceve in input un nodo v e si comporta sbloccando v e tutti i nodi contenuti nella sua Bset
3.4 Identificare bubbles in un grafo orientato: MouthCycle 47
Figura 3.14: [33]
3.4.3
Possibili varianti
Quello descritto nel precedente paragrafo, rappresenta le linee generali seguite dall’algoritmo decritto in [33], ma alcune modifiche possono essere apportate in modo da migliorarne alcuni aspetti. Per guidare nella comprensione faremo riferimento spesso allo pseudocodice esposto precedentemente usando solo i nomi delle funzioni Main, CYCLE, UNBLOCK ma riferendosi rispettivamente a (3.12), (3.13), (3.14).
Versione Space Efficient
Come anticipato al termine dell’introduzione al paragrafo 3.4, si può pensare di ridurre lo spazio necessario dall’algoritmo in modo da ottenere complessità lineare O(|V | + |E|). La modifica sostanzialmente consiste nel saltare, della FASE1 di trasformazione di G = (V, E) in G0 s = (V 0 s, E 0 s), la parte riguardante
la duplicazione dei nodi, usando allo stesso tempo due accorgimenti:
• una variabile booleana swaped, che verrà inizializzata false nel Main, ci informerà del fatto che si stia attraversando un nodo v ∈ V o un nodo v ∈ ¯V . Questa variabile cambierà valore in true prima di iniziare l’attraversamento dello swap-arc con la chiamata a CYCLE in linea 18 e verrà reimpostata a false al rientro da tale chiamata (∼ linea 20). Chiameremo questa, l’operazione di swap del grafo.
• per ogni nodo v ∈ V manteniamo non solo l’insieme N+(v) di nodi
adiacenti, ma anche l’insieme N−(v) di nodi w che hanno v come nodo
adiacente, (w, v) ∈ E. Nel codice si può intervenire scorrendo gli elementi
1 Si lavorerà quindi su un grafo G0
s = (V, E
0
s). Si noti il fatto che è necessario
comunque mantenere informazioni separate legate allo status nonchè al con- tenuto del Bset. Nasce quindi la necessità di differenziare l’UNBLOCK di un
nodo v rispetto a quella del suo twin ¯v, perchè venga presa in considerazione, fra le due, la Bset legata al nodo corrente. La soluzione proposta consiste nel- l’aggiungere un argomento booleano, chiamiamolo is-twin-node, alla funzione
UNBLOCK, il cui valore è:
• false: se il nodo da sbloccare è v ∈ V • true: se il nodo da sbloccare è v ∈ ¯V
in questo modo possono essere differenziati i due casi con un semplice controllo. Inoltre è anche da tener in conto la possibilità che un nodo v ∈ V sia elemento della Bset di ¯v, questo avviene solo nel caso in cui da v non si sia chiuso alcun
bubble-cycle. Nel ramo is-twin-node = true dobbiamo aggiungere un controllo
in modo che nel suddetto caso venga invocata la UNBLOCK con parametro
twin-node = false.
Un’altra modifica utile al risparmio di spazio, consiste nell’evitare di registrare l’informazione di adiacenza fra il nodo v e ¯v, che unito alla precedente modifica significherebbe adiacenza fra il nodo e se stesso. Per garantire la correttezza dell’algoritmo è però necessario il seguente accorgimento: nel caso in cui da un nodo v ∈ V non si riesca a chiudere alcun bubble-cycle occorre inserire v nel
Bset di ¯v aggiungendo il controllo e l’istruzione fra le righe 45, 46 di CYCLE.
Terminato il ciclo nelle linee [9-15] di CYCLE, verrà solamente effettuato lo
swap del grafo e chiamato cycle nuovamente sul nodo corrente. Quest’ultima
modifica si rivela utile nel caso si scelga di rappresentare il grafo mediante liste di adiacenza.
Riduzione corrispondenza (s,t)-bubble/bubble-cycle
Nel paragrafo 3.4, fra le altre cose, viene descritta l’importante relazione che sussiste tra bubble-cycle e (s,t)-bubble affermando che: ad ogni (s,t)-bubble in
G corrispondono 2 bubble cycle in G0s. Esiste cioè una corrispondenza 1:2
tra le due strutture. La metà dei risultati ottenuti al termine dell’esecuzione del metodo sarà perciò ridondante. Di seguito descrivo una variazione che permette di porre rimedio a questa situazione: consideriamo l’esistenza di un
1in seguito capiterà ancora di riferirsi ai nodi v e ¯v perchè quest’idea di fondo agevola la
3.4 Identificare bubbles in un grafo orientato: MouthCycle 49
ordinamento fra i nodi v ∈ V ed assegniamo lo stesso ordine ai rispettivi nodi
twin ¯v. Chiamiamo swap-predecessor (sp) il nodo nel ciclo C che precede t,
mentre chiamiamo swap-successor (ss) il nodo del ciclo C che succede ¯t. Dei due cicli trovati uno avrà come caratteristica sp<ss, per il secondo avverrà invece il contrario. L’unico caso in cui sp e ss possono essere identici è nella chiusura di un bubble-cycle di dimensione 4. Con questo controllo siamo quindi in grado di escludere anche questo tipo di cicli che non rispondono alla defi- nizione di bubble-cycle (cap. 3.4.1). Tutti gli altri casi in cui sp=ss vengono esclusi a priori dall’algoritmo in quanto si contravverrebbe la bipolarità. La variazione può essere applicata facilmente eseguendo in CYCLE linea 27 un controllo prima di stampare l’output, questo non comporta perciò alcun costo addizionale.
Aggiunta vincoli ai path
Per poter aggiungere dei vincoli ai path, come ad esempio quelli impiegati dal metodo di analisi descritto nel paragrafo 3.2, si può agire allo stesso modo eseguendo dei controlli prima dell’output in linea 27 di CYCLE, senza alterare il costo computazionale.
Un’applicazione di MouthCycle
Il lavoro svolto nasce con l’intento iniziale di realizzare un’implementazione efficiente dell’algoritmo MouthCycle (MC) (cap.3.4) su un grafo direzionato. In seguito un unico obiettivo ha segnato il suo evolversi:• la necessità di testare l’algoritmo su dati reali con il fine di provare a migliorare le performance di una qualsiasi applicazione che al suo interno preveda l’individuazione di bubble. Permettendo in questo modo anche il confronto delle performance dell’algoritmo con uno progettato per lo stesso un compito.
Sorprendentemente però, non esistono in letteratura algoritmi disegnati per ricercare bubbles in generale, siamo quindi costretti a confrontarci con appli- cazioni che implementano casi particolari.
Un lavoro di cui siamo a conoscenza che impiega un caso particolare dell’algo- ritmo è KisSplice (KS) (cap.3.3). Come abbiamo visto, KS è composto da una pipeline sequenziale di processi, di cui uno in particolare si occupa proprio del- la ricerca di bubble in un grafo di de Bruijn. La particolarità di tale processo consiste nel fatto che è progettato per rilevare solo bubble con i vincoli definiti dal modello di analisi (cap. 3.2). Al contrario MC, come abbiamo visto, nasce con l’intento più generale di rilevare tutte le bubble in un grafo orientato. Il lavoro è perciò proseguito con l’integrazione di MC nella pipeline di KS, in- serendolo in modo da sostituire completamente il processo con la medesima funzionalità. Con l’obiettivo sopracitato di migliorare le performance di KS è quindi chiaro che KisSplice con MouthCycle (KMC) parte penalizzato rispetto alla sua versione originale, ma nonostante ciò vedremo al termine del capitolo che i risultati saranno ugualmente favorevoli alla nostra modifica.
4.1 Implementazione MouthCycle 51
A questo va aggiunto, come mostreremo nel proseguo del capitolo, che tra le
bubble non previste nel modello di analisi e rilevate solo da MC, ce ne potrebbe-
ro essere alcune che corrispondono ad eventi di AS del tipo mutually exclusive
exon. In questo modo il lavoro realizzato apre la strada verso ulteriori risul-
tati interessanti. Riassumendo per raggiungere i nostri obiettivi andremo a studiare e modificare il funzionamento di KS, i cui realizzatori concedono li- beramente il codice1.
In questo capitolo verrà esposto il lavoro facendo prima una dettagliata de- scrizione delle scelte implementative e progettuali legate a MC, ed in seguito enunciando le variazioni e gli adattamenti apportati a MC e KS per perfezio- nare l’interfacciamento. Al termine del capitolo verranno mostrati i tempi di esecuzione delle due pipeline KS e KMC, applicate a dati reali provenienti da esperimenti di RNA-seq.
4.1
Implementazione MouthCycle
Il primo step del lavoro è stato quello di implementare l’algoritmo in un grafo orientato, nella sua variante space efficient con riduzione della corrispondenza fra (s,t)-bubble/bubble-cycle (cap. 3.4.3). Con l’idea di adattare l’algoritmo ad una successiva implementazione del DBG modello Pevzner (cap. 3.1.1), sono state fatte numerose scelte implementative e progettuali ad iniziare da quella di rappresentare il grafo tramite liste di adiacenza. Questa scelta è dettata dal fatto che da ogni nodo ci potranno essere al massimo 4 archi uscenti come mostrato nell’immagine, il che implica che su dati reali si tratteranno grafi tendenzialmente sparsi.
Figura 4.1: Ogni nodo v ha outdegree<=4
4.1.1
Progettazione
Abbiamo scelto di sfruttare la logica del paradigma ad oggetti per modellare il problema come mostrato nel seguente schema UML:
Figura 4.2: UML che rappresenta la relazione logica che sussiste fra le classi che modellano il nostro problema.
Nello schema 4.2, al di lá del contenuto delle classi che sarà commentato più avanti, si vuole porre l’accento sulle relazione fra di esse. L’idea generale è quella che ogni nodo mantenga la lista dei suoi nodi adiacenti. Il grafo, invece, avrà una qualche struttura dati che conterrà l’insieme dei nodi. Infine, la classe
BubbleEnumerator conterrà le funzioni e le informazioni necessarie prettamente
allo scopo di realizzare l’algoritmo MouthCycle. A sostegno di questa scelta, vi sono i principi di Single Responsibility e Cohesion, che fanno parte dei principi conosciuti, nell’ambito dell’ingegneria del software, con l’acronimo SOLID2.
4.1.2
Dettagli dell’implementazione
Come linguaggio di programmazione è stato scelto il C++, sfruttando le strut- ture dati implementate nella standard template library (STL), in cui la gestione dinamica della memoria è gestita dalle varie librerie. Di seguito analizzerò nel dettaglio le caratteristiche delle varie classi.
4.1 Implementazione MouthCycle 53
Figura 4.3: Attributi e funzioni della classe Node.
Classe Node
Node è la classe che rappresenta un singolo nodo del grafo, ma nella quale
vengono mantenute tutte le informazioni sia di v che ¯v, così come esposto fra le varianti di MouthCycle nel capitolo 3.4.3. Dallo schema 4.3 quanto detto è abbastanza evidente, infatti questa sua bivalenza è stata gestita suddividendo le rispettive informazioni. Nel codice con il prefisso node ci si riferisce alle in- formazioni del nodo v, mentre viene usato il prefisso twin per riferirsi a quelle del nodo ¯v. Si rende necessario anche il mantenimento di due liste di adiacenza distinte, che conterranno rispettivamente le informazioni dei nodi adiacenti a
v (next_list) e di quelli adiacenti a ¯v (prev_list), questi ultimi saranno logi-
camente gli stessi che precedono v. Per le liste di adiacenza ho impiegato due
singly-linked list implementate nella STL sotto il nome di forward-list. L’in-
terfaccia di Node consente solo di inserire o rimuovere un nodo adiacente a v mediante la funzione addNextNode() e il conseguente inserimento o cancella- zione del nodo successivo a ¯v è gestito automaticamente dalla stessa funzione. La funzione init ha il compito di inizializzare il nodo impostando lo stato di v e ¯v a free azzerando inoltre il contenuto delle rispettive Bset. Per lo stato del nodo e quello del twin sono state impiegate due distinte variabili, node_status e
twin_status, entrambe della dimensione di 3 bit adottando questa convenzione:
• 100: lo stato è free; • 010: lo stato è blocked;
• 001: lo stato è twined; • 000: solo per il nodo ¯s;
Queste informazioni vengono impostate dalle funzioni set_Status(s:Status) ed interrogate dalle funzioni isFree(), isBlocked() per v ed isTwinFree(), isT-
winBlocked(), isTwinTwined()per ¯v. Le funzioni di interrogazione presentano
tutte la stessa struttura di controllo: ad esempio, la funzione isFree() effet- tua un controllo sulla combinazione di node_status, se questa è 100 restituisce
true. L’unico nodo il cui stato può avere la combinazione di bit 000 è il nodo ¯s,
l’interrogazione su tale combinazione spetta alla funzione isBubbleEnd(), che verifica l’eventuale chiusura di un ciclo. Il tipo Status è una enumerazione {F, B, T } (Free, Blocked, Twined), mentre NodeStatus è un array di 3 bit im- plementato per mezzo della classe bitset della STL.
I Bset per v e ¯v sono entrambi implementati mediante la classe set della STL, la quale costruisce un balanced search tree i cui dettagli non sono forniti dalle specifiche dallo standard C++0x. Questa scelta è stata fatta per velocizza- re l’operazione di interrogazione w ∈ Bset, per un qualche w ∈ V , controllo richiesto dalla funzione CYCLE (si veda lo pseudocodice 3.13 alla linea 42). In questo modo l’operazione è garantita in O(log n). La funzione addInB-
set(u:Node&, twin:bool) a seconda dell’argomento booleano twin inserirà il
nodo u nella corretta struttura dati.
Classe Graph
Figura 4.4: Attributi e funzioni della classe Graph.
Per la classe Graph ho implementato le funzioni di costruzione necessarie per: l’inserimento di un nodo ed il suo reperimento; l’inserimento e la rimozione di un arco dati due nodi. La classe Graph, inoltre, prevede un costruttore in
4.1 Implementazione MouthCycle 55
grado di generare un grafo direzionato a partire da un file di testo. Questo file sarà composto da due colonne node-from e node-to, nelle quali verranno